# Four Color Theorem

(Difference between revisions)
 Revision as of 09:36, 4 June 2009 (edit)← Previous diff Revision as of 10:13, 4 June 2009 (edit) (undo)Next diff → Line 5: Line 5: |ImageDescElem=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? |ImageDescElem=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. + 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 currently known proofs can 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=[[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. + |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'''. Two vertices connected by an edge are said to be '''adjacent'''. 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 easily be 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. An edge is not drawn between two territories which share only a corner, such between Utah and New Mexico. The four color theorem states that the vertices of any planar graph can be colored with at most four colors such that no adjacent vertices are the same color. Since every map can be represented by a planar graph, this theorem is the same as saying any map where each territory + |AuthorName=Brendan John |AuthorName=Brendan John |Field=Graph Theory |Field=Graph Theory |InProgress=Yes |InProgress=Yes }} }}

## Revision as of 10:13, 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 currently known proofs can 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. Two vertices connected by an edge are said to be adjacent. 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 easily be 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. An edge is not drawn between two territories which share only a corner, such between Utah and New Mexico. The four color theorem states that the vertices of any planar graph can be colored with at most four colors such that no adjacent vertices are the same color. Since every map can be represented by a planar graph, this theorem is the same as saying any map where each territory