Questions: Brooks' Theorem

Question 1

You have a connected graph G with maximum degree Δ = 5 that is neither a complete graph nor an odd cycle. What does Brooks' Theorem guarantee?

• A. The graph requires exactly 5 colors — no more, no less
• B. The graph can be properly colored with at most 5 colors
• C. The graph requires at most 6 colors, because the trivial greedy bound always applies
• D. The graph can always be 4-colored because Δ is only an upper bound

Answer: (B)

Brooks' Theorem gives an upper bound of Δ for all connected graphs except complete graphs and odd cycles. For this graph (Δ = 5, neither exception), at most 5 colors suffice. Option A is wrong — 'at most' does not mean 'exactly'; χ(G) might be 3 or 4. Option C applies the weaker trivial bound (Δ+1), which Brooks supersedes. Option D incorrectly extrapolates 'upper bound' to mean 'can always go lower.'

Question 2

Which of the following graphs requires Δ+1 colors according to Brooks' Theorem?

• A. A connected 4-regular graph that is not a complete graph and not an odd cycle
• B. The cycle graph C₇ (seven vertices arranged in a ring)
• C. A 3-regular bipartite graph
• D. A 5-regular graph that contains a triangle

Answer: (B)

C₇ is an odd cycle with maximum degree Δ = 2. By Brooks' Theorem, odd cycles are one of only two exception families requiring Δ+1 = 3 colors. You can 2-color any even cycle (alternating colors around the ring work out), but odd cycles force a color conflict at the wrap-around. Options A, C, and D all describe graphs that are not complete graphs or odd cycles, so they satisfy χ ≤ Δ.

Question 3

Brooks' Theorem says nearly every graph can be properly colored with exactly Δ colors.

• T. True
• F. False

Answer: False

The theorem gives an upper bound: χ(G) ≤ Δ for graphs that are not complete graphs or odd cycles. 'At most Δ' does not mean 'exactly Δ.' A bipartite graph with Δ = 5 only requires 2 colors; a tree with Δ = 10 only requires 2 colors. Brooks' Theorem rules out needing more than Δ colors (outside the two exception families) but says nothing about whether fewer might suffice.

Question 4

The complete graph K₅ has chromatic number 5, which equals Δ+1 for that graph.

• T. True
• F. False

Answer: True

K₅ has 5 vertices, each adjacent to all other 4, so Δ = 4. Since every pair of vertices is connected, each vertex needs a distinct color, giving χ(K₅) = 5 = Δ+1. This makes Kₙ one of the two families that cannot be colored with Δ colors — which is exactly why Brooks' Theorem carves them out as exceptions. The theorem's upper bound of Δ is tight: complete graphs prove you cannot improve it further.

Question 5

Why do odd cycles require Δ+1 colors, while even cycles only need Δ colors?

Model answer: An odd cycle has Δ = 2 but requires 3 colors. When you try to 2-color by alternating colors around the ring, the last vertex before closing the loop is adjacent to the first vertex — and because the cycle has an odd number of vertices, those two vertices end up with the same color, creating a conflict. Even cycles avoid this: with an even number of vertices, the alternating pattern closes perfectly and the first and last vertices have different colors, so 2 colors suffice.

This is the cleanest example of why Brooks' Theorem needs exceptions. Odd cycles are sparse (Δ = 2) yet require an extra color — purely due to parity, not density. The proof of Brooks' Theorem works by finding orderings that let greedy coloring succeed within Δ colors, but no such ordering exists for odd cycles. Even cycles (also Δ = 2) are bipartite, which is why 2 colors always work for them.