Graph Coloring, or Proof by Crayon

http://jeremykun.wordpress.com/2011/07/14/graph-coloring-or-proof-by-crayon/

by ColinWright • 14 years ago

47 21 14 years ago

jeremykun.wordpress.com

cperciva• 14 years ago

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

agrona• 14 years ago

Specifically:

6 - R

7 - G

1 - B

15 - B

16 - R

8 - Cannot be R G or B

mgallivan2• 14 years ago

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".

AbsoluteZeroFF• 14 years ago

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.

richforrester• 14 years ago

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.

Ogre• 14 years ago

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.

pjungwir• 14 years ago

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.

ColinWright5• 14 years ago

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.

jnotarstefano• 14 years ago

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

jscipione• 14 years ago

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.

Evbn2• 14 years ago

Not all of CRs neighbors touch each other.

ColinWright5• 14 years ago

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.

Evbn2• 14 years ago

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)

esrauch2• 14 years ago

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

dmerfield• 14 years ago

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.

ColinWright5• 14 years ago

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.

cookingrobot• 14 years ago

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.

ColinWright5• 14 years ago

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).

esrauch2• 14 years ago

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.

Graph Coloring, or Proof by Crayon

Related Stories