TITLE: Showing that $n \leq \chi(G)\chi(G')$ and $\chi(G') + \chi(G) \geq 2\sqrt n$.
QUESTION [0 upvotes]: Let $n$ be the number of vertices of $G$. Recall that $G'$ denotes the complement of $G$. Show that
  a) $n \leq \chi(G)\chi(G')$ and therefore,
  b) $\chi(G') + \chi(G) \geq 2\sqrt n$.

This question was on my graph theory exam and I didn't know how to approach solving it.
Any tips on how to approach this would be greatly appreciated!

REPLY [1 votes]: So Given a coloring c and c' of G and G' using $\chi(G)$ and $\chi(G')$ colors, we get a coloring for the complete graph $G\cup G'$ by associating a vertex u the color $(c(u),c'(u))$. And so $n \leq \chi(G)\chi'(G)$. 
Now, $(\chi(G)-\chi'(G))^2 \geq 0$ so $\chi(G)^2-2\chi(G)\chi'(G)+\chi'(G)^2\geq0$ so $\chi(G)^2+2\chi(G)\chi'(G)+\chi'(G)\geq 4\chi(G)\chi'(G)$ so $(\chi(G)+\chi'(G))^2\geq 4n$ so $\chi(G)+\chi'(G) \geq 2\sqrt{n}$ !
{"set_name": "stack_exchange", "score": 0, "question_id": 3181764}