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
    thanks for help.but that is not a proof although question is obvious.2012-11-01
  • 1
    @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.2012-11-01
  • 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