*Due Wednesday, February 19 at 5:00 PM. Please refer to the homework policy here.*

Let be an undirected graph.

- 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}