Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.