Mathematics for Computer Science

11.11. References 457

supposeGnC 1 has a vertex,v, of degree strictly less thank. Now we only

need to prove thatGnC 1 isk-colorable.

To do this, first remove the vertexvto produce a graph,Gn, withnvertices.

Letube a vertex that is adjacent tovinGnC 1. Removingvreduces the

degree ofuby 1. So inGn, vertexuhas degree strictly less thank. Since no

edges were added, the vertex degrees ofGnremaink. SoGnsatisfies the

conditions of the induction hypothesis,P.n/, and so we conclude thatGnis

k-colorable.

Now ak-coloring ofGngives a coloring of all the vertices ofGnC 1 , except for

v. Sincevhas degree less thank, there will be fewer thankcolors assigned

to the nodes adjacent tov. So among thekpossible colors, there will be a

color not used to color these adjacent nodes, and this color can be assigned to

vto form ak-coloring ofGnC 1.



(c)With a slightly strengthened condition, the preceding proof of the False Claim
could be revised into a sound proof of the following Claim:
Claim.LetGbe a graph whose vertex degrees are allk. Ifhstatement inserted from belowi
has a vertex of degree strictly less thank, thenGisk-colorable.

Circle each of the statements below that could be inserted to make the proof correct.

Gis connected and

Ghas no vertex of degree zero and

Gdoes not contain a complete graph onkvertices and

every connected component ofG

some connected component ofG

Problem 11.42.
In the graph shown in Figure 11.32, the vertices connected in the triangle on the left
are calledcolor-vertices; since they form a triangle, they are forced to have different
colors in any coloring of the graph. The colors assigned to the color-vertices will
be calledT;FandN. The dotted lines indicate edges to the color-vertexN.

(a)Explain why for any assignment ofdifferenttruth-colors toPandQ, there is
a unique 3-coloring of the graph.

(b)Prove that in any 3-coloring of the whole graph, the vertex labeledPXORQ
is colored with theXORof the colors of verticesPandQ.