Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?

Question

Question: Let G(V, E) be an undirected connected finite graph with the weight function w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of Kruskal’s algorithm that finds T (for suitable ordering of edges).

Answer: We show that the following proposition P is true by induction: If F is the set of edges chosen at any stage of the algorithm, then there is some minimum spanning tree that contains F and none of the edges rejected by the algorithm.

• Clearly P is true at the beginning, when F is empty: any minimum spanning tree will do, and there exists one because a weighted connected graph always has a minimum spanning tree.

• Now assume P is true for some non-final edge set F and let T be a minimum spanning tree that contains F. If the next chosen edge e is also in T, then P is true for F + e.

  Otherwise, if e is not in T then T + e has a cycle C. This cycle contains edges which do not belong to F, since e does not form a cycle when added to F but does in T. Let f be an edge which is in C but not in F + e. Note that f also belongs to T, and by P, it has not been considered by the algorithm. f must therefore have a weight at least as large as e. Then T − f + e is a tree, and it has the same or less weight as T. However since T is a minimum spanning tree then this new graph has the same weight as T, otherwise we get a contradiction and T would not be a minimum spanning tree .So T − f + e is a minimum spanning tree containing F + e and again P holds.

• Therefore, by the principle of induction, P holds when F has become a spanning tree, which is only possible if F is a minimum spanning tree itself.

Answer 1

To prove correctness of Kruskal's algorithm (and Prim's), you can use the cut property.

Lemma (The cut property). Let $\emptyset \subset S \subset V$ be a set of vertices and $e$ a cheapest edge with exactly one endpoint in $S$. Then there is a minimum spanning tree $T$ that contains $e$.

Proof (sketch). Let $S$ be as above and $e = uv$ a cheapest edge with $u \in S$ and $v \notin S$. Let $T'$ be an MST. If $e$ is in the tree, we are done. So assume $e$ is not in $T'$. Since $T$ is a spanning tree, there is a path from $u$ to $v$ in $T'$, and this path must leave $S$ at some point. So let $e' = u'v'$ be an edge in $T$ with $u' \in S$ and $v' \notin S$. Observe that $w(e') \geq w(e)$. Create $T = (T' \setminus e') \cup e$, the tree where we replace $e'$ with $e$.

1. $w(T) \leq w(T')$.
2. $T$ is spanning
3. $T$ is a tree.

To see why the last is true, observe that we replaced one edge with another, so the number of edges is the same as in $T'$, so we only need to show that it is connected. But this holds since $u'$ is connected to $v'$ via the (already existing) $u$-$u'$-path and $v$-$v'$-path, plus the edge $e$. It follows that $T$ is acyclic and therefore a tree.