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 be the minimum weight, say it is the weight on edge , and assume that any edge of an MST have weight greater than . Add the edge to tree and we have exactly one cycle as subgraph of . Removing any edge from this cycle other than , we will have another tree whose total weight is less than total weight of , contradicting the minimality of . 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.

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

Finally, a mathematical problem I can really understand 😀 Nice, Ja!