The four-colour theorem: The basis for a hand-checkable proof

Abstract

The four-colour theorem is easily explained and requires no mathematical knowledge to grasp the concept, yet it took more than a century to prove it. The theorem states that the vertices of every planar graph can be coloured with four colours, such that neighbouring vertices do not have the same colour. In this thesis we have introduced the theorem. First we limited ourselves to undirected graphs made of triangles. Then we looked at smaller graphs called configurations, and found that we can prove the theorem by finding an unavoidable set of reducible configurations. We have detailed two ways to prove the reducibility of a configuration: D-reducibility, which looks only at the direct surroundings of the configuration, and Creducibility, which first tries to change the configuration by contracting some of its edges. Proving unavoidability is left as a future project. With the insight gained during this project we concluded that an increase in computing power will increase the number of reducible configurations that can be found. A recommendation is made for future work to assess the chance of checking unavoidability by hand, as a result of this increase in reducible configurations.