Show that: $\chi(G) + \chi(\overline{G}) \leq |V| + 1$

Question

Show that: $\chi(G) + \chi(\overline{G}) \leq |V| + 1$

I have problem with starting with this task. I have already done similar ones like for example $\chi(G) * \chi(\overline{G}) \geq |V|$, but I can't really find the proper way of thinking to solve the task mentioned at the beginning.

Any tips?

Answer 1

Hint. This can be proved by induction on $n(G)$, the number of vertices.

Choose any vertex $v$ of $G$. By the inductive hypothesis we have: $$\chi(G-v)+\chi(\overline{G-v})\le n(G-v)+1=n(G)\tag1$$ and we also have $$\chi(G)\le\chi(G-v)+1\tag2$$ and $$\chi(\overline G)\le\chi(\overline{G-v})+1\tag3$$ whence $$\chi(G)+\chi(\overline G)\le n(G)+2.\tag4$$ All we have to do now is show that equality can't hold in $(4)$. Well, for equality to hold in $(4)$, we must have equality in $(1)$, $(2)$, and $(3)$. But then . . .

Further hint:

Equality in $(2)$ implies $\deg_G(v)\ge\chi(G-v)$