Is it true to say that a graph can be coloured by k colours if and only if the largest fully connected subgraph has k or fewer members?For example, is saying a planar graph can always be coloured by 4 colours the same as saying a planar graph can never have more than 4 nodes that are all connected to each other?

 They're not quite the same. Certainly if there are five vertices all connected to each other then the graph can't be four-coloured. But the converse isn't true.
 Thanks, that's a really great example. It definitely feels non trivial to come up with an example.
 No, in fact there are graphs of arbitrary chromatic number that don’t even contain a triangle. It’s true, and quite easy to prove, that a planar graph can’t contain a complete subgraph on 5 vertices. But this isn’t sufficient to prove the four-color theorem.There is a slight modification of the statement that may be correct; if you replace the condition of having a complete subgraph with that of having a complete minor, this is a very famous open problem called the Hadwiger conjecture. (It’s known to be true for the case n=5, i.e. every 5-chromatic graph has a K_5 minor.)
 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.
 Right—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.

Search: