Four Color Theorem in Discrete Mathematics
In 1852, Francis Guthrie, a student of Augustus De Morgan, a notable British mathematician and logician, proposed the 4-color problem. He defined the problem in terms of maps that meet specific requirements, such as not having any holes and connecting every region (e.g. country or state) so that no region exists in two or more non-contiguous sections.
Guthrie asserted that with such maps, no more than four colors would be required to color the map so that no two adjacent parts were the same color.
If the regions of Map M are colored so that adjacent regions are different, then no more than 4 colors are required.
Every planar graph is 4-colorable (Vertex Coloring) but when a triangle is a graph or sub-graph we need only 3 colors.
Four Color Theorem Definition
The Four Color Theorem states that any planar graph (a graph that can be drawn on a plane without any edges crossing) can be colored with at most four colors such that no two adjacent vertices share the same color.
Mathematicians had been attempting for years to come up with a sophisticated proof (of a color theorem) along the lines of the Six Color Theorem or the Five Color Theorem, and using the brute force method almost appeared like hacking the process.
Every planar graph can be colored in four different ways.
Vertices and edges are found in graphs. We want adjacent vertices/ regions to be of different colors.
Four Color Theorem and Kuratowski’s Theorem in Discrete Mathematics
The Four Color Theorem and Kuratowski’s Theorem are two fundamental results in discrete mathematics, specifically in the field of graph theory. Both theorems address the properties of planar graphs but from different perspectives.
In this article, we will understand about Four Color Theorem and Kuratowski’s Theorem in Discrete Mathematics, their definition, examples, and semantic differences between them.
Table of Content
- Four Color Theorem in Discrete Mathematics
- Four Color Theorem Definition
- How to color?
- Example – Four Color Theorem
- Kuratowski’s Theorem in Discrete Mathematics
- Kuratowski’s Theorem Definition
- Example – Kuratowski’s Theorem
- Semantic Difference between Four Color Theorem and Kuratowski’s Theorem