3 ms·
In case anyone is wondering: Paris is not 3-colourable. The proof is trivial, by looking at region 6 and its neighbours.
by cperciva 14y ago
In case anyone is wondering: Paris is not 3-colourable. The proof is trivial, by looking at region 6 and its neighbours.
- agrona 14y agoSpecifically: 6 - R 7 - G 1 - B 15 - B 16 - R 8 - Cannot be R G or B
- deleted 14y ago[deleted]
- mgallivan 14y agoIs 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".
- ColinWright 14y agoNot 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.
- mgallivan 14y agoThanks!