An edge set spans an edge if and are connected in .
An edge set is spanning if it spans every edge.
An edge set is acyclic and is a forest if it does not contain any cycles. In particular, between any pair of vertices connected by , there is a unique path between them in .
Let be connected. An edge set is a spanning tree if it is both spanning and a forest.
Combining the definition of spanning and forest, an edge set is a iff every pair of vertices is connected by a unique path in .
Let and be two spanning trees, and let be an edge in but not . Prove that there exists an edge such that and are both spanning trees. (Here "" denotes adding an edge and "" denotes deleting an edge.) (Such a pair and are sometimes called a mutually exchangeable pair.)
Let and be two spanning trees. Show that there exists a one-to-one mapping such that for every , the tree is a spanning tree. 1
Let be a spanning tree in a weighted graph. Prove that is the minimum weight spanning tree iff for every spanning tree with (that is, for every spanning tree differing in exactly one edge.) 2