Is there a theorem that states if a graph has $\chi(G) = n$ then it also contains a subgraph isomorphic to $K_n$?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The answer is simply NO, since there are triangle-free graphs with arbitrarily high chromatic number, in virtue of the following lemma:
If $G$ is a triangle-free graph with chromatic number $n$, its Mycelskian $M(G)$ is a triangle free graph with chromatic number $n+1$.