View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

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

        Thumbnail
        View/Open
        4CT_Scriptie_Final.pdf (402.6Kb)
        Publication date
        2019
        Author
        Bink, J.C.
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/32996
        Collections
        • Theses
        Utrecht university logo