Undergraduate Mathematical Sciences Seminar
Thursday, January 29, 2009, 12:30 -- 1:50pm
Planar Graphs and the Four Color Theorem
Steve Klee, Graduate Student, UW Department of Mathematics
Abstract: Loosely speaking, a graph is a collection of dots connected by lines. Despite this seemingly innocent definition, questions about graphs can be deceptively difficult to solve. In 1852, Francis Guthrie noticed that he could always color the counties in a map of England using only four colors. He then asked if this was true of any map -- if we want to color a map in a way that neighboring countries receive different colors, is it always enough to use at most four colors? Surprisingly, Guthrie's question was not answered until the 1970's by Appel and Haken.
In this talk, I will define graphs and pose Guthrie's problem in the language of graph theory. I will discuss the complexity of Appel and Haken's proof of the celebrated Four Color Theorem. To conclude the talk, I will give some counterintuitive results about graphs and discuss the applications of graph theory in other branches of science.