Let be a connected, weighted graph and let be the subgraph of produced by the algorithm. cannot have a cycle, being within one subtree and not between two different trees. cannot be disconnected, since the first encountered edge that joins two components of would have been added by the algorithm. Thus, is a spanning tree of .