K₄
Δ = 3 but χ = 4
Complete graph: the exception.
Brooks' theorem: for a connected graph that is neither complete nor an odd cycle, , the maximum degree. The four colour theorem: every planar graph has .
This page is easier if you are comfortable with:
In general (colour greedily), and Brooks says the extra colour is needed only in two cases. The complete graph has and ; the odd cycle has and (its colourings are counted in the chromatic polynomial of a cycle). The even cycle has . The Petersen graph (3-regular, not complete) has , as Brooks allows.
is planar, so it shows the four colour theorem cannot be improved: some planar graphs need 4 colours. The planarity itself is characterised by Kuratowski's theorem, and planar graphs obey the edge bounds in planar graph bounds and Euler's formula.
Brooks' bound is useful in timetabling and register allocation, where the maximum degree is easy to compute. The edges at each vertex are counted by the handshaking lemma. Colourings of bipartite graphs are in bipartite graphs.
Brooks' theorem bounds the number of colours by the largest degree, with two known exceptions.
K4 and C5 are the exceptions where Δ + 1 colours are needed.
These examples are worked by hand, step by step, so you can compare your own working.
Find and for the complete graph .
The Petersen graph is 3-regular and not complete. What does Brooks give for ?
Find for , and compare .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
Δ = 3 but χ = 4
Complete graph: the exception.
Δ = 2 but χ = 3
Odd cycle: the other exception.
Δ = 3 and χ = 3
Brooks applies.
χ ≤ 4
Four colour theorem.
Greedy colouring gives χ ≤ Δ + 1. Brooks’ theorem sharpens this to χ ≤ Δ for connected graphs that are neither complete nor odd cycles. The four colour theorem says every planar graph has χ ≤ 4.
A graph has Δ = 5. Give the greedy bound on χ.
A connected graph with Δ = 5 is not complete or an odd cycle. Give Brooks’ bound.
Find χ(K₅) and compare with Δ.
Find Δ and χ for C₇.
χ(K₄) ≤ 3 ✗
χ(K₄) = 4 ✓
Complete graphs are the exception.
χ(C₅) ≤ 2 ✗
χ(C₅) = 3 ✓
Odd cycles are the exception.
every planar graph needs 4 ✗
at most 4 ✓
Many need fewer.
applying to disconnected graphs ✗
treat each component ✓
Brooks assumes connected.
Try each one on paper, then open the answer. Use the solver above to see the full working.
8
7
6
5
1
3
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
For connected graphs that are not complete or odd cycles, χ ≤ Δ.
Every planar graph has χ ≤ 4.
4.
χ ≤ Δ + 1.
chromatic polynomial of a cycle.
Kuratowski’s theorem.
More in Discrete maths and number theory and the formula sheets.