Let $G$ be a simple graph such that $|V|\ge 5$, also $x,y$ are vertices that aren't adjacent. Prove that if $d(x),d(y)\ge \frac {n+1}2$, then $x,y$ has at least $3$ common neighbors.
My attempt:
$d(x)+d(y)=n+1$ these are the pigeons.
There are other than $x,y$ more $n-2$ vertices, these are the pigeonholes.
So from the pigeon hole principle there are at least $3$ common neighbors to $x,y$.
But I saw a proof that each time remove a common vertex to show that there are at least $3$ neighbors, i.e. get to where I got, then remove the common vertex, then there are $n-1$ neighbors to $x,y$, and $n-3$ vertices, and again $n-3$ neighbors and $n-4$ vertices.
Why it's not enough to use the PHP once like I did?
Usually, the pigeon-hole principle is stated in a form that one can merely conclude from the fact that there are $p$ pigeons and $h$ holes with $p>h$ that there exists at least one hole with at least two pigeons in it. Therefore, the three-step procedure is employed to show the result here.
However, if one knows that in each hole there fit at most two pigeons, then the principle can be formulated more explicitly so that one can conclude that at least $p-h$ holes contain two pigeons. Whether this is considered a variant or a consequence of the pigeon-hole princoiple is in the eye of the beholder. (I tend to the second view, though it is not a deep result)