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?
Best Answer
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$.