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

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.

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. Oct 5 at 16:37
• Do you've a good reason to discourage it? It can be helpful to others who want to see similar proofs. Oct 6 at 11:30
• @achhainsan I have literally added links with explainations. Oct 6 at 12:55
• Please do not delete your question after receiving an answer. This is often considered impolite. Part of our purpose here is to build up an archive of high-quality questions and answers that will be useful to others -- not just to you -- and answerers may be writing their answer on the assumption that it will help not only you but others.
– D.W.
Oct 13 at 19:05

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.