For each vertex $v$ there are $d = \deg v$ neighbours and $n-1-d$ non-neighbours. Together they account for $\binom {d} {2} + \binom {n-1-d} {2} \geq \left \lceil \dfrac {(n-1)(n-3)} {4} \right \rceil$ configurations of interest. Thus in total there are at least $n \left \lceil \dfrac {(n-1)(n-3)} {4} \right \rceil$ such configurations. Since there are $\binom {n} {2} = \dfrac {n(n-1)} {2}$ ways to choose points $A,B$, to at least one pair correspond at least $\dfrac {n \left \lceil \dfrac {(n-1)(n-3)} {4} \right \rceil} {\dfrac {n(n-1)} {2}} = \left \lfloor \dfrac {n-2} {2} \right \rfloor$.

This problem is a restatement of this problem. Which problem is the real #4?

This on page 2 has the problem as There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\left\lfloor\frac{n}{2}\right\rfloor-1$ of them, each of whom either knows both or else knows neither of the two. Assume that knowing is a symmetric relation, and that $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$. It's a different problem statement from Kalva, so it's probably right, but I don't know if I'd trust it enough to put it in the contest section.

Mrdavid445 wrote: There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\left\lfloor\frac{n}{2}\right\rfloor-1$ of them, each of whom either knows both or else knows neither of the two. Assume that knowing is a symmetric relation, and that $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$. Can anyone tell some good solution??