Mathematics for Computer Science

Chapter 11 Simple Graphs470

edge among the edges with one endpoint in the tree. Continue as long as there is
no edge between two trees, then go back to applying the general gray edge method
until the parallel trees merge to form a spanning tree ofG. (This is 6.042’s parallel
MST algorithm.)

(d)Verify that you got the same MST each time.

Problem 11.68.
In this problem you will prove:

Theorem.A graphGis 2-colorable iff it contains no odd length closed walk.

As usual with “iff” assertions, the proof splits into two proofs: part (a) asks you
to prove that the left side of the “iff” implies the right side. The other problem parts
prove that the right side implies the left.

(a)Assume the left side and prove the right side. Three to five sentences should
suffice.

(b)Now assume the right side. As a first step toward proving the left side, explain
why we can focus on a single connected componentHwithinG.

(c)As a second step, explain how to 2-color any tree.

(d)Choose any 2-coloring of a spanning tree,T, ofH. Prove thatH is 2-
colorable by showing that any edgenotinT must also connect different-colored
vertices.

Homework Problems

Problem 11.69.
LetDD.d 1 ;d 2 ;:::;dn/be a sequence of positive integers wheren 2.

(a)SupposeDis a list of the degrees of vertices of somen-vertex treeT, that is,
diis the degree of theith vertex ofT. Explain why

Xn

iD 1

diD2.n1/ (11.9)

(b)Prove conversely that ifDsatisfies equation (11.9), thenDis a list of the
degrees of the vertices of somen-vertex tree.Hint:Induction.