Three-Colored Christmas ‘Tree’
Merry Christmas and Happy New Year 2019! I suppose it’s not too late to say that. It’s been more than a year since I wrote my last post, so I plan to write more this year: New Year, New Resolution, New Posts.
This Christmas, my girlfriend and I decorated our Christmas tree in Fig 1.
Whoops! Actually, it’s not a ‘tree’ by any means, but let’s call it a ‘tree’. There were also 3 kinds of ornaments available: star (silver), heart (red) and ball (gold). Our task was to hang an ornament on each spot. Here is the catch: We want to ensure every pair of adjacent spots has different ornaments. This is Three-Color problem in mathematics. Why three? We only have three different ornaments at that time :)
Four-Color Problem
Three-Color problem is more difficult than Four-Color problem, so let’s start with this one first. This problem has been solved using a computer, so in mathematical language, we can call it Four-Color theorem:
Given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
I won’t explain the proof in details since it’s complex and requires background knowledge in Graph Theory. You can read the summary of the proof here.
To test the theorem, you can try coloring it by yourself. Take any random maps or draw any separated regions. Next, pick 4 different colored pencils and start coloring the regions. The chances are you might not be successful at the first attempt. The theorem doesn't guarantee that you will be successful if you color them randomly. Instead, there exists possible color combinations to color every region so that no pair of regions has the same color. The example can be found in Fig 2.
Three-Color Problem
Unlike Four-Color problem, you cannot always color any maps or regions using only three color. Why is that? You simply have less colors to use so the task is harder. For example, take a look at Fig 3. You simply cannot color it with only three colors.
x-Color Problem
Well, you can use any number of color you want. However, you should remember the idea. If x=2, you won’t make it with only that few colors obviously. If x≥5, the task can be done in easier way, i.e. it’s easier to find the right setup.
Applications
Aside from the knowledge that every map can be colored with only 4 colors (which is useful for cartography), it’s hard to find the real life applications of Four-Color theorem. This post explains some of the applications, however I think they don’t use the theorem directly.
Nevertheless, the theorem is pretty much applicable to art. For instance, if you want to decorate using colors (just like I did with my Christmas ‘tree’), you may find the theorem useful. Quoting from Kenneth May, you can always color every map with 4 colors, but 3 colors are enough in most cases.
That’s all I want to share in this short post. My goal is to share to you all that beauties and application of mathematics can be found in simple things around you. Thanks for reading! Your claps and feedbacks are all appreciated.
Here are the references for further reading:
- Four Color Theorem: https://en.wikipedia.org/wiki/Four_color_theorem
- Formal Proof — Four Color Theorem: https://www.ams.org/notices/200811/tx081101382p.pdf
