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