01 - Kruskal's Algorithm and MCST

Kruskal's Algorithm and MCST

Let $G$ be a connected graph
Let $c(e)$ be positive for each edge then

Kruskal’s Algorithm ends with MCST for $G$

Proof

As $V(H_t)=V(H_0)=V$ then $H_t$ then $H_t$ is spanning
Hence acyclic by construction

Suppose $H_t$ is not connected then
Let $C$ be a component of $H_t$

As $C$ does not contain all vertices then
Let $v$ be inside $C$ and $w$ be outside $C$
So $G$ contains a $v$-$w$ path which must leave $C$

Hence there exists edge $e=xy$ of $G$ with $x$ inside $C$ and $y$ outside
Hence $x$ and $y$ are not connected in $H_t$ hence $H_t+e$ is acyclic

This contradicts stopping rule in algorithm
Hence $H_t$ is a spanning tree

Thus $t=n-1$ where $n=|G|$

Let ${\mathcal{P}}_i$ be proposition such that exists MCST $T$ of $G$ with $H_i\subseteq T$ for $0\le i\le n-1$
So ${\mathcal{P}}_0$ holds as $H_0$ has no edges

If ${\mathcal{P}}_{n-1}$ holds then $H_{n-1}\subseteq T$ then
Both $H_{n-1}$ and $T$ have $n-1$ edges so

$$H_{n-1}=T$$

Thus $H_{n-1}$ is a MCST

Suppose $i<n-1$ and $P_i$ holds so

$$H_i\subseteq T$$

for some MCST $T$ of $G$

Let $e$ be the next edge added by algorithm so

$$H_{i+1}=H_i+e$$

If $e$ is an edge of $T$ then

$$H_{i+1}\subseteq T$$

Let $e=xy$ then $T$ contains $x$-$y$ path
Hence $T+e$ contains cycle $C$

As $H_{i+1}$ is acyclic then exists edge $f$ of $H$ not in $H_{i+1}$
Let $T^{\prime }=T+e-f$

As $H_{i+1}\subseteq T^{\prime }$ by construction then

$$H_{i+1}=H_i+e\subset T+e$$

where $f$ is not in $H_{i+1}$

As $T+e$ has $n-1$ edges then by Relation of connectivity and edges to a tree it is a tree
Hence $T+e$ is acyclic

Thus $f$ was a possible edge to add at step $i$ and by definition then

$$c(e)\le c(f)$$

Hence

$$c(T^{\prime })\le c(T)$$

and as $T$ has minimum cost then so does $T^{\prime }$