How to color?
Take any map and divide it into a set of connected regions: R1, R2 … Rn with continuous boundaries.
There must be some way to assign each region Ri -> in the set {R, G, B, Y}, such that if two regions Ri and Rj are “touching” (i.e. they share some nonzero length of the boundary between them), they must receive different colors.
Example – Four Color Theorem
1. The four-color map is shown below :
A planar map
Here, as you can see, every region that touches another region has a different color than the touching one & we required a total of a maximum of four colors to color this map – Red, Green, Blue & yellow.
2. The transformation of an uncolored Map G into a colored Map is shown below –
Map G
Here you can see that every region that touches another region has a different color than the touching one & we required a total of maximum four colors to color this map – Red, Green, Blue & yellow.
3. The transformation of an uncolored Map H into a colored Map is shown below –
Map H
Here also you can see that every region that touches another region has a different color than the touching one & we required a total of a maximum of four colors to color this map – Red, Green, Blue & yellow.
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