Search for question
Question

Problem 2

Sometimes it is essential to identify a minimum-weight spanning tree in a connected

graph. For

example, it might be the goal to reduce the operational costs of a transportation

system while

maintaining connectivity between all the stops in the system. It can seem a little

counter-intuitive,

but in certain cases, a minimum-weight spanning tree must have the maximum

weight edge. The

following tasks guide you to explore a relationship between cut edges, the maximum-

weight edge

in a connected simple graph, and minimum-weight spanning trees for that graph.

Let G be a connected, simple graph, I be a spanning tree of G, and e be an edge of G.

(a) Prove that if e is not on a cycle in G, then e is an edge of T. (You might consider

using

contradiction to verify this statement.)

(b) Prove that if e is on a cycle in G, and e is in T, then there is an edge f* e such

that I-e + f

is also a spanning tree.

(c) Suppose G is edge-weighted (i.e. each edge has had some numeric value assigned

to it),

the weight of e is larger than the weights of all the other edges, e is on a cycle in G,

and e

is an edge of T. Conclude that T is not a minimum weight spanning tree of G.

(Consider

comparing the total weights of T and T - e + f in your proof.)