Posted by: Dave Richeson | December 9, 2008

Four color theorem applets

The four color theorem is a beloved result with a long and fascinating history.

The theorem says that four colors suffice to color any map so that no two bordering regions are the same color. The conjecture was made in 1852 by Francis Guthrie. After many, many failed proofs, the conjecture was finally put to rest in 1976 (using a computer) by Kenneth Appel and Wolfgang Haken. To this date there is no pencil-and-paper proof of this seemingly elementary theorem.

Today I was exploring the website of the Japanese publisher and puzzle-popularizer Nikoli. The website has a number of interesting Flash-based logic games (Kakuro, Nurikabe, Sudoku, etc.). They also have five four color theorem applets such as the one below.

Four color

The goal of each puzzle is to find a four-coloring of the given map. I wish they had more than five of these!

About these ads

Responses

  1. For pencil-and-paper proof(s) see my arXiv papers. For illustrations including one of the puzzle visit: http://www.flickr.com/photos/49058045@N00/

    • Thanks for the link. If your papers get published, please post (or send me) the publication information.

  2. Nice applet

  3. Hi,

    I am also building a Java application (http://sourceforge.net/projects/maps-coloring) and a WordPress blog dedicated to the four color theorem, to share some ideas and to find a very easy “pencil and paper” proof (human checkable) of the four color theorem.

    I think I’ve found an interesting fact about maps, which I would like to verify and share with people interested in the problem. I’ve found that, all regular maps can be topologically transformed into circular or rectangular maps, which are more manageable forms of maps.

    Example of these maps with the proof of this transformation problem, can be found here (see T2 and “conversion of famous maps”): http://4coloring.wordpress.com

    Bye, Mario Stefanutti

  4. Here is a video that shows the nature of rectangular and circular maps.

    All maps concerning the four color theorem (“regular maps” | “planar graphs without loops”) can be topologically transformed into rectangular or circular maps.

    [youtube http://www.youtube.com/watch?v=Gj79LH7JHm0%5D


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 178 other followers

%d bloggers like this: