Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.
Four Color Theorem
Transcript of Four Color Theorem
By Courtney Traylor, Michele Schuhriemen, and Mary Kate Sullivan
Francis Guthrie first realized this idea when he noticed four different colors were needed, while coloring a map of England
The four color theorem was proven in by Kenneth Appel and Wolfgang Haken in 1976
History of Four Color Theorem
Vertex Coloring - Each vertex of a graph is assigned to a color (or a number representing the color) that is different from the colors assigned to any of its adjacent vertices
Chromatic Number - The fewest number of colors required to color a graph so that adjacent vertices receive different colors
Mapmakers need to determine the chromatic number so they know the fewest amount of colors to use
Planar vs Non Planar
Planar- A graph that can be drawn on the plane in such a way that its edges may intersect only at their endpoints
Use this map to create a graph that shows the minimal amount of colors needed (Chromatic Number) for this map
3 minutes to do this!
World Map Using the Four Color Theorem
Real World Applications
The four color theorem can be applied to many real life examples such as scheduling. When scheduling finals, Universities do not want students to have two exams at the same time but they want as many exams running concurrently as possible. The color theorem can be useful in this situation. If each class is given a vertex and a edge between vertices represents any two classes that contain the same student the different colors will represent different time slots. The minimum number of colors used will equal how many time slots are necessary.
Final Exam Scheduling
Six students at Clemson University are enrolled in six different courses. Alexa is in Math, English and Art. Olivia is in Math, Science and Music. Amelia is in Math, Science and Art. Mark is in Math, History, Music and Art. Matt is in English and Art and Sophia is in Science, History and Music. The University is scheduling the final exams and does not want to schedule students to have two exams in the same class at the same time. Construct a color graph to create the minimal amount of time slots for exams.
Period 1: Math
Period 2: Art, Music
Period 3:English, Science
Period 4: History
Alexa: Math, English, Art
Olivia: Math, Science, Music
Amelia: Math, Science, Art
Mark: Math, History, Music
Matt: English, Art
Sophia: Science, History, Music
Scheduling Class Activity
Thomas: Science, Geography, Music
Sydney: Spanish, Biology, PE
Kayla: Biology, PE
Lauren: Spanish, Science, Music
Hannah: Spanish, Geography, Music
Josh: Spanish, Science, PE