Software Tools for Exploring a Potential Alternative Proof of the Four-Color Theorem

Location

CSU

Student's Major

Computer Information Science

Student's College

Science, Engineering and Technology

Mentor's Name

David Haglin

Mentor's Department

Computer Information Science

Mentor's College

Science, Engineering and Technology

Description

The Four Color Theorem is often cited in mathematical texts as an example of a problem which is easy to state and understand, but immensely difficult to prove. The theorem states that the most colors required to color any planar map, such that no two adjacent regions are the same color, is four. Posed in 1852 by graduate student Francis Guthrie, it was finally solved in 1976 by Kenneth Appel and Wolfgang Haken through the extensive use of a computer verifying hundreds of possible subcases. Is there a shorter, more elegant way to prove this theorem? It is the purpose of this project to explore that tantalizing possibility. A proposed algorithm for four-coloring a planar mapping can be shown to work for relatively small graphs that can be processed by hand. Designing a software implementation of this algorithm would help expand the size and variety of maps the algorithm has worked on, provide insight for improving the algorithm, and potentially lead to the publication of a far shorter proof for the Four Color Theorem.

This document is currently not available here.

Share

COinS
 

Software Tools for Exploring a Potential Alternative Proof of the Four-Color Theorem

CSU

The Four Color Theorem is often cited in mathematical texts as an example of a problem which is easy to state and understand, but immensely difficult to prove. The theorem states that the most colors required to color any planar map, such that no two adjacent regions are the same color, is four. Posed in 1852 by graduate student Francis Guthrie, it was finally solved in 1976 by Kenneth Appel and Wolfgang Haken through the extensive use of a computer verifying hundreds of possible subcases. Is there a shorter, more elegant way to prove this theorem? It is the purpose of this project to explore that tantalizing possibility. A proposed algorithm for four-coloring a planar mapping can be shown to work for relatively small graphs that can be processed by hand. Designing a software implementation of this algorithm would help expand the size and variety of maps the algorithm has worked on, provide insight for improving the algorithm, and potentially lead to the publication of a far shorter proof for the Four Color Theorem.