11.11. Forests & Trees 351
(a)Recast this problem as a question about coloring the vertices of a particular
graph. Draw the graph and explain what the vertices, edges, and colors represent.
(b)Show a coloring of this graph using the fewest possible colors. What schedule
of recitations does this imply?
Problem 11.23.
This problem generalizes the result proved Theorem 11.7.3 that any graph with
maximum degree at mostwis.wC1/-colorable.
A simple graph,G, is said to havewidth,w, iff its vertices can be arranged in a
sequence such that each vertex is adjacent to at mostwvertices that precede it in
the sequence. If the degree of every vertex is at mostw, then the graph obviously
has width at mostw—just list the vertices in any order.
(a)Describe an example of a graph with 100 vertices, width 3, butaveragedegree
more than 5.Hint:Don’t get stuck on this; if you don’t see it after five minutes,
ask for a hint.
(b)Prove that every graph with width at mostwis.wC1/-colorable.(c)Prove that the average degree of a graph of widthwis at most2w.Exam Problems
Problem 11.24.
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:
Induction hypothesis:
P.n/WWD“LetGbe ann-vertex graph whose vertex degrees are allk. IfGalso
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.