I came across this question in my textbook, but I am having trouble solving it.
Prove that $\alpha(G) \cdot \omega(G) \leq \frac{n(n+2)}{4}$ when $n$ is even, and $\alpha(G) \cdot \omega(G) \leq \frac{(n+1)^2}{4}$ when $n$ is odd. Here $\alpha(G)$ is the independence number and $\omega(G)$ is the clique number in a graph with $n$ vertices.
I tried to prove this by induction, but got stuck. I would appreciate any help on this!
Note that $\alpha(G) = \omega(\overline{G})$. The problem boils down to maximizing the product $\omega(G)\omega(\overline{G})$. You will need to show that $\omega(G) + \omega(\overline{G}) \le n+1$. Maximizing the sum implies maximizing the product, so assuming equality of the sum leads to $$\omega(G)\omega(\overline{G}) = \omega(G)(n+1 - \omega(G)) = (n+1)\omega(G) - (\omega(G))^2.$$ This is a quadratic (in $\omega(G)$) with a maximum, so find the vertex (of the quadratic function). This is where the product is maximized. What remains is to think about what the product looks like when $n$ is even or odd.