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 t