Big Data/Analytics Zone is brought to you in partnership with:

John Cook is an applied mathematician working in Houston, Texas. His career has been a blend of research, software development, consulting, and management. John is a DZone MVB and is not an employee of DZone and has posted 171 posts at DZone. You can read more from them at their website. View Full User Profile

The Seven Color Map Theorem

07.20.2013
| 3278 views |
  • submit to reddit

The famous four color theorem says that any flat map can be colored with four colors so that no two countries that touch at more than a point are the same color. The hard part is to show that four colors are sufficient; it’s easy to show that four colors are necessary.

It’s easier to prove generalizations of the four color theorem to more complex surfaces. These were settled decades before the original four color theorem.

For example, the seven color map theorem says that any map on a torus (doughnut) can be colored using seven colors, and there exists a map that requires seven colors.

Besides the seven color theorem for the torus, there’s an eight color theorem for a surface with two holes, a nine color theorem for a surface with three holes, etc. In fact, there’s an n color theorem for all n at least 7.

From the examples above, it looks like if a surface has g holes (g for genus, what topologists call these holes), the number of colors required is 6 + g. That’s true for g up to 6, but then it fails. The actual theorem is that a surface with g holes requires

\left\lfloor \frac{7 + \sqrt{1+48g}}{2}\right\rfloor

colors where ⌊ x ⌋ is the largest integer no greater than x.

Because the expression above flattens out as a function of g, it will produce all integers greater than 6, and will produce some several times. For example, a map on a surface with 6 holes requires 12 colors, but so does a map on a surface with 7 holes.

Source: Four Colors Suffice: How the Map Problem Was Solved

Published at DZone with permission of John Cook, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)