Fun Fact - The Four Color Theorem

The four color theorem states that the regions of any map can be colored using four colors, such that adjacent regions never have the same color. If Florida is yellow then Georgia and Alabama cannot be yellow, perhaps they are red and blue respectively. South Carolina could be yellow however, since it does not touch Florida. Color a few maps and you'll become convinced that 4 colors are enough, but the proof is notoriously difficult, requiring a computer to verify thousands of cases.

First, a few rules. Regions are well behaved, with well behaved borders, and regions must touch along a border to be adjacent - corners will not do. For example, in the United States, Arizona and Colorado are not adjacent, as they only meet at a corner, hence they could both be yellow. Similarly, Utah and New Mexico could both be blue. If this rule were not in place, then a pie with n slices meeting at the center would require n colors.

With this in mind, we can make the problem a little harder by increasing the number of regional connections. Squish Arizona and Colorado together so they actually share a border. This pushes Utah and New Mexico a centimeter apart, but no matter. If you can color this map, then the same coloring satisfies the original map. This map forces Arizona and Colorado to have different colors, a restriction that is relaxed in the original map. So to save time we jump straight to the "harder" map, wherein each vertex, each corner, brings exactly three regions together, or two regions if we are at the boundary of the map, e.g. California and Oregon. Such a map is called triangulated, with at most three regions touching at a vertex. These are the harder maps to solve, yet the analysis is a bit easier.

Next, bring in the ocean as another region that surrounds the map. color it blue if you like. Again, if you can color this map then remove the ocean and you have colored the original. With the ocean in play, every vertex connects three regions. The aforementioned western vertex connects California, Oregon, and the ocean.

Finally, assume the map is connected. If you wanted to color North America and Europe, you could color each separately using four colors and that would do the trick. So let the map be connected, and when you bring in the ocean that covers the whole planet.

Four colors are in fact necessary. Nevada is surrounded by a ring of five states: California, Oregon, Idaho, Utah, and Arizona. This ring requires three colors; it cannot be colored with two. Nevada must then acquire the fourth color. For a European example, Hungary is surrounded by a ring of 7 countries: Slovakia, Ukraine, Romania, Serbia, Croatia, Slovenia, and Austria, which also has 7 countries around.

Euler's Formula

Leonhard Euler was a Swiss born mathematician and physicist, the preeminent mathematician of the 18th century, and one of the most prolific. Along with pure and applied mathematics, he advanced the fields of optics, astronomy, fluid dynamics, mechanics, and even music theory. His formula, in the context of graph theory, relates the number of vertices, edges (borders), and faces (regions). With v for vertices, e for edges, and f for faces, his formula is as follows.

v - e + f = 2

Draw the capital letter B, with two countries inside, one on top of the other, and the ocean all around. Thus the number of regions, or faces, is 3. For the moment, let's be general and say that vertices and edges are however you want to define them. Establish six vertices, one on each side of the three horizontal segments of B. The edges are then three horizontal segments, two vertical segments forming the left edge of B, and the two curved edges forming the right side of B. That's 7 edges, whence 6 - 7 + 3 = 2, consistent with Euler's formula.

The proof is surprisingly easy, and beautiful. It is inductive, based on the number of edges. Remove the middle horizontal segment from B and join the two countries together into one. That's one less region and one less edge, preserving v - e + f. Or, if you prefer, remove the lower curved edge, whereupon the bottom country joins with the ocean. Again, one less region and one less edge. Having done this, remove the bottom horizontal segment and the right end vertex, leaving the capital letter P. One less edge and one less vertex - that preserves v - e + f. Remove the stem of P, leaving a small squared off version of the capital letter D. Again, one less edge and one less vertex. Remove the right curve, whence the enclosed country joins the ocean. Remove the top segment and its right vertex, the bottom segment and its right vertex, and the left segment and its top vertex. That leaves a single point and the ocean, whence v - e + f = 2. Every graph unravels down to a single point and the ocean, leaving v - e + f fixed all the while, hence v - e + f = 2 from the start.

The formula works in general, but as mentioned earlier, a well behaved map does not have vertices that simply cut edges in half. Each vertex is a meaningful demarkation of three regions. Thus the capital letter B would only have two vertices, the left and right endpoints of the middle segment. These are the points where three regions meet. The bottom half of B is an edge and the top half of B is an edge. Two vertices, three edges, three regions, and 2 - 3 + 3 = 2, as it should.

Five Neighbors or Less

Assuming a triangulated map, some region somewhere has five neighbors or less.

In our letter B example, each region has two neighbors, including the ocean. Nevada has five neighbors, the ring of states around it. Tennessee and Missouri lead the states with eight neighbors. Let fi be the number of faces with i neighbors. Let's see how fi fits into Euler's formula.

