Editing Kruskal's algorithm (section)

== Proof of correctness ==

The proof consists of two parts. First, it is proved that the algorithm produces a [[spanning tree]]. Second, it is proved that the constructed spanning tree is of minimal weight.

===Spanning tree===
Let <math>G</math> be a connected, weighted graph and let <math>Y</math> be the subgraph of <math>G</math> produced by the algorithm. <math>Y</math> cannot have a cycle, as by definition an edge is not added if it results in a cycle. <math>Y</math> cannot be disconnected, since the first encountered edge that joins two components of <math>Y</math> would have been added by the algorithm. Thus, <math>Y</math> is a spanning tree of <math>G</math>.

===Minimality===

We show that the following proposition '''''P''''' is true by [[Mathematical induction|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''. The cycle ''C'' contains edges which do not belong to  ''F'' + ''e'', 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'', since ''f'' belongs to ''T'' + ''e'' but not ''F'' + ''e''. By  '''''P''''', ''f'' has not been considered by the algorithm. ''f'' must therefore have a weight at least as large as ''e''. Then ''T'' &minus; ''f'' + ''e'' is a tree, and it has the same or less weight as ''T''. However since ''T'' is a minimum spanning tree then ''T'' &minus; ''f'' + ''e'' has the same weight as ''T'', otherwise we get a contradiction and ''T'' would not be a minimum spanning tree. So ''T'' &minus; ''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.