4 Spanning Trees 4.2 ***Spanning Trees and Forests***4.4 ***Kruskal and other algorithms ***

4.3 Minimal spanning trees

Definition 4.17 (Minimal Spanning Tree ).

Consider a weighted graph $G, w$ . Given a subgraph $H\subset G$ , we define $w(H):=\sum_{e\in H}w(e).$ $M S T$ is said to be a minimal spanning tree if $w(MST)=\min\{w(T):\mbox{$T$ is a spanning tree}\}.$

Of course, minimal spanning tree exists if $G$ is a connected graph. A set of edges $S\subset E$ is said to be a cut³³ 3 Sometimes this is called a minimal cut and a cut is $S\subset E$ if $\beta_{0}(G-S)>\beta_{0}(G)$ . if $\beta_{0}(G-S)=\beta_{0}(G)+1$ and for any $S^{\prime}\subsetneq S$ , $\beta_{0}(G-S^{\prime})=\beta_{0}(G)$ .

Proposition 4.18 (Some properties of MST).

Let $G$ be a connected graph with edge-weights.

1.

Uniqueness : If $w:E\to\mathbb{R}$ is an injective function, then $M S T$ is unique.
2.

Cut property : If $M$ is a MST and $C$ is a cut in $G$ , then one of the minimal weight edges in $C$ should be in the $M$ .
3.

Cycle property : If $M$ is a MST and $C$ is a cycle in $G$ , then one of the maximal weight edges in $C$ will not be in $M$ .

Proof.

(i) : Let $T_{1},T_{2}$ be MSTs such that $T_{1}\neq T_{2}$ . Since $T_{1},T_{2}$ have the same vertex set, there exists an edge in $T_{1}\Delta T_{2}$ . Choose the edge $e_{1}$ with the least weight and WLOG let $e_{1}\in T_{1}$ . Since $T_{2}$ is a spanning tree, $T_{2}+e_{1}$ has a cycle $C$ . Since $C\subsetneq T_{1}$ , there exists $e_{2}\in C-T_{1}$ and also $e_{2}\in T_{1}\Delta T_{2}$ . Thus $w(e_{2})>w(e_{1})$ as $e_{1}$ has the least weight in $T_{1}\Delta T_{2}$ . As in the proof of insertion property for spanning trees (Lemma 4.15), we can show that $T_{2}+e_{1}-e_{2}$ is a tree. Thus, we have that $w(T_{2}+e_{1}-e_{2})<w(T_{2})$ and hence contradicting the minimality of $T_{2}$ .

(ii) : Let $C=\{e_{1},\ldots,e_{k}\}$ in non-decreasing order of weights. If $e_{1}:=(u,v)\notin M$ , then $M\cup e_{1}$ has a cycle. Since there exists a path in $M$ from $u$ to $v$ and $C$ is a cut, this path must pass through $e_{i}$ for some $i>1$ . This gives that $M-e_{i}+e_{1}$ is a spanning tree(since it has no cycles and has $n-1$ edges). But since $M$ is a MST, $w(e_{i})\leq w(e_{1})$ . By choice of $e_{1}$ , $w(e_{1})\leq w(e_{i})$ and so $w(e_{i})=w(e_{1})$ . Thus $e_{i}$ is a minimal weight edge and $e_{i}\in M$ as required.

(iii) : One can argue as above for this case too. ∎

Exercise* 4.19.

Prove (iii) in the above proposition.

4.3 **Minimal spanning trees**

Definition 4.17 (Minimal Spanning Tree ).

Proposition 4.18 (Some properties of MST).

Proof.

Exercise* 4.19.

4.3 Minimal spanning trees