# Four Color Theorem

(Difference between revisions)
 Revision as of 14:54, 3 June 2009 (edit)← Previous diff Revision as of 09:36, 4 June 2009 (edit) (undo)Next diff → Line 1: Line 1: {{Image Description {{Image Description - |ImageName=Four Color + |ImageName=Four Color Theorem |Image=Usagraphfinal2.PNG |Image=Usagraphfinal2.PNG |ImageIntro=Four coloring and graph representation of the United States. |ImageIntro=Four coloring and graph representation of the United States. Line 6: Line 6: It turns out that only four colors are needed to color such a two-dimensional map. It has taken over a century for a correct proof of this fact to emerge, and the proof can currently only be carried out with the aid of computers. An example of a map colored with only 4 colors is the map of The United States on this page's main image. It turns out that only four colors are needed to color such a two-dimensional map. It has taken over a century for a correct proof of this fact to emerge, and the proof can currently only be carried out with the aid of computers. An example of a map colored with only 4 colors is the map of The United States on this page's main image. - |ImageDesc=Map coloring is an application of Graph Theory, the study of graphs. A graph is informally a collection of points, known as vertices, connected by lines, known as edges. This p + |ImageDesc=[[Image:Graphexample.JPG|thumb|left|200px|Example of a planar graph (top) and a non-planar graph (bottom)]]Map coloring is an application of Graph Theory, the study of graphs. A graph is informally a collection of points, known as vertices, connected by lines, known as edges. A graph is planar if no two edges overlap each other, as shown in the diagram to the left. Graphs are useful to analyze map coloring because a map can be easily converted into a planar graph by representing each territory with a vertex and each border with an edge, as in this page's main image. |AuthorName=Brendan John |AuthorName=Brendan John |Field=Graph Theory |Field=Graph Theory |InProgress=Yes |InProgress=Yes }} }}

## Revision as of 09:36, 4 June 2009

Four Color Theorem

Four coloring and graph representation of the United States.

# Basic Description

How many colors are needed to color the territories of a map, if all the territories that share a border must be of different colors?

It turns out that only four colors are needed to color such a two-dimensional map. It has taken over a century for a correct proof of this fact to emerge, and the proof can currently only be carried out with the aid of computers. An example of a map colored with only 4 colors is the map of The United States on this page's main image.

# A More Mathematical Explanation

[[Image:Graphexample.JPG|thumb|left|200px|Example of a planar graph (top) and a non-planar graph (bot [...]

Example of a planar graph (top) and a non-planar graph (bottom)
Map coloring is an application of Graph Theory, the study of graphs. A graph is informally a collection of points, known as vertices, connected by lines, known as edges. A graph is planar if no two edges overlap each other, as shown in the diagram to the left. Graphs are useful to analyze map coloring because a map can be easily converted into a planar graph by representing each territory with a vertex and each border with an edge, as in this page's main image.