Mathematics for Computer Science

Chapter 11 Simple Graphs456

[h]

Figure 11.31 Replacing an edge-crossing with a planar gadget.

Hint:Only two colorings are needed, one whereuandvare the same color and
another where they are not the same color.

(b)Prove that the graph in Figure 11.30 satisfies condition (2).

Hint:The colorings for part (a) are almost completely forced by the coloring ofu
andv.

Exam Problems

Problem 11.41.

False Claim.LetGbe a graph whose vertex degrees are allk. IfGhas a vertex
of degree strictly less thank, thenGisk-colorable.

(a)Give a counterexample to the False Claim whenkD 2.

(b)Underline the exact sentence or part of a sentence that is the first unjustified
step in the following bogus proof of the False Claim.

Bogus proof.Proof by induction on the numbernof vertices:

The induction hypothesis,P.n/is:

LetGbe ann-vertex graph whose vertex degrees are allk. IfG

also has a vertex of degree strictly less thank, thenGisk-colorable.

Base case: (nD 1 )Ghas one vertex, the degree of which is 0. SinceGis

1-colorable,P.1/holds.

Inductive step: We may assumeP.n/. To proveP.nC1/, letGnC 1 be

a graph withnC 1 vertices whose vertex degrees are allkor less. Also,