I'm aware of the above theorem — namely that if a graph G contains a complete subgraph on t vertices, then the chromatic number is AT LEAST t. But, I'm wondering if anyone can show me some example graphs which contains some complete subgraph on t vertices, and the chromatic number is GREATER than t.
In other words, I'm wondering why the $\ge$ sign in the theorem cannot simply be replaced by an = sign. Thanks.
Best Answer
Note that $K_t$ is contained in $K_{t+1}$, which has chromatic number $t+1$.