Mathematics for Computer Science

11.11. References 433

edges by definition are not edges ofF, the graphMCegcontainsFCe. We

claim thatMCegis an MST, which proves the claim thateextendsF.

To prove this claim, note thatMCeis a connected, spanning subgraph, andgis

on a cycle ofMCe, so by Lemma 11.9.6, removinggwon’t disconnect anything.

Therefore,MCegis still a connected, spanning subgraph. Moreover,MCeg

has the same number of edges asM, so Lemma 11.10.4 implies that it must be a

spanning tree. Finally, sinceeis minimum weight among gray edges,

w.MCeg/Dw.M/Cw.e/w.g/w.M/:

This means thatMCegis a spanning tree whose weight is at most that of an

MST, which implies thatMCegis also an MST. 

Another interesting fact falls out of the proof of Lemma 11.10.11:

Corollary 11.10.12.If all edges in a weighted graph have distinct weights, then

the graph has auniqueMST.

The proof of Corollary 11.10.12 is left to Problem 11.70.

11.11 References

[7], [12], [21], [24], [26]

Problems for Section 11.2

Class Problems

Problem 11.1. (a)Prove that in every simple graph, there are an even number of

vertices of odd degree.

(b)Conclude that at a party where some people shake hands, the number of people

who shake hands an odd number of times is an even number.

(c)Call a sequence of people at the party ahandshake sequenceif each person in

the sequence has shaken hands with the next person, if any, in the sequence.

Suppose George was at the party and has shaken hands with an odd number of

people. Explain why, starting with George, there must be a handshake sequence

ending with a different person who has shaken an odd number of hands.