Exam 2023 (2A)

1b

\begin{matrix} Let G = (V, E) be a simple non-empty finite connected graph \\ Let e \in E : G^{'} = (V, E ∖ {e}) has two connected components \\ Prove: \exists v \in V : d e g (v) is odd \\ Proof: \\ Let \forall v \in V : d e g (v) is even \\ Let e = {v, u} \\ d e g (v) in G^{'} is equal to d e g (v) in G ⟹ it is odd \\ \sum_{u \in [w]_{\sim}} d e g (w) = 2 \cdot | E_{v} | = \underset{even}{\underset{⏟}{\sum_{u \in [w]_{\sim} ∖ {v}} \underset{even}{\underset{⏟}{d e g (w)}}}} + \underset{o d d}{\underset{⏟}{d e g (v)}} \\ ⟹ 2 \cdot | E_{v} | is odd - Contradiction! \\ ⟹ \exists v \in V : d e g (v) is odd \end{matrix}

\begin{matrix} Let A be a set \\ Let R, S be order relations on A \\ Prove or disprove: R \cup S is an order relation on A ⟺ R \subseteq S \lor S \subseteq R \\ Disproof: \\ A = {1, 2, 3} \\ R = I_{A} \cup {(1, 2)} \\ S = I_{A} \cup {(1, 3)} \\ R \cup S = I_{A} \cup {(1, 2), (1, 3)} \end{matrix}

\begin{matrix} Let A, B be sets \\ Prove or disprove: P (A) \cup P (B) = P (A \cup B) ⟺ (A \subseteq B) \lor (B \subseteq A) \\ Proof: \\ Let B \neq A \cup B \neq A \\ ⟹ A \cup B \in P (A \cup B), A \cup B \notin P (A), A \cup B \notin P (B) \\ ⟹ P (A) \cup P (B) \neq P (A \cup B) \\ ⟹ P (A) \cup P (B) = P (A \cup B) ⟹ (\underset{B \subseteq A}{\underset{⏟}{A \cup B = A}}) \lor (\underset{A \subseteq B}{\underset{⏟}{A \cup B = B}}) \\ ⟸ is trivial \end{matrix}

\begin{matrix} \forall a \in R : \forall r \geq 0 \in R define an open-ball of radius r around a to be \\ B (a, r) = {x \in R | | x - a | < r} \\ Set U \subseteq R is called open if \forall a \in U : \exists B (a, r) \subseteq U \\ Set X is called closed if X^{c} is open \end{matrix}

\begin{matrix} Is there a subset of R which is both open and closed? \\ Solution: \\ \emptyset is open (vacuously true) \\ e s e r t^{c} = R is open, B (x, 1) \subseteq R \\ ⟹ \emptyset is also closed \end{matrix}

\begin{matrix} Let {U_{i}}_{i \in [n]} be family of sets \\ Prove: \forall i \in [n] : U_{i} is open ⟹ ⋂_{i = 1}^{n} U_{i} is open \\ Proof: \\ Let x \in ⋂_{i = 1}^{n} U_{i} \\ ⟹ \forall i \in [n] : x \in U_{i} ⟹ \forall i \in [n] : \exists B (x, r_{i}) \subseteq U_{i} \\ n \in N ⟹ B = {r_{1}, r_{2}, \dots, r_{n}} is finite \\ ⟹ \exists r \in B : \forall r_{i} \in B : r_{i} \leq r ⟹ r_{i} = r \\ \forall i \in [n] : r \leq r_{i} ⟹ B (x, r) \subseteq U_{i} \\ ⟹ B (x, r) \subseteq ⋂_{i = 1}^{n} U_{i} \end{matrix}