Spiked Math Games  // Math Fail Blog  // Gauss Facts  // Spiked Math Comics



Coloring Book - February 6, 2012
Rating: 4.7/5 (53 votes cast)
  • Currently 4.7/5
  • 1
  • 2
  • 3
  • 4
  • 5

Spiked Math Comic - Coloring Book

The last problem is known as the Hadwiger-Nelson problem. The chromatic number of the plane is currently an open problem but it is known to be between 4 and 7. For the upper bound, one must (simply) construct a coloring using 7 colors.  Lower bounds are a bit harder to get!

home     info     archive     contact     rss

Google+ Page   //   Facebook Page   //   Twitter Page


So is the first one easy because of being impossible?

I'm fairly certain it's not impossible.

For the first one:

Outer pentagon, starting at the upper vertex, going clockwise: R, Y, R, Y, G.
Inner star, starting at the upper vertex, going clockwise: Y, G, G, R, Y.

"For the upper bound, one must (simply) construct a coloring using 7 colors."
I think you accidentally a word there.

Lower bound of the last one is fairly easy as well. Suppose 3 colours suffices. An equilateral triangle (of unit edge length) must be rainbow (all three colours are used on the vertices). Glue two such triangles together along an edge to get a rhombus. The two vertices ("tips") on the longer diagonal must be the same colour. Now take two copies of this rhombus and identify one pair of the tips and make the other pair be one unit distance apart. There is a monochromatic edge. A contradiction.

second one, think of combinatorics. Starting from the single vertex, we have three colour choices. The next one along has two possibly colour choices (6 total, so far), for the remaining two, we must use the two colours that were not used for the middle vertex, and there are two ways these can be arranged. So in total we have 3*2*2=12


I may be wrong here, but it seems to me that you're essentially constructing a specific scenario to prove your point. If you purposely create a contradiction, of course there will be a contradiction.
What I'm saying is, what you have demonstrated is that it is POSSIBLE for a contradiction to occur, not that one MUST occur.

A) easy ...
going clockwise from top, red, blue, green, red, blue
inner star from top, green, green, blue, blue, red

B) 4 possible combinations per colour (middle colour is unique in each combination) 3 colours, 12 possible combinations in total.

| 3-4

1) 3=red, 1=4=blue, 2=green
2) 3=red, 1=blue, 2=4=green
3) 3=red, 1=4=green, 2=blue
4) 3=red, 1=green, 2=4=blue

5) 3=blue, 1=4=red, 2=green
6) 3=blue, 1=red, 2=4=green
7) 3=blue, 1=4=green, 2=red
8) 3=blue, 1=green, 2=4=red

9) 3=green, 1=4=red, 2=blue
10) 3=green, 1=red, 2=4=blue
11) 3=green, 1=4=blue, 2=red
12) 3=green, 1=blue, 2=4=red

C) impossible (for me) :)

JP, if you are talking to me, then indeed, you are wrong. However, I do apologize for leaving some details out that I thought was obvious. Let me flesh it out more.

We are given an infinite graph G, where the vertices are the points in the plane, and the edges connect every pair of vertices that are at unit distance from each other. This is known as the unit distance graph (of the plane). The task is to provide a lower bound for the chromatic number of G.

Now the finite graph H I constructed in my previous comment is a subgraph of G. So the chromatic number of H provides a lower bound for the chromatic number of G. Indeed, if H cannot be properly coloured by 3 colours, then of course G cannot either. This implies that the chromatic number of G is at least 4.

We had just gone over the last problem in Applied Combinatorics class (junior undergrad level), though we hadn't yet gone into four or more colors., The proof for two colors being impossible is a simple example of proof by contradiction. Assume first that the point in the center has all points at radius exactly 1 be a different color. As a result, there exist two points both on the perimeter of the circle whose distance will be 1 unit away.
The proof that it can't be three can be constructed similarly. The way it was shown to us was using a similar explanation that Htam used. In the case of only three colors, given an equilateral triangle, all three vertices must be different colors. In the interest of naming things, we'll say one vertex is at the origin, O. On the opposite side of the triangle, there must be the same color as was at the origin(since there are only three colors to choose from). For the origin not to have any point at distance one unit away all points at radius 1 unit away must be alternating between the remaining two colors, creating a two-color perimeter circle. However for each pair of points on the perimeter, there will be a point outside the circle the same color as the origin. We can think of this as yet another circle outside of the first, and this with a single color along the entire perimeter. As such, there will be times where the distance is only 1 from one point of the larger circle to another point on the same circle.

Regarding the Hadwiger-Nelson problem, proving that 4 <= Chi(G) <= 7 is one of my favorite proofs. 1. Moser Spindle, 2. Tile the plain with hexagons, and BOOM.

Maybe I'm under-thinking it. But it seems obvious that it only 4 are necessary for the last problem.

Leave a comment

Profile pictures are tied to your email address and can be set up at Gravatar. Click here for recent comments.
(Note: You must have javascript enabled to leave comments, otherwise you will get a comment submission error.)
If you make a mistake or the comment doesn't show up properly, email me and I'll gladly fix it :-).


home     info     archive     contact     rss

Google+ Page   //   Facebook Page   //   Twitter Page

Welcome to Spiked Math!

Hello my fellow math geeks. My name is Mike and I am the creator of Spiked Math Comics, a math comic dedicated to humor, educate and entertain the geek in you. Beware though, there might be some math involved :D

New to Spiked Math?
View the top comics.

New Feature: Browse the archives in quick view! Choose from a black, white or grey background.