5-color-theorem

4 min readMay 2, 2023

The 5-color theorem, also known as the five-color map theorem, is a mathematical theorem that states that any map on a two-dimensional surface can be colored using only five colors in such a way that no two adjacent regions have the same color. This theorem is one of the most famous and important results in graph theory and combinatorics, and has numerous applications in fields such as computer science, cartography, and topology.

History:

The five-color theorem was first proposed in the mid-19th century by Francis Guthrie, a student of Augustus De Morgan. Guthrie was trying to color a map of the counties of England, and noticed that he could do so using only four colors. He conjectured that this was always possible for any map, but was unable to prove it. Guthrie’s brother, Frederick, passed the problem on to his friend Arthur Cayley, a renowned mathematician, who also tried but failed to prove the conjecture.

In 1878, Alfred Kempe, a lawyer and amateur mathematician, claimed to have proved the conjecture by showing that every map could be reduced to a special type of graph called a planar graph, which could be colored using only four colors. Kempe’s proof was widely accepted for over a decade, until in 1890, Percy Heawood discovered a flaw in Kempe’s argument.

In 1890, Heawood proved that every map could be colored using only five colors, by introducing a new technique called discharging, which allowed him to reduce the problem to a finite number of cases. Since then, numerous other proofs of the five-color theorem have been discovered, each using different techniques and insights.

Statement and proof:

The statement of the five-color theorem is deceptively simple: any map on a two-dimensional surface can be colored using only five colors in such a way that no two adjacent regions have the same color. However, the proof of this theorem is highly nontrivial, and requires a deep understanding of graph theory and combinatorics.

One way to prove the five-color theorem is to use the concept of planar graphs, which are graphs that can be drawn on a plane without any edges crossing. Every map can be represented as a planar graph, with regions corresponding to vertices and borders corresponding to edges. It can be shown that every planar graph can be reduced to a simpler type of planar graph called a 5-reducible graph, which can be colored using only five colors. This is done using a technique called discharging, which involves redistributing colors from certain vertices to others.

Another way to prove the five-color theorem is to use the concept of Kempe chains, which are sequences of adjacent regions of the same color that divide the map into two parts. It can be shown that if there is a Kempe chain of a certain color, then the map can be recolored using one fewer color. By carefully analyzing the possible Kempe chains that can appear in a map, it can be shown that every map can be colored using only five colors.

Applications:

The five-color theorem has numerous applications in fields such as computer science, cartography, and topology. In computer science, it is used in algorithms for graph coloring, which are used in tasks such as scheduling, register allocation, and data compression. In cartography, it is used to minimize the number of colors needed to distinguish different regions on a map. In topology, it is used to study the properties of surfaces and their embeddings in higher-dimensional spaces.

Conclusion:

The five-color theorem is a fundamental result in graph theory and combinatorics, and is an example of how seemingly simple problems can have deep and unexpected solutions. Its importance extends far beyond the realm of mathematics.

Now lets test your understanding,

The minimum number of colors that is sufficient to vertex -color any planar graph is _____

[A] 3

[B] 5

[C] 4

[D] 2

Ans [C]

2. Consider a connected graph G in which vertices is equal to the number of edges, and every vertex has degree 2. What is the minimum number of colors required to edge-color G?

[A] 1

[B] 2

[C] 3

[4] 4

Ans [C]

3.Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-color G is

[A] 4

[B] 5

[C] 7

[D] 9

Ans [C]

4. Which is the following is an invalid type of a Graph?

a. Directed Graph

b. Null Graph

c. Undirected Graph

d. Proper Graph

Ans : [D]

References