Question

1) Professor Sabatier conjectures the following converse of Theorem 23.1. Let G=(V,E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a subset of E that is included in some minimum spanning tree for G, let (S,V−S) be any cut of G that respects A, and let (u,v) be a safe edge for A crossing (S,V−S). Then, (u,v) is a light edge for the cut. Show that the professor's conjecture is incorrect by giving a counterexample.

2) Let ee be a maximum-weight edge on some cycle of connected graph G=(V,E). Prove that there is a minimum spanning tree of G′=(V,E−{e}) that is also a minimum spanning tree of G. That is, there is a minimum spanning tree of G that does not include e.

Answer 1

2. Let T be a minimum spanning tree of G'. Then T is also a spanning tree of G since G' and G contain the same vertices.

Assume that T is not a minimum spanning tree.

The only difference between G and G' is the edge e. So if T is not a minimum spanning tree of G then there must be a tree T' in G that is a minimum spanning tree with weight less than T and containing the edge e.

But e is a maximum edge on a cycle. So remove the edge e from T' and add an edge (x,y) from the cycle that is not already in T' to make T''.

T'' must be a tree with weight less than T' since the edge (x,y) has weight less than e (since e is maximum).

But then T' is not a minimum spanning tree, which is a contradiction.