Exercise 1686Combinatorics › Graph theoryL1Added 3 Nov 2026

The four-color theorem (statement)

#four-color#planar#chromatic

Statement

State the four-color theorem and give an example of a planar graph needing $4$ colors.

Hint

A planar graph needs at most $4$ colors; some need exactly $4$ .

Show solutionHide solution

Theorem. Every planar graph is $4$ -colorable (i.e. $\chi(G)\le4$ ).

Example. $K_4$ (tetrahedron) is planar and needs $\chi=4$ .

Tightness. Some planar graphs (like the $K_4$ ) require all four colors.

Conclusion. The bound is tight and is one of the most famous theorems in graph theory.