Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
The Four- Color Theorem
6
The Four- Color Theorem
Proof relies on being able to
reduce a set of configurations
on a graph.
Why did it take so long to prove the theorem?
- It was easy to prove that 6 colors would work and to reduce that number to 5, but very hard to prove 4
- Thought to be 9,000 different map configurations= turned to computers
Four Color Theorem
Any map in a plane can be colored using 4 colors in such a way that regions sharing a common boundary do not share the same color
Proof by Computer
1976 Kenneth Appel and Wolfgang Haken constructed a computer-assisted proof that four colors were sufficient (not accepted by some mathematicians)
1996 Shorter, more efficient proof by Robertson et al.
2004 G. Gonthier verified proof using Coq proof assistant (interactive theorem prover)- removed need to trust many computer programs, only necessary to trust Coq.
Definition
Given any separation of a plane into adjacent regions, the regions can be colored using at most four colors so that no adjoining regions have the same color. A region is adjacent to another if they share a border and NOT just a point.
Early Proof Attempts
1852 Francis Guthrie conjectured theorem- difficult to prove
1878 Arthur Cayley wrote first paper on conjecture, made contributions to the way the problem was approached
1879/80 Fallacious proofs given by Alfred Kempe and P.G.Tait (accepted for a decade)
1890 Percy Heawood finds flaw in Kempe’s proof, proves 5-color theorem (Heawood conjecture)
"The bound for the number of colors which are sufficient for map coloring on a surface of genus g
Why you should care
- Outstanding example of how old ideas combine with new discoveries and techniques in different fields of mathematics to provide new approaches to a problem
- Example of how an apparently simple problem was thought to be "solved" but then became more complex
- First example where a computer was involved in proving a mathematical theorem
- Great example of mathematical controversy: is a proof done on a computer a proper proof?