Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

The Seven Color Map Theorem

· Big Data Zone ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Hortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

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

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.

Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub.  Join the discussion.

Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.