Let r be one of the regions with i neighbors. r has i edges and i vertices around. Each edge is shared between two faces. If the edge is a two lane highway, then r consumes i/2 edges. Since the map is triangulated, each vertex connects three regions. Thus r consumes i/3 vertices. Accounting for each r in fi, we have:

v - e + f

i×fi/3 - i×fi/2 + fi

-i×fi/6 + fi

fi × (1 - i/6)

When i = 6, this expression contributes nothing to Euler's formula. For i > 6, the expression is negative. However, Euler's formula has to evaluate to 2. Some expression is positive, hence there is some fi with i < 6, and some region with 5 neighbors or less.

The cube has 6 faces, each face having 4 neighbors. That's 6 × (1-4/6) = 2, so we're good.

The dodecahedron is a shape with 12 faces, each face a pentagon, having 5 neighbors. That's 12 × (1-5/6), or 2. All's well.

The Five Color Theorem

The five color theorem is based on induction on the number of regions. Let r be a region with 5 neighbors or less. Remove any edge of r and join regions together, so the map has one less region. It can be colored with 5 colors. Put the edge back in and leave r white, i.e. uncolored. If there are only 4 colors around r then give it the fifth color and you're done. If there are 5 colors around r then there is one country exhibiting each color, since r has 5 neighbors. Let the colors run red blue yellow green orange around, with red at the top. Switch red to yellow, and any adjacent yellow countries to red, and any adjacent red countries to yellow, and so on. If these red-yellow chains never reach the yellow next to r, then the colors run yellow blue yellow green orange around, and r can be painted red. However, if a chain connects red to yellow, then blue is inside the chain and green is outside. Change blue to green, and adjacent greens to blue, and adjacent blues to green, and so on, but these changes are contained within the red-yellow chain. The green connected to r is unaffected. The colors now run red green yellow green orange, and r can be painted blue. That completes the proof. Five colors are sufficient.

The four color theorem seems similar. If the neighbors of r exhibit three colors or less than there is no trouble. If r has four neighbors running red blue yellow green around, then switch red to yellow, and if there is a troublesome chain wrapping all the way around to yellow, then switch blue to green and you're done.

Suppose r has five neighbors running red blue red green yellow traveling clockwise. Switch blue to yellow if you can, without disturbing the other yellow; that would allow r to be painted blue and you would be done. If a blue-yellow chain prevents this, switch blue to green. If a blue-green chain prevents this, then a blue-yellow chain surrounds the first red, and a blue-green chain surrounds the second red. Change the first red to green and the second red to yellow, and aha, r can be painted red, and that completes the proof.

This is compelling, and many people were convinced by this argument, but it's not right. Pause and see if you can spot the flaw in this logic.

Spoiler. We think of the two chains as separate loops, but that might not be the case. They could cross each other several times, so that the blue-green chain weaves in and out of the blue-yellow chain. As the first red changes to green, the change propagates along red-green lines, and could disrupt the blue-green chain, turning some of those greens to red. We might not have a solid blue-green chain around the second red any more. We might not have the luxury of turning that red to yellow. So we can change the first red to green, or the second red to yellow, but perhaps not both.

Computer

These chaining arguments can be applied to various subgraphs, sections of the map, but there are far too many to enumerate with pencil and paper. In 1976, Appel and Haken, at the University of Illinois, wrote a computer program to check thousands of cases, and prove the four color theorem. This was the first computer assisted proof in mainstream mathematics. Is there a simpler proof that does not require a computer? We don't think so, but you never know.

Torus

Instead of a planet, imagine a map of countries drawn on the torus, which looks like a doughnut or innertube. Seven colors are both necessary and sufficient on the torus. Proof of sufficiency is very much like the five color theorem above, with a modified version of Euler's formula on the torus: v - e + f = 0. The new formula can be demonstrated by one vertex, a loop traveling around one way, a loop traveling around the other way, and one face. I'll leave the details to you. To show that seven colors are required, construct a map of seven countries, each touching the other six. Start with a 3 by 3 grid of squares, like a tic-tac-toe board. Sew the left and right edges together to form a cylinder. Then sew the top and bottom edges together to form a torus. Place country A in the center of the middle square, place B C and D in the squares running down the left column, and place E F and G in the squares running down the right column. Thus the countries look like this.
B E
C A F
D G

Directly connect A to the other 6 countries, with no "wrap-arounds". Thus A has 6 neighbors, and we are done with A.

Connect B to C to D to B, going straight down the left column. Of course the connection from D to B wraps around the torus, leaving the board at the bottom and reappearing at the top. In the same fashion, connect E to F to G to E, going straight down the right column. All that remains is to connect E F and G to B C and D.

Directly connect B to E and D to G, traveling across the middle column. Then connect B to G using a top-to-bottom path with slope ½.

