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