Calculating the lower bound on the chromatic number of a simple graph.

Question

In a homework assignment, I was told to show that if $G$ is a simple graph, then $\chi(G) \geq \frac{\nu^2}{\nu^2 - 2\varepsilon}$, where $\nu(G)$ is the number of vertices in the graph and $\varepsilon(G)$ is the number of edges in the graph (I include this because I've been told the notation is out of date). I've attempted to do this by induction on both the number of vertices and the number of edges (for a given graph on $\nu$ vertices). Neither seems to be working very well. How should I proceed here?

Answer 1

Solving for $\varepsilon$, an equivalent statement is $$ \varepsilon(G) \le \left(1 - \frac1{\chi(G)}\right)\frac{\nu(G)^2}{2}. $$ This follows from Turán's theorem, since $G$ cannot contain a clique on $\chi(G)+1$ vertices.