Prove that $|V(G)| \leq \alpha(G)\cdot \omega(G)$ (clique number, independency number)

Question

How can you prove that $|V(G)| \leq \alpha(G)\cdot \omega(G)$?

(Number of vertices in a graph is less than or equal to the graph's clique number * its independency number.)

Answer 1

This is false, consider the self complementary graph $C_5$

Answer 2

There is no less than, equal or greather than relation between $|V(G)|$ and $\alpha(G)\cdot \omega(G)$, because for $C_7$ it's $>$, for $K_{n,n}$ it's $=$ and for $P_3$ it is $<$.

Answer 3

If you build a random graph by taking e.g. 10'000 vertices and for every pair throwing a (fair) coin to decide whether to put the edge or not, you probably end up having alpha < 3 log |V| (and same for omega by symmetry), so alpha * omega < 9 (log |V|)^2.

There's however a conjecture that if you only look at graphs with no induced copy of some graph H (no matter how you choose H), then alpha * omega > |V|^c where c is some positive constant depending only on H. (Note that the above example isn't a counter-example to that). It's a very hard conjecture, only confirmed for very small H -- but not for H being the cycle on five vertices, for example.