Inequalities between chromatic number and the number of vertices I am currently doing exercises from graph theory and i came across this one that i can't solve. Could anyone give me some hints how to do it?
Prove that for every graph G of order $n$ these inequalities are true:
$$2 \sqrt{n} \le \chi(G)+\chi(\overline G) \le n+1$$
 A: To prove that $\chi(G)+\chi(\overline G)\ge2\sqrt n$: Suppose $G$ and $\overline G$ have been colored with $\chi(G)$ and $\chi(\overline G)$ colors, respectively. Map each vertex to an ordered pair of colors, namely, $v\mapsto ($color of $v$ in $G,$ color of $v$ in $\overline G)$. Note that this map is injective, showing that $n\le\chi(G)\chi(\overline G)$, whence $\sqrt n\le\sqrt{\chi(G)\chi(\overline G)}\le\frac{\chi(G)+\chi(\overline G)}2$ by the inequality between the geometric and arithmetic means.
The inequality $\chi(G)+\chi(\overline G)\le n+1$ can be proved induction on $n$. Let $G$ be a graph of order $n+1$ and let $v\in V(G)$. By the induction hypothesis, $\chi(G-v)+\chi(\overline G-v)\le n+1$; we have to show that $\chi(G)+\chi(\overline G)\le n+2$. Inasmuch as $\chi(G)\le\chi(G-v)+1$ and $\chi(\overline G)\le\chi(\overline G-v)+1$, the conclusion clearly holds if either $\chi(G)=\chi(G-v)$ or $\chi(\overline G)=\chi(\overline G-v)$. On the other hand, if $\chi(G)>\chi(G-v)$ and $\chi(\overline G)>\chi(\overline G-v)$, then $v$ must be joined to $\chi(G-v)$ many vertices by edges of $G$, and to $\chi(\overline G-v)$ many vertices by edges of $\overline G$, which implies that $\chi(G-v)+\chi(\overline G-v)\le n$ and so $\chi(G)+\chi(\overline G)\le n+2$.
A: For the right hand inequality, use induction:
The case $n=1$ is clear as $\chi(G)=\chi(\overline G)=1$.
If $n>1$, select a vertex $v\in G$.
By induction, we may assume that $\chi(G-v)+\chi(\overline {G-v})\le n$.
Clearly, $\chi(G)\le \chi(G-v)+1$ and $\chi(\overline G)\le\chi(\overline{G-v})+1$.
If the degree $\rho(v)$ of $v$ in $G$ is $\rho(v)<\chi(G-v)$, we find that no additinal colour is needed for $G$, i.e. $\chi(G)=\chi(G-v)$ and hence $$\chi(G)+\chi(\overline G)\le \chi(\overline G)+\chi(\overline{G-v})+1\le n+1.$$
With the same argument for the complemntary graph, if $\rho(v)>(n-1)- \chi(\overline{G-v})$, we have $\chi(\overline{G})=\chi(\overline{G-v})$ and hence again $$\chi(G)+\chi(\overline G)\le \chi(\overline G)+1+\chi(\overline{G-v})\le n+1.$$
Remains the case that $\rho(v)\ge\chi(G-v)$ and $\rho(v)\le (n-1)-\chi(\overline{G-v})$. But then $\chi(G-v)+\chi(\overline{G-v})\le n-1$ and hence 
$$\chi(G)+\chi(\overline G)\le \chi(\overline G)+1+\chi(\overline{G-v})+1\le n+1.$$
