This question already has an answer here:

Prove that $\chi(G) \cdot \chi(\bar{G})\geq n$

$\chi(G)$: number of colors required for a graph $G$.

Here $\bar{G}$ is a graph that consists of all the edges that are not in $G$.


marked as duplicate by TMM, Stefan Hansen, Davide Giraudo, Lord_Farin, user642796 Apr 22 '13 at 11:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Answer of your question is available here

  • 2
    $\begingroup$ Please summarize the proof here, so it won't get lost if the link breaks. $\endgroup$ – vonbrand Apr 19 '13 at 13:54
  • $\begingroup$ @vonbrand Hopefully I should make sure the link does not break. $\endgroup$ – Jernej Apr 19 '13 at 16:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.