Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
More generally, if $H$ is any induced subgraph, then $\chi(G) \geq \chi(H)$. – Douglas S. Stones Nov 1 '12 at 21:12
up vote 2 down vote accepted

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

share|cite|improve this answer
thanks for help.but that is not a proof although question is obvious. – World Nov 1 '12 at 20:31
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.