> [!definition|*] Trees > Any of the following are equivalent definitions of **trees**: > > Trees are connected, acyclic graphs. > > Trees are minimally connected graphs. > - That is, a connected graph $T$ where for any $e \in E(T)$, the subgraph $(V(T),E(T)-\{ e \})$ is no longer connected. > > Trees are maximally acyclic graphs. > - That is, $T$ is acyclic, but adding edge $xy$ for any $x,y \in V(T)$ makes a cycle. > [!proof]- Proof of equivalence > (Minimally connected $\Rightarrow$ acyclic) proof by contradiction, breaking an edge in any cycle does not affect connectedness. > > (Connected + acyclic $\Rightarrow$ minimal connected) proof by contradiction, if removing edge $p_{xy}$ still gives a connected graph with $xy$-path $q_{xy}$, then $p_{xy}+q_{xy}$ is a cycle. > > (Minimally connected $\iff$ maximally acyclic): If the graph is minimally connected, then adding the edge ${xy}$ forms a cycle with the already-existing $xy$-path $q_{xy}$. Conversely, if removing ${xy}$ still gives a connected graph, then the remaining $xy$-path $q_{xy}$ forms a cycle with ${xy}$ in the original graph. ### Properties of Trees There is a unique path between vertices $x,y$ in a tree. > [!proof] > Suppose $p,q$ are distinct paths between $x,y$. > Let $w$ be the last common vertex of $p,q$ starting from $x$, and $z$ their next common vertex $w$, which exist since $p,q$ at least share vertices $x,y$. > Then joining sections of $p,q$ between $w,z$ gives a cycle, a contradiction. Any tree $T$ with $|V(T)| \ge 2$ vertices has at least $2$ leaves. > [!proof]- > Let $P$ be the maximal path in tree $T$, and denote its two ends as $x,y$. > Then $x$ (similarly $y$) has only one neighbor in $T$, i.e. the one immediately after (before) it in $P$, making them leaves. > > This is because: > - If there is a neighbor $a \not \in P$, appending it gives a longer path, a contradiction; > - If there is another neighbor $a \in P$, then there is a cycle ($a \to x$ via $P$, then returning via the edge $xa \not \in P$) unless $a$ is immediately next to $x$. Removing a leaf $v$ from tree $T$ still gives a tree. > [!proof]- > Acyclicity is trivial. Connectedness holds since any $xy$-path in $T$ is still one in $T-\{ v \}$ if $x,y \ne v$). If $G$ is connected with $n$ vertices, $G$ is a tree $\iff G$ has $n-1$ edges. > [!proof]- > $[\Rightarrow]$ induct by removing leaves repeatedly, until $G$ has only one vertex (the base case). > > $[\Leftarrow]$ spanning tree $H \subseteq G$ must have $n-1$ edges, but then $H=G$, so $G$ is a tree. ### Spanning Trees and Kruskal's Algorithm Any connected graph $G$ contains a **spanning tree**: a minimally connected subgraph with the same vertices. Given a weighted, connected graph $G$ with costs $c(e):V(G) \to \mathbb{R}$, **Kruskal's algorithm** finds the **minimum cost spanning tree (MCST)**. > [!algorithm] Kruskal's Algorithm > $[1]$ Initialize an empty set $A_{0}=\emptyset$ to store the edges in the MCST. > $[2]$ While there exists edge $e$ where $A_{i} \cup \{ e \}$ is acyclic, add the cheapest one to $A_{i}$ to get $A_{i+1}$. > $[3]$ Repeat $[2]$ until no such edge exists, then return the current $A_{i}$ as the MCST. > [!theorem|*] Kruskal's Algorithm > Kruskal's algorithm always returns a MCST $A$. > > > [!proof] Sketch Proof > > *Acyclicity* is by construction. > > *Connectedness*: if $(V(G), A)$ is not connected, then say the connected components are joined by edge $e$ in $G$, and adding $e$ to $A$ still gives an acyclic graph, and the algorithm should not have terminated. > > *Minimal Cost*: $A_{i}$ is always a subgraph of some MCST $B$ of $G$, so when $A$ grows to be a spanning tree, it must be a MCST. > > > [!proof]- Proof of the claim above > > > Proof by induction on each step; when $A_{i} \subseteq B$ grows to be $A\cup \{ e \} \not \subseteq B$, $B \cup \{ e \}$ contains a cycle $C$ by minimal acyclicity of $B$. > > > By minimality of $e$, there is an edge $f \in C$ in the cycle where $f \not \in A$ and $c(f) \ge c(e)$, else the entirety of $C-\{ e \}$ would have been added to $A$, and the addition of $e$ completes the cycle, contradicting the algorithm. > > > Now replace $f$ with $e$ to get $B' := B- \{ f \} \cup \{ e \}$, another spanning tree. Since $c(B')\le c(B)$, $B'$ must also be a MCST (and in fact their costs are equal), and $A \subseteq B'$.