3 ms·
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
by mgallivan 14y 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".
- 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!