Student name:________________________ Preceptor: __________________________
Grade: ____________________ Grader: ______________________
Consider a graph G= (V,E), where each edge is assigned a distinct real number as a cost.
1. Give a rigorous proof that along any cycle of G the most expensive edge cannot be in the MST of G.
2. The most efficient MST algorithms are based on a certain contractibility theorem, which you should prove:
Consider the graph G(W) induced by a subset W
of V. (This is the graph with vertex set W, whose edge set
consists of all the edges of E with both endpoints in W.)
We say that G(W) is contractible if, given any two
edges e, f of E, both of which have exactly one
endpoint in W, there exists a path P in G(W) joining
e and f such that no edge of P is more expensive than both e and f.
Prove that if G(W) is contractible, then
the edges of G(W) that happen to belong to
MST(G) form a subtree (ie, a connected graph).