Brooks and four-colour Theorems Explained with Worked Examples

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 .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Brooks and four-colour theorems means

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.

What is it used for?

Brooks' theorem bounds the number of colours by the largest degree, with two known exceptions.

How to use brooks and four-colour theorems

  1. Compute the maximum degree .
  2. Check whether the graph is complete or an odd cycle.
  3. If not, ; otherwise .
  4. If the graph is planar, also .

Graph

Chromatic numbers: K4 = 4, Petersen = 3, C5 = 3, C6 = 2K4: 4Petersen: 3C5: 3C6: 200.511.522.533.544.5501234Chromatic numbers: K4 = 4, Petersen = 3, C5 = 3, C6 = 2graphyGraph with x from 0 to 5 and y from 0 to 4.8. Shows bars (4); point K4: 4 at (1, 4); point Petersen: 3 at (2, 3); point C5: 3 at (3, 3); point C6: 2 at (4, 2).

K4 and C5 are the exceptions where Δ + 1 colours are needed.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: K₄

Find and for the complete graph .

Worked example
Answer
χ=4=Δ+1\chi=4=\Delta+1
  1. Δ
  2. χ (all vertices adjacent)

Example 2: Petersen graph

The Petersen graph is 3-regular and not complete. What does Brooks give for ?

Worked example
Answer
33
  1. Bound
  2. Actual value

Example 3: odd cycle

Find for , and compare .

Worked example
Answer
33
  1. Δ
  2. χ

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

K₄

Δ = 3 but χ = 4

Complete graph: the exception.

C₅

Δ = 2 but χ = 3

Odd cycle: the other exception.

Petersen graph

Δ = 3 and χ = 3

Brooks applies.

Planar graphs

χ ≤ 4

Four colour theorem.

Word problems

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.

Greedy bound

A graph has Δ = 5. Give the greedy bound on χ.

  1. Δ + 1
  2. Check: ✓6.

Brooks bound

A connected graph with Δ = 5 is not complete or an odd cycle. Give Brooks’ bound.

  1. χ ≤ Δ
  2. Check: ✓5.

An exception Higher

Find χ(K₅) and compare with Δ.

  1. Δ(K₅)4
  2. χ(K₅)5
  3. Check: χ = Δ + 1 ✓5.

Odd cycle Higher

Find Δ and χ for C₇.

  1. Δ2
  2. χ3
  3. Check: χ = Δ + 1 ✓Δ = 2, χ = 3.

Common mistakes

Applying Brooks to complete graphs

χ(K₄) ≤ 3 ✗

χ(K₄) = 4 ✓

Complete graphs are the exception.

Applying Brooks to odd cycles

χ(C₅) ≤ 2 ✗

χ(C₅) = 3 ✓

Odd cycles are the exception.

Four colours always needed

every planar graph needs 4 ✗

at most 4 ✓

Many need fewer.

Ignoring connectivity

applying to disconnected graphs ✗

treat each component ✓

Brooks assumes connected.

Exam tips

  1. χ ≤ Δ + 1 always.
  2. χ ≤ Δ apart from K_n and odd cycles.
  3. Planar: χ ≤ 4.
  4. Check the exceptions first.
  5. Components separately.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Greedy bound when Δ = 7 Foundation

8

2. Brooks bound when Δ = 7 Foundation

7

3. χ(K₆) Foundation

6

4. Δ(K₆) Higher

5

5. Greedy bound minus Brooks bound Higher

1

6. χ(C₉) Higher

3

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Chromatic number (χ)
Fewest colours for a proper colouring.
Maximum degree (Δ)
Largest vertex degree.
Brooks’ theorem
χ ≤ Δ except K_n and odd cycles.
Four colour theorem
Planar graphs are 4-colourable.
Planar graph
Drawable without crossings.
Greedy colouring
Colour vertices in turn.

Frequently asked questions

What does Brooks’ theorem say?

For connected graphs that are not complete or odd cycles, χ ≤ Δ.

What is the four colour theorem?

Every planar graph has χ ≤ 4.

What is χ(K₄)?

4.

What is the greedy bound?

χ ≤ Δ + 1.

Which page covers cycle colourings?

chromatic polynomial of a cycle.

Which page covers Kuratowski?

Kuratowski’s theorem.

More in Discrete maths and number theory and the formula sheets.