a spanning tree of a connected graph is a subgraph that is a tree which includes all of the vertices of the graph
given is an undirected non-negatively weighted graph. let be a spanning tree, then:
let be an spanning tree of and let . upon the removal of from we get a cut (in ) and upon the addition of any crossing edge to (in place of the one we removed) we get another spanning tree for .
let be a spanning tree of and let , upon the addition of to we get a single cycle and upon the removal of any of this cycle's edges we get another spanning tree
spans and so it contains a single path from to . let the graph we get by adding a new edge to . in the graph there exists a cycle that contains and the edges from the path . if we were to drop from one of the edges of the cycle, we would get a graph such that is connected, contains no cycles and contains all the vertices of , which means is a spanning tree of .