# If a graph G has chromatic number 3, then G contains a subgraph isomorphic to $K_3$?

Is there a theorem that states if a graph has $\chi(G) = n$ then it also contains a subgraph isomorphic to $K_n$?

-
You are trying to compare the chromatic number to the so called clique number. There is a whole literature about this problem. Google should provide relevant information. –  Mariano Suárez-Alvarez May 13 '13 at 22:25

## 2 Answers

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$.

-

Consider the cycle on $5$ vertices.

-
Yes, $\chi(G)=3$ here but no $K_3$. –  coffeemath Jan 29 '13 at 11:56