3 ms·
The problem description doesn’t specify “planar”, and K4 has degree 3 for each of its four vertices, but (obviously) requires 4 colors (and K5 has maximum degre
by Someone 9y ago
The problem description doesn’t specify “planar”, and K4 has degree 3 for each of its four vertices, but (obviously) requires 4 colors (and K5 has maximum degree 4, but requires 5 colors, etc.)
Also, K3, K2 and K1 are planar with maximum degree 2, 1, respectively 0, but require 3, 2, 1 colors.
So, in general, D colors isn’t sufficient.