0
$\begingroup$

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

  • 1
    More generally, if $H$ is *any* induced subgraph, then $\chi(G) \geq \chi(H)$.2012-11-01

1 Answers 1

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

  • 0
    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.2012-11-01