The Four Color Theorem: Any map on the plane
or the sphere can be colored with at most 4
The Color problems: Discussion and proof of the five color theorem.
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 article by Eric W. Weisstein © 1999 CRC Press LLC, © 1999-2003 Wolfram Research, Inc.
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 JOC/EFR September 1996
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 Euler's formula we can deduce that the sum of the charges over all the vertices must be 12. A given set S of configurations can be proved unavoidable if for a triangulation T which does not contain a configuration in S we can redistribute the charges (without changing the total charge) so that no vertex ends up with a positive charge.
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.
What about graphs on the Torus?
We have a connected graph on the torus with one vertex, two edges and only one region. But this information does not match for the euler formula for the plane or the sphere. SO.. the torus must be topologically different from the sphere or the plane!
In fact for the torus we see that it is possible for V+R= E or V-E+R= 0
We learned about
(and proved) Euler's Formula
for the plane or the sphere. What can we say about a formula for the torus or the Klein bottle?
Surfaces:Mark Sudduth's web page of surfaces.[ A physics master's degree student at UT, Arlington.
What is a surface?
With or without boundary:
Orientable or Non-orientable: we considered the moebius band and the Klein Bottle as examples of non-orientable surfaces.
Can be realized (imbedded) in a plane, in 3 space, in 4 space.
Can be visualized (immersed) in ...
Examples:A closed disc, an open disc, a
plane, an annulus- cylinder, a mobius band;
Experiments with the mobius band. Drawing a curve along the center of the band we cover both "sides." Cutting along that curve the band does not fall apart, but gets twice as long!
a Klein bottle
the projective plane... Why is this a closed and bounded surface?
A sphere with a cross cap .
Activity:Graphs on the torus.
Games and puzzles on the torus and the klein bottle.
From the Fun Fact files,
hosted by the
Harvey Mudd College Math Department , |
Imagine that the two objects in Figure 1 are solid (with thickness) and made of very flexible and stretchy rubber.
Question: is it possible to deform one object into the other in a continuous motion (without tearing or cutting)?
Surprise answer: Yes!!
Hint: it is important that the object is solid and has thickness; this transformation cannot be done with a one-dimensional piece of string. It is also not possible to do this with a piece of rope because even though the rope has thickness, it is not flexible or "stretchy" enough. See below for an explanation and animated gif. Or, don't scroll down if you want to think about it a while!
The Math Behind the Fact:
Visualizations of surfaces by flattened - cut apart models.
A cylinder, a mobius band, the torus, the Klein bottle, the projective plane.
Closed Surfaces: Handles and cross-caps attached to the sphere.
A sphere with a handle = a torus
A Sphere with a cross cap = the projective plane
The Topological Classification of "closed surfaces."
Every connected closed and bounded surface is topologically equivalent to a sphere with handles and crosscaps attached.