linguistic:translation, structural:summarization
Spanning tree

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