Let \( k = \chi(G) \) and \( \bar{k} = \chi(\bar{G}) \). Consider a \(k\)coloring of \(G\) and denote by \(n_i \) the number of vertices given the color \(i\) for \( i = 1,2, \ldots, k \). Let \(j \in \left\{ {1,2, \ldots ,k} \right\}\) be such that \({n_j} = \max \left\{ {{n_1},{n_2}, \ldots ,{n_k}} \right\}\). Clearly, we have \(n = \sum\limits_{i = 1}^k {{n_i}} \), hence \[{n_j} \ge \frac{n}{k}.\] If two vertices are given the same color in \(G\), then the edge they determine must be in the complementary graph \( \bar{G} \) and they must be given different colors in \( \bar{G} \). It follows that \[\bar k \ge {n_j}.\] Therefore, \(\bar k \ge \dfrac{n}{k}\) and \[\boxed{\chi \left( G \right) \cdot \chi \left( {\bar G} \right) \ge n}.\] Now, the arithmeticgeometric mean inequality implies that \[\chi \left( G \right) + \chi \left( {\bar G} \right) \ge 2\sqrt {\chi \left( G \right) \cdot \chi \left( {\bar G} \right)} \ge 2\sqrt n \] and the result follows.
To see that the equality can be achieved, let \( n = m^2 \). Divide the \( n \) vertices into \( m \) groups, where the vertices in each group are given the same color (so \( m \) colors are used). The edges of \( G \) are defined to be those joining vertices of different colors. Clearly, \[\chi \left( G \right) = \chi \left( {\bar G} \right) = m = \sqrt n ,\] so \[\chi \left( G \right) + \chi \left( {\bar G} \right) = 2\sqrt n .\]
