Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

Does this help?  Write back if you'd like to talk about this some 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/