**Thursday 10-27
**

**Last class we applied Euler's
Formula for the plane or the sphere:
Theorem: For any connected graph in the
plane,
**

**We'll continue to examine more applications of this topological property of graphs (networks) in the plane.
**

**Last class we applied "Euler" to analysis of the Utilities problem.
**

**Complete graphs. A complete graph is a graph in
which each vertex of the graph is connected by an edge to every other vertex.**

**For example:**

**2 vertices: 1 edge - a line segment
3 vertices: 3 edges - a triangle
4 vertices: 6 edges - a tetrahedron
Notice these all have planar representations.
The technical way this is decribed is to say these graphs can be **

**Discussion: Analysis. Suppose this were possible
and consider the consequences.
If the graph were drawn it would have V = 5 vertices and E= ? _
__ edges.
Based on Euler's formula, the graph would therefore have to have R=?
regions in the
plane.
**

** By design each region would have to have
at least 3 edges.
Thus if we count the edges by the regions we would have at least 3R=21
edges counting each edge twice- because an edge is a boundary for exactly
two regions.
Thus the number of edges must be more than 3/2R=10 1/2.
Is this possible? What can we conclude?**

**Coloring problems: Suppose we have a map that
consists of a graph that deteremines R regions ( countries) with E edges
(borders). How many colors are needed
to color the regions so that countries that share a border (not merely a
vertex) have different colors.**

The Junkyard on the color problem.

From Serendip
at Bryn Mawr College.

The Shockwave movie below makes it possible for you to play with the four
color problem yourself. Create a "map of countries" of any number, shape,
and size by drawing in the space, or let Serendip create a map for you by
clicking on the Generate Map button. The question is how many colors are
required to color such a map, using the rule that no two countries with adjacent
borders may be the same color (countries meeting at a point may be the same
color).

Once generated, either by you or by Serendip, click on Submit Map. After a processing delay, Serendip will then present the map to you in grey, and you can color individual countries by clicking on them (or let Serendip color the map for you). See if you can create a map that requires two colors, or three colors, or four colors. If you create one that requires five colors, you will upset mathematicians (and a few others) worldwide.Warning: Serendip has a small bug- so that sometimes it will give a less than best coloring of the map or will evaluate your work incorrectly.

Created by Paul Grobstein and Sasha Schwartz. Shockwave
programming by Sasha Schwartz. Reactions, comments, suggestions gratefully received.

Send us your comments at Serendip

© by Serendip 1994-2003 - Last Modified:
Wednesday, 05-Mar-2003 17:11:21 EST

**Draw a map that needs 3 colors.
Draw a map that needs 4 colors.
Draw a map that needs 5 colors.
**

**The Four Color Theorem: Any map on the plane or
the sphere can be colored with at most 4 colors.
**The Color
problems: Discussion and proof of the

** Some References for "proofs":
1995
** summary of a new proof of the Four Color
Theorem and a four-coloring algorithm found by Neil Robertson,
Daniel P. Sanders,
Paul Seymour and Robin Thomas.

1999

From the Math History web site: http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/The_four_colour_theorem.html

**Article by: J J O'Connor and
E F Robertson**

**However the final ideas necessary for the solution of the
Four Colour Conjecture had been introduced before these last two results.
Heesch in 1969 introduced the method of discharging. This consists
of assigning to a vertex of degree i the charge 6-i. Now from **

** Heesch thought that the Four Colour Conjecture could be
solved by considering a set of around 8900 configurations. There were difficulties
with his approach since some of his configurations had a boundary of up to
18 edges and could not be tested for reducibility. The tests for reducibility
used Kempe chain arguments but some configurations had obstacles to prevent
reduction. **

**The year 1976 saw a complete solution to the Four Colour
Conjecture when it was to become the Four Colour Theorem for the second, and
last, time. The proof was achieved by Appel and Haken, basing their methods
on reducibility using Kempe
chains. They carried through the ideas of Heesch and eventually they constructed
an unavoidable set with around 1500 configurations. They managed to keep
the boundary ring size down to less than or equal to 14 making computations
easier that for the Heesch case. There was a long period where they essentially
used trial and error together with unbelievable intuition to modify their
unavoidable set and their discharging procedure. Appel and Haken used 1200
hours of computer time to work through the details of the final proof. Koch
assisted Appel and Haken with the computer calculations. **

** The Four Colour Theorem was the first major theorem to
be proved using a computer, having a proof that could not be verified directly
by other mathematicians. Despite some worries about this initially, independent
verification soon convinced everyone that the Four Colour Theorem had finally
been proved. Details of the proof appeared in two articles in 1977. Recent
work has led to improvements in the algorithm.**