The minimum number of colors is called the chromatic number of the graph. In this way, the map coloring problem becomes a graph coloring problem: Color the vertices so neighbors are different colors. If it helps, we can imagine that the vertices are the capital cities and the edges are roads joining them. Replace each region of the map with a vertex and connect the vertices of neighboring regions with an edge. To focus on the information that matters, we can encode these relationships using a graph, also known as a network, where dots (vertices) are connected by lines (edges). map from being four-colorable, but it could, mathematically. All that matters is which regions share boundaries, although we do require all regions to be connected Michigan, with its separate upper peninsula, doesn’t actually prevent the U.S. To understand how Kempe and most mathematicians have looked at this problem, it helps to recognize that a map contains a lot of information irrelevant to the coloring problem, such as the shape, size and exact location of each region. Yet it was ingenious, and it contained key ideas that would appear in the eventual proof. Unfortunately, Kempe’s proof - like all the others that would appear for the next century - was flawed. The proof was convincing, and it was accepted as correct for over a decade. It was the first one, by the barrister Alfred Kempe in 1879, that turned out to be the most important. Soon after that, proofs started appearing. The problem sat largely dormant until 1878, when Arthur Cayley asked members of the London Mathematical Society if anyone had found a proof.
0 Comments
Leave a Reply. |