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$.


1 Answer 1


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, 2013 at 13:54
  • $\begingroup$ @vonbrand Hopefully I should make sure the link does not break. $\endgroup$
    – Jernej
    Apr 19, 2013 at 16:04

Not the answer you're looking for? Browse other questions tagged .