Six connections to go. These all leave the right side of the board and reappear on the left. Connect F to C B and D, using paths with slopes 0 1 and 2 respectively. Connect E to D and C, using paths with slopes 1 and 2 respectively. Finally connect G to C with a path of slope 1. That completes the proof.

Three Dimensions

How many colors are required for a map of regions in 3 dimensional space? Infinitely many, because each region can have tendrils that reach out to all the others. Arrange infinitely many spheres in a line, perhaps down the x axis. The first sphere, at the origin, has an arm that runs the length of the x axis and touches every other sphere. The second sphere has another arm, a few degrees above the first, that runs down the x axis and touches all the remaining spheres. The third sphere has an arm, skinnier than the other two, and a degree higher, that touches the remaining spheres. Arms become skinnier, and are located further around the spheres, but there's room for infinitely many such arms, and at the end of the day, each sphere touches all the others, and infinitely many colors are required.

For a more interesting problem, assume all the regions are convex. There aren't any arms sticking out, or dents. Technically, for any two points in a region r, the entire segment connecting those points also lies in r. Now how many colors are required? Surprisingly, the answer is still infinite. Pause here and try to construct infinitely many convex regions, all mutually touching.

Spoiler. Let the regions lie in the first octant, bounded by the xy, xz, and yz planes. The first region is bounded above by the plane 3x + 2y + 3z = 6. Therefore the first region is a scaled version of the standard 3 simplex, and is convex.

Let the x and y axes define the floor, while the z axis is vertical, where the two walls meet. The first region r1 intersects the axes at 2 and 3 on the floor, and 2 at the peak of the roof.

To build the nth region rn, pass a cutting plane pn through the first octant, establishing a volume between itself and the union of the previous regions. Since this region is a polytope, it is convex.

Let pn intersect the coordinate axes in xn, yn, and zn. We already said x1 = 2, y1 = 3, and z1 = 2. Let xn = 1 + 1/n, yn = n + 2, and zn = 3 - 1/n. To see why this works, watch the planes as they intersect the walls and the floor. The cutting planes intersect the yz plane in a sequence of line segments that do not intersect each other. Both yn and zn steadily increase. In the limit these segments approach a ray parallel to the y axis with a z coordinate of 3. The yz wall of rn is a simple quadrilateral for n ≥ 2.

In the xz wall, line segments have slopes that start at -1 and approach -3. The x intercept moves from 2 to 1, while the z intercept moves from 2 to 3. The nth segment crosses its predecessor before colliding with the z axis. The nth intersection, between the lines defined by n and n-1, is:

xzn ∩ xzn-1
x = (n+1) / (4×(n-1))
y = (3n-4) × (3n-1) / (4n×(n-1))

These points move up and towards the z axis, approaching [1/4,9/4]. The xz wall of rn is an ever thinning triangle that approaches the segment joining [1/4,9/4] and [0,3].

If you walk across the tops of these regions, along the xz wall, you will discover smaller and smaller segments, like shingles that shrink as they tip up.

What happens on the xy floor? The lines on the floor have decreasing slopes of -n(n+2) / (n+1). These segments intersect the first segment, 3x + 2y = 6, at [2n+2,3n+6] / (2n+3). The x coordinate, 1 - 1/(2n+3), increases with n, and approaches 1. The y coordinate approaches 3/2 from above.

Consider the roof of rn. Climb up the xz wall to get to the start of this roof. You'll pass over the roofs of all the other regions along the way, following a polygonal path that is concave up. Once you reach the roof of rn, travel along this roof, i.e. within the plane pn, down to the xy floor, reaching the aforementioned intercept. Like the xz plane, this plane, pn, skates across the roofs of all the prior regions in a polygonal path. Let's see how this happens.

When n = 2, p2 cuts across the top of our first simplex, creating a seam if you will, the intersection of p1 and p2, a segment from [3/4,0,5/4] to [6/7,12/7,0]. The third plane, p3, starts higher on the xz wall, cuts through both planes, and lands closer to x = 1 on the floor. Clearly r3 touches r2 and r1.

Let q3 be the intersection of the first three planes. In general, let qn be the intersection of pn, pn-1, and pn-2. As you lay down the next plane p4, it defines q4, which is higher up on the preexisting seam p3 ∩ p2. This is closer to the xz wall, and it creates a new seam p4 ∩ p3. It also skates across p2 and p1. You want to derive the formula for qn and show that it steadily marches toward the xz wall, so that each plane makes a new seam, exposes the previous seam, and cuts across all the prior planes. It's a lot of algebra, and beyond the scope of this article. I hope the construction is reasonably intuitive. Each region touches all the previous regions, and infinitely many colors are required.

Further Reading

Euler and Euler's formula
The Four Color Theorem