# Stuck on Kruskal's Algorithm Proof Using Induction

So I want to understand how induction proves that Kruskal's Algorithm is correct in terms of giving us a minimum spanning tree. I understand why the algorithm gives us a spanning tree, but I don't understand how it gives us a minimum.

So I was reading my lecture notes from class, and it tries to explain it using induction on the algorithm stage number. So the proof is as follows:

Let F$$_i$$ be the set of edges chosen at stage i of the algorithm. Let P$$_i$$ be the proposition: "There is some minimum spanning tree that contains F$$_i$$." Clearly any minimum spanning tree contains F$$_0$$ which is just the empty set of edges, so P$$_0$$ is true. Now suppose that P$$_i$$ is true. Then there is a minimum spanning tree T that contains F$$_i$$. Let e be the edge considered next by the Algorithm. If e is in T, then F$$_i$$ $$\cup$$ {e} $$\in$$ T, so P$$_{i+1}$$ is true. Now assume that e is not in T. Then F$$_i$$ $$\cup$$ {e} contains a cycle with e in it.

So P$$_{i+1}$$ cannot be true in this case since it's impossible to form a new tree that contains this cycle, so I don't see how induction holds. Can some please explain this to me so that it makes sense?

Thank you in advance.

• You have to prove that there is a minimum spanning tree containing the edges chosen so far. You haven't chosen a cycle yet. – saulspatz Mar 31 at 14:26

## 1 Answer

We have to prove that that there is some minimum spanning tree containing the edges chosen so far. The easy case is when $$e$$ is in $$T,$$ and we have to deal with the case when $$e$$ is not in $$T.$$ $$T\cup\{e\}$$ contains a cycle $$C,$$ and obviously $$e$$ is one of the edges of $$C.$$ No edge $$e'$$ of $$C$$ can have greater weight than that of $$e,$$ for then we could delete $$e'$$ and obtain a spanning tree of lesser weight than $$T.$$ $$e$$ cannot have been the last edge of $$C$$ to be chosen, for the algorithm never creates a cycle. Therefore, some edge $$e'$$ of $$C$$ was chosen after $$e,$$ and we must have $$w(e)=w(e').$$ Deleting $$e'$$ gives a spanning tree $$T'$$ of the same weight as $$T,$$ containing all edges chosen so far.