Homework 6 - Due 4/21

1.  Problem 22-2, page 558.  You can read about the description of G_pi and E_pi on page 540.  What it refers to is the *forest* that the DFS found within the graph G.

2.  We proved in class that if G is an undirected, weighted graph with all weights distinct, then there is a unique minimum weight spanning tree of G.  Give an example showng that there may be a tie for the spanning tree of G with the second-lowest weight.

3.  Suppose that G is an undirected, weighted graph on n vertices, with all weights distinct.  Prove that if T is a minimum weight spanning tree of G, and T' is a spanning tree of G with the next-smallest possible weight.  Show that T-T' and T'-T each consist of a single edge.  That is, show that they have n - 2 of their n - 1 edges in common.