College of Computer & Information Science Fall 2006 Northeastern University Handout 11 CSU690: Algorithms and Data 17 October 2006

Review 4 (Tuesday, October 17)

For each of the following three statements, decide whether the statement is true. If it is true, then provide a proof; otherwise, give a counterexample.

1. Let G be an undirected connected graph with nonnegative weights on edges. Let T be a minimum spanning tree of G. Then, for any vertex u and v, the unique path between u and v in T is the shortest path between u and v in G.

2. Let G be an undirected connected graph with weights on edges, and let T be an MST of G. Suppose we add W to the weight of every edge. Then, T remains an MST of the graph with the new weights.

3. Let G be an undirected connected graph with weight w(e) on every edge e. Suppose e^{∗} is a lightest edge in G; that is, w(e^{∗}) ≤ w(e) for all edges e. Then, there is an MST T of G that contains e^{∗}.