News for hackers. Stuff that matters.
Re:Graph Coloring, or Proof by Crayon by cperciva on Tuesday December 18, 2012 @01:28PM (#4938769)
In case anyone is wondering: Paris is not 3-colourable. The proof is trivial, by looking at region 6 and its neighbours.
Re:Graph Coloring, or Proof by Crayon by agrona on Tuesday December 18, 2012 @02:45PM (#4939187)
Specifically:

6 - R

7 - G

1 - B

15 - B

16 - R

8 - Cannot be R G or B

Re:Graph Coloring, or Proof by Crayon by mgallivan on Tuesday December 18, 2012 @05:33PM (#4940003)
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".

Re:Graph Coloring, or Proof by Crayon by ColinWright on Tuesday December 18, 2012 @05:45PM (#4940061)
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.
Re:Graph Coloring, or Proof by Crayon by mgallivan on Tuesday December 18, 2012 @06:41PM (#4940335)
Thanks!