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.)