Minimum spanning tree containing edge with minimum weight

In my midterm exam of Graph Theory, there is the following problem:

Show that the minimum spanning tree of a weighted connected graph must have an edge with minimum weight in the graph.

I thought this problem was a trap. Some students may fail by asserting that by Kruskal Algorithm, we have it obvious, in fact, I think that such argument is wrong. Kruskal Algorithm is just one of the “generator” of Minimum Spanning Tree (MST) and thus it does not guarantee the completeness of necessary arguments.

Nah, apparently, the solution is not hard. Well, let w be the minimum weight, say it is the weight on edge e, and assume that any edge of an MST T have weight greater than w. Add the edge e to tree T and we have exactly one cycle as subgraph of T. Removing any edge from this cycle other than e, we will have another tree T' whose total weight is less than total weight of T, contradicting the minimality of T. Thus, any minimum spanning tree must have an edge with minimum weight.
Note that the wording can be dangerous here. If we say “any MST must contain minimum-weighted edges”, the statement is wrong. Well, let’s just consider uniform weighted graph and we may leave some (minimum-weighted) edges behind. So, the problem is almost trolling.
Advertisements

One Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s