Platinum Partner
architects,bigdata,theory,tips and tricks,tools & methods

The Seven Color Map Theorem

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 {{ articles[0].authors[0].realName }}, DZone MVB. (source)

Opinions expressed by DZone contributors are their own.

{{ tag }}, {{tag}},

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}
{{ parent.authors[0].realName || parent.author}}

{{ parent.authors[0].tagline || parent.tagline }}

{{ parent.views }} ViewsClicks
Tweet

{{parent.nComments}}