graphs proof of correctness proving kruskal' algorithm correctly finds minimum weighted spanning tree can be done with proof by contradiction the proof starts by recognizing that there must be | |- edges in the spanning tree then we assume that some other edge would be better to add to the spanning tree than the edges picked by the algorithm the new edge must be part of one and only one cycle if adding the new edge formed two or more cycles then there would have had to be cycle in the tree before adding the new edge one of the edges in this newly formed cycle must be deleted from the minimum weighted spanning tree to once again make it tree andthe deleted edge must have weight greater than the newly added edge this is only possible if the new edge and the deleted old edge have exactly the same weight since all the old edges in the cycle were chosen before the new edge and the new edge was skipped because choosing it would have formed cycle so dropping the same weighted edge of the older edges will result in minimum weighted spanning tree with the same weight thereforethe new spanning tree has the same weight as the original spanning tree and that contradicts our assumption that better edge could be found kruskal' complexity analysis the complexity of kruskal' algorithm depends on sorting the list of edges and then forming the union of sets as the algorithm proceeds sorting listas was shown in chap when we looked at the complexity of quicksortis (| |log| |sorting the list is one half of kruskal' algorithm the other half is choosing the correct edges recall that each edge starts in set by itself and that an edge belongs to the minimum weighted spanning tree if the two endpoint vertices are in separate sets if sothen the union is formed for the two sets containing the endpoints and this union of two sets replaces the previous two sets going forward three operations are required to implement this part of the algorithm first we must discover the set for each endpoint of the edge being considered for addition to the spanning tree then the two sets must be compared for equality finallythe union of the two sets must be formed and any necessary updates must be performed so the two endpoint vertices now refer to the union of the two sets instead of their original sets one way to implement these operations would be to create list of sets where each position in the list corresponded to one vertex in the graph the vertices are conveniently numbered - in the example in the text but vertices can be reassigned integer identifiers starting at otherwise the set corresponding to vertex can be determined in ( time since indexed lookup in list is constant time operation this copy belongs to 'acha