The five color theorem is a result from
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
that given a plane separated into regions, such as a
political map
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Althoug ...
of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.
The five color theorem is implied by the stronger
four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
, but is considerably easier to prove. It was based on a failed attempt at the four color proof by
Alfred Kempe
Sir Alfred Bray Kempe FRS (6 July 1849 – 21 April 1922) was a mathematician best known for his work on linkages and the four colour theorem.
Biography
Kempe was the son of the Rector of St James's Church, Piccadilly, the Rev. John Edward K ...
in 1879.
Percy John Heawood
Percy John Heawood (8 September 1861 – 24 January 1955) was a British mathematician, who concentrated on graph colouring.
Life
He was the son of the Rev. John Richard Heawood of Newport, Shropshire, and his wife Emily Heath, daughter of th ...
found an error 11 years later, and proved the five color theorem based on Kempe's work.
Outline of the proof by contradiction
First of all, one associates a simple planar
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discr ...
to the given map, namely one puts a
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
in each region of the map, then connects two vertices with an
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
if and only if the corresponding regions share a common border. The problem is then translated into a graph coloring problem: one has to paint the vertices of the graph so that no edge has endpoints of the same color.
Because
is a simple
planar
Planar is an adjective meaning "relating to a plane (geometry)".
Planar may also refer to:
Science and technology
* Planar (computer graphics), computer graphics pixel information from several bitplanes
* Planar (transmission line technologies), ...
, i.e. it may be embedded in the plane without intersecting edges, and it does not have two vertices sharing more than one edge, and it doesn't have loops, then it can be shown (using the
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space' ...
of the plane) that it must have a vertex shared by at most five edges. (Note: This is the only place where the five-color condition is used in the proof. If this technique is used to prove the four-color theorem, it will fail on this step. In fact, an
icosahedral graph
In geometry, a regular icosahedron ( or ) is a convex polyhedron with 20 faces, 30 edges and 12 vertices. It is one of the five Platonic solids, and the one with the most faces.
It has five equilateral triangular faces meeting at each vertex. It ...
is 5-regular and planar, and thus does not have a vertex shared by at most four edges.) Find such a vertex, and call it
.
Now remove
from
. The graph
obtained this way has one fewer vertex than
, so we can assume by
induction that it can be colored with only five colors. If the coloring did not use all five colors on the five neighboring vertices of
, it can be colored in
with a color not used by the neighbors. So now look at those five vertices
,
,
,
,
that were adjacent to
in cyclic order (which depends on how we write G). So we can assume that
,
,
,
,
are colored with colors 1, 2, 3, 4, 5 respectively.
Now consider the subgraph
of
consisting of the vertices that are colored with colors 1 and 3 only and the edges connecting them. To be clear, each edge connects a color 1 vertex to a color 3 vertex (this is called a
Kempe chain Kempe may refer to:
* Kempe baronets, a title in the Baronetage of England
* Kempe chain, part of the four-colour theorem
* Kempe Fjord, King Christian X Land, Greenland
* Kempe Glacier, Antarctica
* Kempe Hill, former name of Camp Hill, West ...
). If
and
lie in different connected components of
, we can swap the 1 and 3 colors on the component containing
without affecting the coloring of the rest of
. This frees color 1 for
completing the task. If on the contrary
and
lie in the same connected component of
, we can find a path in
joining them that consists of only color 1 and 3 vertices.
Now turn to the subgraph
of
consisting of the vertices that are colored with colors 2 and 4 only and the edges connecting them, and apply the same arguments as before. Then either we are able to reverse the 2-4 coloration on the subgraph of
containing
and paint
color 2, or we can connect
and
with a path that consists of only color 2 and 4 vertices. Such a path would intersect the 1-3 colored path we constructed before since
through
were in cyclic order. This is clearly absurd as it contradicts the planarity of the graph.
So
can in fact be five-colored, contrary to the initial presumption.
Linear time five-coloring algorithm
In 1996, Robertson, Sanders, Seymour, and Thomas described a quadratic four-coloring algorithm in their "Efficiently four-coloring planar graphs".
[.] In the same paper they briefly describe a linear-time five-coloring algorithm, which is
asymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly e ...
. The algorithm as described here operates on multigraphs and relies on the ability to have multiple copies of edges between a single pair of vertices. It is based on
Wernicke's theorem, which states the following:
:Wernicke's theorem: Assume G is planar, nonempty, has no faces bounded by two edges, and has minimum
degree 5. Then G has a vertex of degree 5 which is adjacent to a vertex of degree at most 6.
We will use a representation of the graph in which each vertex maintains a circular linked list of adjacent vertices, in clockwise planar order.
In concept, the algorithm is recursive, reducing the graph to a smaller graph with one less vertex, five-coloring that graph, and then using that coloring to determine a coloring for the larger graph in constant time. In practice, rather than maintain an explicit graph representation for each reduced graph, we will remove vertices from the graph as we go, adding them to a stack, then color them as we pop them back off the stack at the end. We will maintain three stacks:
* S
4: Contains all remaining vertices with either degree at most four, or degree five and at most four distinct adjacent vertices (due to multiple edges).
* S
5: Contains all remaining vertices that have degree five, five distinct adjacent vertices, and at least one adjacent vertex with degree at most six.
* S
d: Contains all vertices deleted from the graph so far, in the order that they were deleted.
The algorithm works as follows:
# In the first step, we collapse all multiple edges to single edges, so that the graph is simple. Next, we iterate over the vertices of the graph, pushing any vertex matching the conditions for S
4 or S
5 onto the appropriate stack.
# Next, as long as S
4 is non-empty, we pop ''v'' from S
4 and delete ''v'' from the graph, pushing it onto S
d, along with a list of its neighbors at this point in time. We check each former neighbor of ''v'', pushing it onto S
4 or S
5 if it now meets the necessary conditions.
# When S
4 becomes empty, we know that our graph has minimum degree five. If the graph is empty, we go to the final step 5 below. Otherwise, Wernicke's Theorem tells us that S
5 is nonempty. Pop ''v'' off S
5, delete it from the graph, and let ''v''
1, ''v''
2, ''v''
3, ''v''
4, ''v''
5 be the former neighbors of ''v'' in clockwise planar order, where ''v''
1 is the neighbor of degree at most 6. We check if ''v''
1 is adjacent to ''v''
3 (which we can do in constant time due to the degree of ''v''
1). There are two cases:
## If ''v''
1 is not adjacent to ''v''
3, we can merge these two vertices into a single vertex. To do this, we remove ''v'' from both circular adjacency lists, and then splice the two lists together into one list at the point where ''v'' was formerly found. Provided that ''v'' maintains a reference to its position in each list, this can be done in constant time. It's possible that this might create faces bounded by two edges at the two points where the lists are spliced together; we delete one edge from any such faces. After doing this, we push ''v''
3 onto S
d, along with a note that ''v''
1 is the vertex that it was merged with. Any vertices affected by the merge are added or removed from the stacks as appropriate.
## Otherwise, ''v''
2 lies inside the face outlined by ''v'', ''v''
1, and ''v''
3. Consequently, ''v''
2 cannot be adjacent to ''v''
4, which lies outside this face. We merge ''v''
2 and ''v''
4 in the same manner as ''v''
1 and ''v''
3 above.
# Go to step 2.
# At this point S
4, S
5, and the graph are empty. We pop vertices off S
d. If the vertex were merged with another vertex in step 3, the vertex that it was merged with will already have been colored, and we assign it the same color. This is valid because we only merged vertices that were not adjacent in the original graph. If we had removed it in step 2 because it had at most 4 adjacent vertices, all of its neighbors at the time of its removal will have already been colored, and we can simply assign it a color that none of its neighbors is using.
See also
*
Four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
References
Further reading
*{{Citation, last=Heawood , first=P. J. , title=Map-Colour Theorems , periodical= Quarterly Journal of Mathematics, Oxford , volume= 24 , year = 1890 , pages = 332–338 , authorlink=Percy John Heawood
Graph coloring
Theorems in graph theory