# If $G$ has an induced $K_n$, show the chromatic number $\chi(G)\ge n$.

How to show that if G has an induced subgraph which is a complete graph on n vertices, then the chromatic number is at least $\chi(G)\ge n$.

• More generally, if $H$ is any induced subgraph, then $\chi(G) \geq \chi(H)$. – Douglas S. Stones Nov 1 '12 at 21:12

Consider coloring such an induced subgraph, say $H$. Clearly, since $H = K_n$, you will needed $n$ colors to color $H$. However, $\chi(G) \geq \chi(H)$, because $G$ includes some other vertices and edges built on top of $H$. Hence, $\chi(G) \geq n$.
• @World Not sure how detailed you want the proof. If you ensist, consider a particular "least" coloring function of $G$, and note that it must color $H$ in at least $n$ colors, that would be more formal language but with the same idea. – gt6989b Nov 1 '12 at 20:34
• Is it obvious that you need at least $n$ colours to properly colour $K_n$? (If you use fewer, than there are two adjacent vertices with the same colour.) Hence $\chi(K_n) \geq n$, which is all you need for the proof. – Douglas S. Stones Nov 1 '12 at 21:18