[mgallivan]

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]

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.

[mgallivan]

Thanks!