show that χ(G)≤√(2|E|)

Question

I was given an Homework exercise where I need to show that χ(G)≤√(2|E|)
So far I've manged to prove that:
1. χ(G)+χ(G′)≤n+1
2. χ(G)≤maximin{di,i}

Now I tried using (1) because I know that there's a link between n+1 and |E| but then I was left with G'...
Can someone help solve this? Thank you!

Answer 1

For a clique $K_n$ you have $$n = \chi(K_n) \not\leq \sqrt{2\big|E(K_n)\big|} = \sqrt{n(n-1)},$$ in other words that inequality is not true. However, you can prove $$\chi(G)\big(\chi(G)-1\big) \leq 2\big|E(G)\big|.$$

Hint:

• Imagine there is no edge between some pair of different colors, what could you do?

I hope this helps $\ddot\smile$