3 ms·
To confirm I understand (and I think this is where I was at originally): If a graph contains K_5 then it requires at least 5 colours to colour, but if a graph
by Cogito 7y ago
To confirm I understand (and I think this is where I was at originally):
If a graph contains K_5 then it requires at least 5 colours to colour, but if a graph does not contain K_5 then it might still require 5 colours.
The example given by OscarCunningham is a great one.
- intuitionist 7y agoRight—as mathematicians say, having a K_n subgraph is a sufficient but not necessary condition for having a chromatic number of at least n. Hadwiger’s conjecture goes the other way, stating that having a K_n minor is a necessary but not sufficient condition for having a chromatic number of at least n.