A theorem of Gaddum and Nordhaus
Given a graph G with n vertices. Let G' be the complementary graph of G, which has the same vertex set as G and two vertices are adjacent in G' iff they are not adjacent in G. Let \chi(G) and \chi(G') be the chromatic number of G and G'. In 1956, two mathematicians Edward Alfred Nordhaus and Jerry William Gaddum obtained the following estimates: (i) 2\sqrt{n} <= \chi(G) + \chi(G') <= n + 1 (ii) n <= \chi(G)\chi(G') <= ((n + 1)/2)^2 The result was written in the paper "On complementary graphs", which was published in The American Mathematical Monthly. To show that \chi(G)\chi(G') >= n, we assume that the vertices of G can be colored by k colors and the vertices of G' can be colored by k' colors. For each vertex v, let G(v) be the color of v in G and G'(v) be the color of v in G'. Since for any two different vertices v, u, either v is adjacent to u in G (which means that G(v) and G(u) must be different) or...
