| dc.description.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. | |
