Chromatic number on a graph

Question

Let $G$ be any graph with order $p$ and size $q$. Prove that $$χ(G)\ge {p^2 \over p^2-2q}$$

If someone could give me a hint it would be amazing!

Answer 1

Suppose a graph with $v$ vertices has chromatic number $\chi$, so we have a splitting of the vertex set into independent sets of sizes $v_1,\ldots,v_\chi$. Then the number of edges $e$ is at most $$e\leq \sum_{1\leq i<j\leq \chi}v_iv_j\leq \frac{\chi-1}{2\chi}(\sum_i v_i)^2=\frac{\chi-1}{2\chi}v^2 $$ where the middle inequality is something that holds for all real numbers as it is just $\sum_{i<j}(v_i-v_j)^2\geq 0$.