Discrete-math 23

Forest #definition

\begin{matrix} Acyclic graph is called a forest \end{matrix}

Tree #definition

\begin{matrix} Connected acyclic graph is called a tree \end{matrix}

Leaf #definition

\begin{matrix} Vertex of degree 1 is called a leaf \end{matrix}

Leaves of a tree #lemma

\begin{matrix} Let T be a tree with n \geq 2 vertices \\ Then T has at least two leaves \\ Proof: \\ Let P be the longest simple path in T \\ T has at least one edge ⟹ Length of this path is at least 1 \\ P = (v_{0}, v_{1}, \dots, v_{k}), v_{0} \neq v_{1} \\ Suppose by contradiction d e g (v_{0}) > 1 \\ Then v_{0} has at least one more neighbor, let’s call it v^{'} \\ T has no cycles ⟹ v^{'} is not in P ⟹ (v^{'}, v_{0}, \dots, v_{k}) is longer than P - Contradiction! \\ The same can be done for v_{k} \\ ⟹ d e g (v_{0}) = d e g (v_{k}) = 1 ⟹ v_{0}, v_{k} are leaves of T \end{matrix}

Paths between vertices #lemma

\begin{matrix} Let G = (V, E) be a simple graph \\ Let v, u \in V \\ Then there is a path from v to u iff there is a simple path from v to u \\ Proof: \\ One direction is trivial, a simple path is a path and we are done \\ Let \exists P (v, u) = (v_{0}, v_{1}, \dots, v_{k}), v = v_{0}, u = v_{k} \\ Let w appear twice in the path, e.g. v_{i} = w = v_{j}, i < j \\ Then \exists P^{'} (v, u) = (v_{0}, v_{1}, \dots, v_{i}, v_{j + 1}, \dots, v_{k}) \\ This process can be repeated until there are no repeating vertices in the path \\ Namely, until we get a simple path \end{matrix}

Properties of the tree #theorem

\begin{matrix} G = (V, E) \\ 1. G is a tree \\ 2. G is maximal acyclic graph \\ 3. \forall v, u \in V : \exists! P (v, u) that is simple \\ 4. G is a minimal connected graph \\ Prove: 1 ⟺ 2 ⟺ 3 ⟺ 4 \\ Proof for 1 ⟹ 2 \\ Let G be a tree \\ G is connected ⟹ It has at least n - 1 edges \\ Adding an edge would make m \geq n which means that G \cup {e} will have a cycle \\ ⟹ G is a maximal acyclic graph \\ Proof for 2 ⟹ 3 \\ Let G be a maximal acyclic graph \\ Let v, u \in V \\ Suppose that there is no path between v and u \\ Then adding edge {v, u} will not create a cycle - Contradiction! \\ ⟹ \exists P (v, u) ⟹ \exists P (v, u) that is simple \\ Suppose that there are two paths from v to u \\ (v_{0}, v_{1}, \dots, v_{k}) \\ (u_{0}, u_{1}, \dots, u_{k}) \\ v_{0} = u_{k} = v \\ u_{0} = v_{k} = u \\ ⟹ \exists P (v, v) : (v_{0}, v_{1}, \dots, v_{k}, u_{1}, \dots, u_{k}) which is a cycle - Contradiction! \\ ⟹ \exists! P (v, u) that is simple \\ Proof for 3 ⟹ 4 \\ Let \exists! P (v, u) that is simple \\ ⟹ G is connected \\ Suppose \exists {v, u} \in E : G ∖ {{v, u}} is connected \\ ⟹ \exists P^{'} (v, u) \neq P (v, u) \\ ⟹ \exists Two simple paths from v to u - Contradiction! \\ ⟹ G is a minimal connected graph \\ Proof for 4 ⟹ 1 \\ Let G be a minimal connected graph \\ ⟹ G is connected \\ Suppose G has a cycle \\ Removing any edge from this cycle would still leave G connected - Contradiction! \\ ⟹ G has no cycles ⟹ G is a tree \\ 1 ⟹ 2 ⟹ 3 ⟹ 4 ⟹ 1 ⟹ 1 ⟺ 2 ⟺ 3 ⟺ 4 \end{matrix}

Number of edges in a tree #theorem

\begin{matrix} G = (V, E) \\ 1. G is a tree \\ 2. G is acyclic, | E | = n - 1 \\ 3. G is connected, | E | = n - 1 \\ Prove: 1 ⟺ 2 ⟺ 3 \\ Proof: \\ Let G be a tree \\ G is a tree ⟹ G is connected and acyclic ⟹ | E | \geq n - 1 \\ If | E | \geq n then G has a cycle ⟹ | E | < n \\ ⟹ | E | = n - 1 ⟹ 1 ⟹ 2, 1 ⟹ 3 \\ Let G be connected, | E | = n - 1 \\ Removing any edge will make the graph disconnected \\ ⟹ G is a minimal connected graph ⟹ G is a tree ⟹ 3 ⟹ 1 \\ Let G be acyclic, | E | = n - 1 \\ Suppose G is not connected \\ ⟹ # of components is at least 2 \\ Let G_{v}, G_{u} be two connected components of G \\ ⟹ There is no path from v to u \\ ⟹ Adding edge {v, u} will make number of edges equal to n and not create a cycle \\ ⟹ G \cup {{v, u}} has no cycle - Contradiction! \\ ⟹ G is connected ⟹ G is a tree ⟹ 2 ⟹ 1 \\ 1 ⟺ 2 \land 2 ⟺ 3 ⟹ 1 ⟺ 2 ⟺ 3 \end{matrix}