10.1.3. Colouring of planar graphs

One of the most famous problem in graph theory is the four colour problem: prove that every plane graph is 4-colourable. The weaker assertion is almost immediate consequence of Euler's formula:

Theorem 10.5.: Every plane graph is 5-colourable.

Let us suppose that the assertion is false, and let G be 6-colourable plane graph with minimal number of vertices. Then G has a vertex x of degree at most 5.

Put . Then H is 5-colourable, say with colours 1,2,3,4,5.

Each of these colours must be used to colour at least one neighbour-hood of x, otherwise the missing colour could be used to colour x, and so G would be 5-colourable.

So, we may assume that , and we denote the neighbours by , and we colour .

Denote by the subgraph of H spanned by the vertices of colour i and j:

 

Suppose first that and belong to distinct components of . Interchanging the colours 1 and 3 in the component of we obtain another colouring of H.

However, in this 5-colouring both and get colour 3, so 1 is not used to colour any of the vertices .

 

So, x is colourable with the colour 1, which is a contradiction.

So, we can suppose that and belong to the same component of . Then, there is an path in H whose vertices are coloured 1 and 3.

Similarly, it is also true that and are in the same component and they can be coloured by 2 and 4, and there exists an path in H.

 

Is this possible?

The cycle of G separates from but cannot meet this cycle.

So, G is not a planar graph, which contradicts our assumption.

Let .

The consequence of the 5-colour theorem: .

  • The original form of the four colour problem was posed by: Francis Guthrie in 1852: show that every plane map can be coloured with four colours.
  • His teacher, de Morgan, circulated the problem among his colleagues, but the problem was first made popular in 1878 by Caley, who mentioned it before the Royal Society.
  • The first ″proofs″ were given by Kempe (1879) and Tait (1880).
  • Heawood's refutation of Kempe's proof was published in 1891. He modified the proof to obtain the five colour problem.
  • Petersen in 1890 proved that Kempe's proof contained false assumptions: He proved that the four colour problem is equivalent to the conjecture that every cubic graph has edge chromatic number three.
  • Birkhoff's introduction of the chromatic polynomial at the beginning of the 20. century contributed to the solution.
  • During the 20. century a lot of works were made by various authors giving lower bounds on the order of a possible counterexample.
  • In 1943 Hadwiger made a deep conjecture containing the four colour problem as a special case: if then G is contractible to .
  • The problem was at last solved by Appel and Haken in 1976 using fast electronic computer and considering more than 1900 reducible configurations to complete the proof.