[Solved]: Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

In fact, something stronger is true: if you can approximate maximum clique within $n^{1-epsilon}$ for some $epsilon > 0$ then P=NP. This is because for every $epsilon > 0$ there is a polytime reduction $f_epsilon$ that takes an instance $varphi$ of SAT and returns an instance $(G,cn)$ of maximum clique such that:

1. If $varphi$ is satisfiable then $G$ has a $cn$-clique.
2. If $varphi$ is not satisfiable then $G$ has no $cn^{1-epsilon}$-clique.

If you could approximate maximum clique within $n^{1-epsilon}$ you would be able to distinguish the two cases (exercise), and so to decide whether $varphi$ is satisfiable or not. The reduction uses the PCP theorem as a first ingredient. Given the PCP theorem it is not hard to give a similar reduction with a constant gap, and with some effort to give a reduction with a gap of $n^epsilon$ for some $epsilon > 0$. The reduction claimed above, which has a gap of $n^{1-epsilon}$ for every $epsilon>0$, is much harder. See lecture notes of Guruswami and O’Donnell for the constant gap, and lecture notes of Scheideler for the $n^epsilon$ gap.