Discrete-math 22

Discrete-math 22

Connected graph #definition

\begin{matrix} Simple graph G = (V, E) \\ Is called connected if \forall u, v \in V : d (u, v) < \infty ⟺ d i a m (G) < \infty \\ i.e. there is a path between any two vertices \end{matrix}

Subgraphs of a connected graph #lemma

\begin{matrix} Let G = (V, E) be a simple connected graph \\ Let S \subset V, S \neq \emptyset \\ Then \exists x \in V ∖ S : x \in Γ (S) \\ Proof: \\ S \neq \emptyset ⟹ \exists u \in S \\ S \subset V ⟹ \exists v \in V ∖ S \\ G is connected ⟹ exists a path from u to v \\ u = v_{1} \\ v = v_{k + 1} \\ (v_{1}, v_{2}, v_{3}, \dots, v_{k}, v_{k + 1}) \\ u \in S, v \notin S ⟹ \exists i \in [1, k] : v_{i} \in S, v_{i + 1} \notin S \\ Let x = v_{i + 1} \\ x \in V ⟹ x \in V ∖ S \\ v_{i} \in S and {v_{i}, x} \in E ⟹ x \in Γ (S) \end{matrix}

Properties of distance function #lemma

\begin{matrix} d : V \times V \to N \cup {0} \cup {\infty} \end{matrix}

Metric #definition

\begin{matrix} Let u, v, w \in V \\ 1. & d (u, v) \geq 0 \\ 2. & d (u, v) = 0 ⟺ u = v \\ 3. & d (u, v) = d (v, u) \\ 4. & d (u, v) + d (v, w) \geq d (u, w) \\ Any function that satisfies these properties \\ is called a metric \end{matrix}

Relation on vertices #definition

\begin{matrix} Let relation \sim on V \\ \forall u, v \in V : u \sim v ⟺ d (u, v) < \infty \\ This relation is: \\ 1. Reflexive: v \sim v \\ 2. Symmetric: u \sim v ⟺ v \sim u \\ 3. Transitive: u \sim v \land v \sim w ⟹ u \sim w \\ ⟹ \sim is an equivalence relation \\ Let u \in V \\ [u]_{\sim} = {v \in V | u \sim v} = {v \in V | d (u, v) < \infty} \end{matrix}

Connected component #definition

\begin{matrix} Let G = (V, E) be a simple graph \\ Let u \in V \\ Connected component of u is a sub-graph of G, \\ denoted as G_{u} = ([u]_{\sim}, E_{u}) \\ where E_{u} = {{x, y} | x, y \in [u]_{\sim}} \\ ^{V} /_{\sim} divides V into sets of vertices of graph’s connected components \end{matrix}

Number of connected components #definition

\begin{matrix} Let G = (V, E) be a simple graph \\ Let | V | = n, | E | = m \\ Then the number of connected components is at least n - m \\ Proof: \\ Base case. Let m = 0 \\ ⟹ There are no edges ⟹ Each vertex is a separate connected component \\ ⟹ There are n components, n \geq n - m = n - 0 \\ Induction step. Let the lemma hold for m edges \\ Let G^{'} = (V^{'}, E^{'}), | V^{'} | = n, | E^{'} | = m + 1 \\ | E^{'} | \geq 1 ⟹ E^{'} \neq \emptyset \\ Let e \in E^{'} \\ G^{'} ∖ {e} = (V^{'}, E^{'} ∖ {e}) has at least n - m connected components \\ Case 1. e connects two vertices in the same connected component of G^{'} ∖ {e} \\ ⟹ # of connected components of G^{'} is also \geq n - m \geq n - (m + 1) \\ Case 2. e connects two vertices in two different connected components \\ ⟹ # of connected components of G^{'} = # of connected components of G^{'} ∖ {e} - 1 \\ meaning it is now \geq (n - m) - 1 = n - (m + 1) \\ ⟹ Proved by Induction \end{matrix}

Number of edges in a connected graph #lemma

\begin{matrix} In any connected graph with n vertices there are at least n - 1 edges \\ Proof: \\ Let there be m < n - 1 edges \\ Then there are at least n - m > n - (n - 1) = 1 connected components \\ ⟹ Graph is not connected - Contradiction! \end{matrix}

Existence of a cycle by edges number #lemma

\begin{matrix} Let G = (V, E) be a simple graph with n \geq 3 vertices and m \geq n edges \\ Then G has a cycle \\ Proof: \\ Base case. Let n = 3 \\ m \geq n = 3 \\ The only possible graph with 3 vertices and 3 edges has a cycle \\ Induction step. Let lemma hold for n vertices \\ Let G^{'} = (V^{'}, E^{'}), | V^{'} | = n + 1, | E^{'} | = m \geq n + 1 \\ Let x \in V^{'} be a vertex with the minimal degree \\ Case 0. d e g (x) = 0 \\ ⟹ In G^{'} ∖ {x} = (V^{'} ∖ {x}, E^{'}) there are n vertices and m \geq n + 1 > n edges \\ ⟹ There is a cycle in G^{'} ∖ {x} \\ We didn’t remove any edges ⟹ G^{'} has a cycle \\ Case 1. d e g (x) = 1 \\ ⟹ There is no cycle containing vertex x \\ ⟹ G^{'} ∖ {x} has n vertices and m - 1 \geq n + 1 - 1 = n edges \\ ⟹ G^{'} ∖ {x} has a cycle \\ We didn’t remove any edges between vertices in this cycle ⟹ G^{'} has a cycle \\ Case 2. d e g (x) \geq 2 \\ ⟹ Degree of any vertex in G^{'} is \geq 2 \\ Start with some edge {u, v} \\ And begin to build the path without using the same edge twice \\ Number of edges is finite ⟹ The process stops at some point \\ Let the process stop at vertex v_{k} \\ d e g (v_{k}) \geq 2 ⟹ If v_{k} is a new vertex, we can continue ⟹ v_{k} is not a new vertex \\ ⟹ path (v_{1}, v_{2}, \dots, v_{k}) contains a sub-path from v_{k} to v_{k} \\ ⟹ There is a cycle from v_{k} to v_{k} \\ ⟹ Proved by Induction \end{matrix}