by has at most neighbor, do you mean has at most one neighbor?

CrazyInMath wrote: by has at most neighbor, do you mean has at most one neighbor? Yes. Thank you, I edited the post.

Split the vertices into the maximal unsocial set $A$ and its complement $B$. Observe that $|A|=x$ and $|B|=n-x$. The idea is to double count the edges between $A$ and $B$, so let's define $T=\{(a,b) : a \in A \text{ and } b \in B\}$. Since $A$ is maximal, every $b$ in $B$ must have at least 2 neighbours in $A$, it follows that $|T| \geq 2(n-x)$. On the other side, every pair of vertices in $A$ must have at least $k$ common neighbours in $B$. We deduce that $kx^2 \geq 2k \binom{x}{2} \geq |T|$. Combining the inequalities we get $kx^2 + 2x - 2n \geq 0$ which implies $x \geq \frac{4+\sqrt{4+8nk}}{2k} \geq \sqrt{\frac{2n}{k}}$.