Let G be a graph of order n. Prove that:?

Due to lack of foreign alphabets and overlines, I'll use
X(G) = chromatic number of G, and
G' = complement of G.
Also,
n=|V| = number of vertices.

Given G=(V,E), to prove X(G).X(G')>=n

We'll need to know the following prerequisites:
Brook's theorem, which says that X(K)=n, or chromatic number of a complete graph is n, or all vertices of a complete graph have different colours.
Ceiling function ceiling(x) is the smallest integer that equals or exceeds x.


Let k=X(G), then V can be subdivided into k disjoint subsets. Since all vertices in each of the k subsets have the same colour, there can be no edge (in G) between vertices of the same subset. This implies that the vertices of each subset forms a complete graph in G' (the complement).

From n vertices that form k subsets, There is at least one subset P that has at least ceiling(n/k) vertices. By Brook's theorem, we know that X(P)=(n/k), which can be reduced to
X(P).k=n........(1)
Also, it could happen that another subset Q can exist such that |Q|>|P|, so
X(P)<=X(G').........(2)

Combining (1) and (2), we conclude that X(G').k>=n.

Substitute k=X(G), we get, finally,
X(G').X(G)>=n