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$.
If $G$ has an induced $K_n$, show the chromatic number $\chi(G)\ge n$.
0
$\begingroup$
graph-theory
coloring
-
1More generally, if $H$ is *any* induced subgraph, then $\chi(G) \geq \chi(H)$. – 2012-11-01
1 Answers
2
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$.
-
0Is 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. – 2012-11-01