7
$\begingroup$

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 2

7

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.

4

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?