4.4 ***Kruskal and other algorithms ***

The proof consists of two steps - Firtly, we will show that the output $M$ is a spanning tree and then show it is of minimum weight.

Step 1 : $M$ is a spanning tree. Clearly $M$ does not contain a cycle. If $M$ has at least two components $C_1,C_2$, then let $e$ an edge with minimal weight between $C_1$ and $C_2$. $e$ exists as $G$ is connected. $e$ would have been added in Step 2 when it was considered. Thus, we derive a contradiction to the fact that $M$ is disconnected. Hence $M$ is connected and acyclic, i.e., a spanning tree.

Step 2 : $M$ has minimum weight. We shall show that the following claim holds by induction : At every stage of the algorithm, there is a minimal spanning tree $T$ such that $M\subset T$.

The above claim suffices because at the last step, the output $M$ is the $M$ at the end of Step 3 and if it is a subgraph of a spanning tree $T$, then it must be that $M=T$ as $M$ is a spanning tree from Step 1.

Induction argument : The claim holds in the beginning because $M=\mathrm{\varnothing }$. Assume that the claim holds at some stage of the algorithm for a $M$ and a $T$.

Now, suppose that the next chosen edge creates a cycle, then $M$ does not change and the claim still holds.

So, let the next chosen edge not create a cycle and hence $M$ becomes $M+e$. If $e\in T$, we are done. Suppose $e\notin T$. Then $T+e$ has a cycle $C$. This cycle contains edges which do not belong to $M$, since $e$ does not form a cycle in $M$ but does in $T$. Note that, there exists $f\in C-M$ which has not been considered by the algorithms before and hence it must have weight at least as large as $e$. If $f$ had been considered before $e$ in the algorithm, $M-e+f$ will not contain a cycle (as $M-e+f\subset T$) and so $f$ would have been added to $M$ already.

Then $T-f+e$ is a tree by the insertion property and it has the same or less weight as $T$. If $w(f)=w(e)$, then $T-f+e$ is a minimum spanning tree containing $M+e$ and again the claim holds. If $w(f)>w(e)$, then $T-f+e$ is a spanning tree of strictly smaller weight than $T$ and leads to a contradiction. ∎

Denote the output by $\tilde{M}$. The proof of the fact that $\tilde{M}$ is a spanning tree is left as an exercise as the steps were sketched in the class. W e shall only show minimality here.

Claim : As with the proof of Kruskal’s algorithm, we shall show that at every step $M\subset M^{\ast }$ with the latter being a MST.

The claim is trivially true at the initial step when $M=\mathrm{\varnothing }$ and since MST exists. Suppose the claim is true upto some step with $M,T,S$ already determined i.e., $M\subset M^{\ast }$, a MST.

Let $e=(u,v)$ be the edge chosen by the Prim’s algorithm at this stage and suppose $e\notin M^{\ast }$. Then, there exists a path $P$ from $u$ to $v$ in $M^{\ast }$. This implies that there exists an edge $e^{\prime }\in P\cap (T\times S)$. But since Prim’s algorithm selected $e$ instead of $e^{\prime }$, we have that $w(e)\le w(e^{\prime })$. But since $P+e$ is a cycle in $M^{\ast }+e$, we can remove any edge from the cycle and still get a spanning tree. Thus, $M^{\ast }+e-e^{\prime }$ is also a spanning tree and since $M^{\ast }$ is a MST, we have that $w(e)\ge w(e^{\prime })$. Thus, we get that $w(e)=w(e^{\prime })$ and $M+e\subset M^{\ast }+e-e^{\prime }$, a MST. This proves the claim and completes the proof. ∎