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.
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.