Chromatic Number

Question

The smallest number of colors needed to color a graph $G$ is called its chromatic number, and is often denoted $\chi(G)$.
Show that if graph $G$ is simple, then $$ \chi \ge \frac{V^2}{V^2 - 2E}. $$

Answer 1

Let $G$ be a graph of order $n$ and size $m$. Suppose that $\chi(G)=k$ and let $C$ be a $k$-coloring of $G$ with color classes $C_1$, $C_2$, . . . , $C_k$ where $|C_i|=n_i$ for $1\leq i\leq k$. The largest possible size of $G$ occurs when $G$ is a complete $k$-partite graph with partite sets $C_1$, $C_2$, . . . , $C_k$ and the cardinalities of these partite sets are as equal as possible or each $|C_i|$ is as close to $n\over k$ as possible for $1\leq i \leq k$. This implies that $m\leq {k\choose 2}\cdot {n^2\over k^2}$ and so $2m\leq{(k-1)n^2\over k}$. So ${n^2\over n^2-2m}\leq {n^2\over n^2-{(k-1)n^2\over k}}=k=\chi(G).$ Thus $\chi(G)\geq {n^2\over n ^2-2m}$.