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

Prove that any graph $G$ with $n$ vertices and $ \chi(G)=k$ has a subgraph $H$ such that $ H \simeq \overline{K_p}$ where $p=n/k$ and $K_p$ is the complete graph with $n/k$ vertices.

My attempt: Because $ \chi(G)=k$ it must be $G \subseteq K_{p_1 p_2 \cdots p_k} $ where $\displaystyle{\sum_{j=1}^{k} p_j =n}$.

Can I consider now that $ p_j =n/k$ for all j?

If no then the other cases is to have $ p_j >n/k$ for some $j \in \{1, \cdots ,k\}$.

But now how can I continue?

share|cite|improve this question
Someone?? I really need this. – passenger Feb 3 '12 at 22:21
You just asked an hour ago. You can't be upset that there's no answer yet. – Graphth Feb 3 '12 at 22:37
@Graphth: I am not upset. Sorry for being so hurry. – passenger Feb 3 '12 at 22:46
I don't understand the question. There is no reason to believe that $n/k$ is an integer. If it isn't, then what is meant by a graph with a fractional number of vertices? Also, what is meant by that bar over the $K_p$? I thought it might mean complement, but complement with respect to what? – Gerry Myerson Feb 3 '12 at 23:25
The color classes are independent sets of average size n/k. – Louis Feb 3 '12 at 23:40
up vote 3 down vote accepted

If $\chi(G) = k$, it means we can color the graph with $k$ colors, $c_1, \ldots, c_k$. Each color class, $c_i$, consists of some vertices $V_i$. Necessarily, the vertices in $V_i$ are independent, or we could not color them all the same color, $c_i$.

Now, assume that every color class contains less than $n / k$ vertices. Then the total number of vertices in the graph is $|G| < k \cdot (n/k) = n$. This isn't possible since we assume $|G| = n$. Therefore, some color class contains at least $n / k$ vertices. Since the vertices in a color class are independent, we have an independent set of size at least $n / k$.

share|cite|improve this answer
So, OP wants the complement of $H$ to be $K_p$, not, as written, $H$ to be the complement of $K_p$. I think you have successfully decoded the question! – Gerry Myerson Feb 4 '12 at 5:05
Thank's for the answer Graphth! I had a mental block. – passenger Feb 4 '12 at 12:37

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.