Homework 8

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

Some useful definitions and facts

Let be an undirected graph.


  1. 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.)
  2. 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
  3. 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


1 Hint: induction on , and use problem 1
2 Hint: use problem 2