Problem in Chromatic Number The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G).  lemma : If G has a degree sequence  $ (d_1, d_2, ... , d_v) $ with $ d_1 \ge d_2 \ge ... \ge d_v $ then $$ \chi \le max_i \; min\{d_i + 1 , i\}. $$
main question : Using lemma, Show that :
 a) $ \; \chi \le \lceil\sqrt{2E}\rceil $ 
 b) $ \; \chi(G) + \chi(G^c) \le V + 1$
 A: The lemma is true (it reflects the greedy coloring algorithm), but
the first statement is false: let $G$ be $K_5$, then $\chi(G)=5$, and $G$ has 10 edges.
Now $\chi\leq\sqrt{2E}$ $\iff$ $5\leq\sqrt{20}$ and the last inequality is not true.
For the second statement, let $j$ be the lowest index that maximizes $min(d_i+1,i)$,
let $a=min(d_j+1,j)$, so $a\leq j$ and $a\leq d_j+1$.
Let $n$ be the number of vertices of $G$.
$G^c$ has degree sequence $n-1-d_n\geq\ldots\geq n-1-d_1$, so the $i$th element of the
degree sequence is $n-1-d_{n-i+1}$.
Let $k$ be the lowest index that maximizes $min(n-1+d_{n-i+1}+1,i)$,
let $b=min(n-d_{n-k+1},k)$, so $b\leq k$ and $b\leq n-d_{n-k+1}$.
Let $\chi=\chi(G)$ and $\chi'=\chi(G^c)$.
The lemma tells us the $\chi\leq a$ and $\chi'\leq b$.
Case 1: $j+k\leq n+1$, then $\chi+\chi'\leq a+b\leq j+k\leq n+1$.
Case 2: $j+k>n+1$, then $j>n+1-k$, so $d_j\leq d_{n+1-k}$.
Now $\chi+\chi'\leq a+b\leq d_j+1+n-d_{n-k+1}\leq n+1$.
Solution for modified first problem.
Again let $j$ be the first index that realizes the maximum,
so again $\chi\leq j$ and $\chi\leq d_j+1$.
Then $2E=\sum d_i\geq d_1+\ldots+d_j\geq jd_j\geq\chi(\chi-1)$.
But then $\chi=\lceil\sqrt{\chi(\chi-1)}\rceil\leq\sqrt{2E}$.
