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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.