Exam 2023 (2B)

1b

\begin{matrix} Prove: \forall n even \in N : \exists tree G = (V, E) : \forall v \in V : d e g (v) \in {1, \frac{n}{2}} \\ Proof: \\ Let us build such a graph \\ Let n \in N be even \\ Let two vertices have an edge between them \\ Let’s call these vertices u, v \\ Now let us add \frac{n - 2}{2} vertices to Γ (v) \\ ⟹ d e g (v) = \frac{n - 2}{2} + 1 = \frac{n}{2} \\ Now let us add another \frac{n - 2}{2} vertices to Γ (u) \\ ⟹ d e g (u) = \frac{n - 2}{2} + 1 = \frac{n}{2} \\ Degrees of all vertices except u, v are 1 \\ d e g (u) = d e g (v) = \frac{n}{2} \\ There are no cycles and the graph is connected ⟹ G is a tree \end{matrix}

graph LR
5(...)
6(...)
9(...)
10(...)

1---2
3---1
4---1
5---1
6---1
2---7
2---8
2---9
2---10

\begin{matrix} Let f : A \to B \\ Prove or disprove: \forall X, Y \subseteq A : f [X ∖ Y] = f [X] ∖ f [Y] \\ Disproof: \\ Let 1 \in B \\ Let f (x) = 1 \\ Let X \neq Y \\ f [\underset{\neq \emptyset}{\underset{⏟}{X ∖ Y}}] = {1} \\ f [X] ∖ f [Y] = {1} ∖ {1} = \emptyset \end{matrix}

\begin{matrix} Prove or disprove: \forall A, B, C : A ∖ (B \cap C) = (A ∖ B) \cup (A ∖ C) \\ Disproof: \\ Left: x \in A, x \notin (B \cap C) ⟹ x \in A \land (x \notin B \lor x \notin C) \\ Right: (x \in A \land x \notin B) \lor (x \in A \land x \notin C) = x \in A \land (x \notin B \lor x \notin C) \\ ⟹ A ∖ (B \cap C) = (A ∖ B) \cup (A ∖ C) \end{matrix}

\begin{matrix} Let A be a set \\ Let R be a relation on A \\ Let S be a relation on A \\ S = {(a, b) \in A \times A | \forall c \in A : (a, c) \in R ⟹ (c, b) \in R} \\ Prove or disprove: R is an equivalence relation ⟹ R = S \\ Disproof: \\ A = {1, 2, 3} \\ R = I_{A} \\ S = I_{A} \cup {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)} \end{matrix}

\begin{matrix} Let X be a set \\ T \subseteq P (X) is called symmetric-complement if \\ 1. T \neq \emptyset \\ 2. \forall A, B \in T : A △ B \in T \\ 3. \forall A \in T : A^{c} \in T \end{matrix}

\begin{matrix} Let X be a set \\ Let T \subseteq P (X) be a symmetric-complement \\ Is \emptyset \in T ? \\ Solution: \\ \forall A \in T : \emptyset = A △ A \in T \end{matrix}

\begin{matrix} Let X be a set \\ Let T, S \subseteq P (X) be a symmetric-complements \\ Prove: T \cap S is a symmetric-complement \\ Proof: \\ \emptyset \in T, \emptyset \in S ⟹ \emptyset \in T \cap S ⟹ T \cap S \neq \emptyset \\ Let A, B \in T \cap S \\ ⟹ A, B \in T ⟹ A △ B \in T \\ ⟹ A, B \in S ⟹ A △ B \in S \\ ⟹ A △ B \in T \cap S \\ A \in T ⟹ A^{c} \in T \\ A \in S ⟹ A^{c} \in S \\ ⟹ A^{c} \in T \cap S \end{matrix}

\begin{matrix} Let X be a set \\ Let T, S \subseteq P (X) be a symmetric-complements \\ Prove: T \cup S is a symmetric-complement ⟺ T \subseteq S \lor S \subseteq T \\ Proof: \\ Let T \subseteq S (WLOG) \\ ⟹ T \cup S = S ⟹ T \cup S is a symmetric-complement \\ Let T \cup S be a symmetric-complement \\ Let A \in T ∖ S, B \in S ∖ T \\ A, B \in T \cup S \\ Let A △ B \in S \\ ⟹ (A △ B) △ B \in S ⟹ A \in S - Contradiction! ⟹ A △ B \notin S \\ ⟹ A △ B \in T \\ ⟹ A △ (A △ B) \in T ⟹ B \in T - Contradiction! ⟹ A △ B \notin T \\ ⟹ A △ B \notin T \cup S - Contradiction! \\ ⟹ T ∖ S = \emptyset \lor S ∖ T = \emptyset \\ ⟹ T \subseteq S \lor S \subseteq T \end{matrix}