Let G be an undirected simple graph and a subgraph of satisfying for some . What can be said about the relation between and ? Find a graph with which does not have a as a subgraph.
Since contains a sub-graph isomorph to the minimum number of colours needed to colour the whole graph is at least the number needed to colour . This means to colour we need at least colours:
The figure below shows a three-colourable graph, which does not contain .