Associated Topics || Dr. Math Home || Search Dr. Math

### Proofs of the Two-Color Map Theorem

```Date: 03/19/2003 at 19:57:25
From: Alex
Subject: The two-color map theorem

How do you prove, using mathematical induction, the two-color map
theorem?

Two-color map theorem: Suppose a map is drawn using only lines that
extend to infinity in both directions; two colors are sufficient to
color the countries so that no pair of countries with a common border
have the same color.
```

```
Date: 03/21/2003 at 05:12:40
From: Doctor Jacques
Subject: Re: The two-color map theorem

Hi Alex,

I will give you two proofs. The first one does not really need
induction (although I will use it), but is valid under more general
conditions. The second one is based on induction, and much easier
(I'll only outline it), but requires some additional restrictions.

Proof 1
-------

As this problem is related to graph theory, we will use some related
definitions:

An intersection between lines is a node.

A section of line between two nodes is a branch. This is a section of
a border.

A country is a face.

We want to color all the faces black or white, in such a way that the
faces on either side of any branch have different colors.

We note first that the number of branches connected to any node is
even (we say that all nodes have even degree). Indeed, if you travel
along an infinite line, every time you encounter a node, you must
leave it along another branch.

The proof below relies solely on that fact, i.e. it is valid for any
map where all nodes have even degrees. You do not require the lines
to be infinite, and any line can cross itself.

In the following, we will consider paths connecting points in the
map. Such paths must obey certain rules:

* A path is a continuous curve.
* A path does not pass through any node.
* A path intersects branches only in isolated points : there is no
segment of non-zero length common to a path and a branch.
* A path cannot intersect itself (there are no figure 8's).

We will color the map using the following algorithm:

* Choose any face and color it black. Select one point A in the
interior of that face.
* For any other face, pick a point B in the interior of that face.
Draw a path from A to B. If the path crosses an even number of
branches, color the new face black, otherwise color it white.

Of course, for that algorithm to make sense, we must show that the
result does not depend on the particular path chosen to connect A and
B.

Consider two paths P1 and P2 from A to B. Assume that P1 crosses n1
branches, and that P2 crosses n2 branches. We must show that n1 and
n2 have the same parity, i.e. are both odd or both even.

Consider the closed path P3 from A to A, constructed by following P1
up to B and P2 (backwards) to return at A. This path crosses n1 + n2
branches. n1 and n2 will have the same parity if and only if n1 + n2
is even.

The conclusion is that we need to prove that any closed path P crosses
an even number of branches.

As P does not cross itself, it defines two regions: the inside and the
outside.

We can limit ourselves to considering branches connecting a node
inside P to a node outside P. Indeed, given a branch AB, whenever it
intersects the path P, we pass from the outside to the inside or
conversely. So, if A and B are both outside or both inside P, the
branch will cross P an even number of times; as we are only interested
in the parity of the number of crossings, we can ignore that branch.

Consider now a closed path P, and let n be the number of nodes inside
P. We will show, by induction on n, that P crosses an even number of
branches.

If n = 0, there are no branches connecting inside nodes to outside
nodes, and, by the remark above, the number of crossings is even.

Assume now that n > 1. If there are no branches connecting inside
nodes to outside nodes, we are done (this cannot happen with infinite
lines, but, as I said before, the theorem is also valid for any graph
where all the degrees are even). Otherwise, there is a branch joining
in interior node A to an exterior node B.

Assume that A has p branches going to exterior nodes (including B)
and q branches going to interior nodes. We know that p+q is even.

Deform the path P to a path P' by moving its intersection with AB
toward and past A, in such a way that A becomes an exterior node. As
P' encloses (n-1) nodes, it crosses an even number of branches, by
the induction hypothesis. Consider the difference in the number of
crossings of P and P' - call them c(P) and c(P'); c(P') is even.

Any of the p branches joining A to an exterior node now joins two
exterior nodes. Such branches were counted in c(P) and are no longer
counted in c(P').

Any of the q branches joining A to another interior node now joins an
exterior node (A) to an interior node. These were not counted in c
(P), but must now be counted in c(P').

All other branches keep their own status, since no other node was
moved.

To summarize, we have:

c(P') = c(P) - p + q

As c(P') is even, and p + q is even, this shows that c(P) is even, and
completes the proof.

Now, you don't really need induction to prove this - we could have
counted the branches connected to interior nodes directly, and a
little algebra would have yielded the desired result.

Proof 2
-------

You can also have a more "induction-like" (and simpler) proof, but you
have to add a restriction, namely that no line crosses itself (this
would be the case, for example, with straight lines). This implies
that any line partitions the plane into two regions. This proof can
non longer be used for any map where we only know that all nodes have
even degree.

In that case, you can use induction on the number of lines. The
general idea is as follows:

If there are no lines, there is a solution (with one color).

If there are n lines, remove one line. The remaining map has n-1 lines
and can be colored black and white (by induction). Add the new line,
and change the colors of all the coutries in one of the two regions
defined by the line.

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 01/13/2006 at 10:33:11
From: Tom
Subject: two color map proofs

I read your inductive proof of the 2-color theorem, in which you
alluded to a non-inductive proof.  I would really like to see it, or
at least get a reference to where it can be found.
```

```
Date: 01/15/2006 at 03:55:42
From: Doctor Jacques
Subject: Re: two color map proofs

Hi Tom,

To get a non-inductive proof, we modify the end of the first proof,
i.e., we keep it until the paragraph:

----
Consider now a closed path P, and let n be the number of nodes inside
P. We will show, by induction on n, that P crosses an even number of
branches.
----

Remember that the hypothesis is that each node has even degree, and,
as the first part of the proof shows, we must show that any closed
path crosses an even number of branches.

We can consider that each branch consists of two halves, where each
half is attached to one of the nodes connected by the branch. The
degree of a node is the number of "half-branches" attached to it.

As each node has even degree, by hypothesis, the total number of half-
branches attached to nodes inside P is even. Let h denote that number.

Those half-branches fall into two categories:

(a) Those that connect two nodes inside P. As each branch has two
halves, the number of such half-branches is even; each half of a
branch is included in the total h.

(b) Those that connect a node inside P to a node outside P. These
correspond to the branches that intersect P, the ones we are
interested in.

As h = (a) + (b), and both h and (a) are even, there are an even
number of branches of type (b), and this was what we wanted to show.
in fact, the non-inductive version is even simpler than the inductive
one...

Please feel free to write back if you want to discuss this further.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 01/15/2006 at 17:09:49
From: Tom
Subject: two color map proofs

First, thank you for your response!

I have since found a very sweet proof of the theorem "If every vertex
of a planar graph has even degree, it is 2-colorable."

Consider the dual G' of the given graph G.  Since every vertex of G
has even degree, every face of G' has an even number of edges.  By
coloring any vertex and then alternating the colors, we can 2-color
the vertices of G', and this coloring corresponds to a 2-coloring of
the faces of G.

What do you think?
```

```
Date: 01/16/2006 at 02:59:30
From: Doctor Jacques
Subject: Re: two color map proofs

Hi Tom,

Your proof is correct. (Note that the basic idea is the same - a
cycle in the dual graph is what I called a closed path in the
original graph.)

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/

```
Associated Topics:
College Discrete Math
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search