How I can prove that in given simple graph G in n vertices: $$\chi(G) + \chi(\overline{G}) \leq n + 1.$$ Where $\chi$ is chromatic number.
I tried to do like that:
$$\chi(G) \leq \Delta(G) + 1 \;; \; (\Delta\text{ is max degree)}$$ $$\chi(\overline{G}) \leq \Delta(\overline{G}) + 1$$ $$\chi(G) + \chi(\overline{G}) \leq \Delta(G) + 1 + \Delta(\overline{G}) + 1$$ $$\Delta(G) + \Delta(\overline{G}) = n-1\;; \text{because graph is simple}$$ $$\chi(G) + \chi(\overline{G}) \leq n - 1 + 1 + 1$$ $$\chi(G) + \chi(\overline{G}) \leq n + 1$$ But I think I'm wrong.