# Chromatic Number Identity Involving Edges

I'm trying the prove the following:

Let $G$ be a simple graph with $m$ edges. Show that $\chi(G)\leq \frac{1}{2}+\sqrt{2m+\frac{1}{4}}.$

A very minute bit of algebraic manipulation shows that this is equivalent to proving $$\chi(G)(\chi(G)-1)\leq 2m.$$ From here I am a bit stuck. Could someone suggest a direction to head in?

Please no full solutions, just hints.

-

## 2 Answers

HINT: A little more manipulation turns it into $$m\ge\binom{\chi(G)}2\;,$$ which can be understood as saying that there must be at least as many edges as there are pairs of colors in a minimal coloring.

-

The fact that $G$ has chromatic number $\chi(G)$ means that you can partition vertices of the graph into $\chi(G)$ disjoint classes such that vertices in the same class have no neighbours.

Can you count the number of edges with respect to such a partition?

-