24 Minimum Spanning Trees

• Let $G=(V,E)$ be an undirected, connected graph $G=(V,E)$ with $n$ vertices
  • connected: there is a path between any two vertices
• A subgraph $T=(V^{\prime },E^{\prime })$ of $G$ is said to be a spanning tree of $G$ if
  • spanning: $V^{\prime }=V$
  • tree: $|E^{\prime }|=n-1$ $G=(V,E)$ is undirected graph, then $H=(V^{\prime },E^{\prime })$ is a subgraph if $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$, then $H$ is spanning if $V^{\prime }=V$ i.e., $H$ contains all vertices of $V$.

A graph $T$ would be a tree only if:

1. $T$ has no cycles (1 + 2 $\Rightarrow$ 3)
2. $T$ is connected (2 + 3 $\Rightarrow$ 1)
3. $T$ has $n-1$ edges and $n$ vertices (1 + 3 $\Rightarrow$ 2)