Four-Color Map Theorem

Definition

The Four-Color Map Theorem states that any map in a plane can be colored using no more than four colors, such that no two adjacent regions share the same color. It is a significant result in graph theory and combinatorics, particularly concerning planar graphs.

5 Must Know Facts For Your Next Test

1. The theorem was first proven in 1976 by Kenneth Appel and Wolfgang Haken, using computer assistance.
2. A region or country in the map corresponds to a vertex in graph theory, with edges representing shared borders.
3. The theorem applies only to planar graphs, which can be drawn on a plane without edges crossing.
4. It took over a century from its conjecture to its proof, making it one of the longest-standing open problems in mathematics.
5. The proof of the theorem relies heavily on computational verification, checking many individual cases.

Review Questions

• What does the Four-Color Map Theorem state about coloring maps?
• Who were the mathematicians that proved the Four-Color Map Theorem using computer assistance?
• How does the Four-Color Map Theorem relate to planar graphs?

Related terms

Planar Graph: A graph that can be drawn on a plane without any edges crossing.

Vertex Coloring: An assignment of colors to vertices of a graph so that no two adjacent vertices share the same color.

Graph Theory: A field of mathematics focused on studying graphs, which are structures made up of vertices connected by edges.