Graph Coloring, or Proof by Crayon | Hacker News Reader

Graph Coloring, or Proof by Crayon

jeremykun.wordpress.com

47 pointsColinWright21 comments

My dad was a mathemetician ("was" as in he died in 2001, otherwise I'd be sending this to him to comment on). I never understood most of what he did, but I know that some of the work he did was based on or related to the four-color proof referenced here. I once had a slightly less math intensive book (but still very academic) mainly about the four color theorem that referenced one of his papers as well, but alas I don't have it handy to find the relevant quote. I don't know where my copy went, but I bet my mom still has one.

I don't know that I have a point to this really other than to say that this post reminded me of my Dad, and all the things I haven't been able to send him links to for the last 11 years.

I find it amazing that people with such a deep and detailed grasp of mathematics such as this person are able to also express very advanced concepts in layman's terms through real-world examples and practical applications.

I'm only a semi-advanced secondary school student, so many of the concepts are way over my head at this point. Things like this article serve as catalysts to curiosity and are inspirations to pursue the study of the mathematics.

That's pretty much what I came to post here, but way more eloquent than when I would've written it :)

Articles like this make me realize that what was the most boring subject in school 10 years ago, is now quickly becoming my favorite tool in the world. Gotta love mathematics.

If people want more like this, _Introductory Graph Theory_ by Chartrand is an enjoying and easy read. In fact it looks like Dover has all kinds of short treatments of math subjects suitable to the layperson. And if you don't know about Martin Gardner, you really must check him out! _The Colossal Book of Mathematics_ and _The Night is Large_ are both wonderful big collections, and there are tons of smaller sets of essays.

I spent an afternoon one-on-one with Martin Gardner just a couple of months before he passed away. Fantastic man, wonderful to be with, and still sharp as anything at 95.

Deeply missed - I so wish I'd got in touch with him earlier. Like 40 years ago.

Another enjoyable book on this topic is "The Mathematical Coloring Book" by Alexander Soifer: http://www.amazon.com/Mathematical-Coloring-Book-Mathematics...

In case anyone is wondering: Paris is not 3-colourable. The proof is trivial, by looking at region 6 and its neighbours.

Specifically:

6 - R

7 - G

1 - B

15 - B

16 - R

8 - Cannot be R G or B

Is there any way to translate between this rather visual proof and the degrees of 8's neighbouring vertices?

I tried to find if there was some theory behind it but all I could really find was "saturation degree".

Not really, no. There are many, many results about when something is and is not three-colorable, but in the end, graph three coloring is NP-Complete.

Thanks!

So indeed it is true! We may color every map with just four colors!

Not true. A map of a country with four or more enclaves (e.g. late 19th century China) would not meet this condition.

It is true under the convention that we color each contiguous region the same color, and each contiguous region can get any color. It is pretty clearly not true if you insist that non-contiguous regions must be colored the same, which is what happens with enclaves.

This latter case is covered by the more abstract version of vertex coloring general graphs, which started with the four color conjecture by Guthrie in the late 1800's, but continues to this day with things like register coloring in compilers, schedule coloring in timetabling, and with the knowledge that graph three (vertex) coloring is NP-Complete.

Why can't you color every enclave the same color - something different from the province they're inside of?

The traditional 4-color map rule only says that each neighboring region has a different color, not that the colors are meaningful.

In mapping, enclaves are usually colored the same as the "parent" country to which they belong. It's an additional restriction that's actually well catered for in the generic graph coloring context, as opposed to the "map" coloring of the original problem (which did not bother with the enclave issue).

I believe his claim is that one country has 4 disconnected regions. If you have that and can only use one graph node to represent all of the disconnected regions then the adjacency graph isn't necessarily planar.

I don't understand why the Costa Rica example is 3-colorable. The green province in the middle touches 5 other provinces so it seems like it should be 5-colorable.

Not all of CRs neighbors touch each other.

Consider a pizza sliced into six pieces. Each piece touches only their neighbor on each side, so you can color them alternately red and blue. Now suppose someone carved an island in the middle around an olive that no one wants. That touches all six, but can still be colored green, so we use only three colors in total, despite the middle "region" having six neighbors.

I don't know Paris specifically, but but nautilusy spiral happens (in anthropology, and also biology) when new growth happens that the position closest to the center, which is a natural goal when proximity is a desirable feature (minimized construction costs, maximize access to community, minimize outer perimeter for defense, etc)

I'm not sure this case can actually be said to be nautilusy rather than simply uneven concentric circles.

Reply on news.ycombinator.com