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?

  • $\begingroup$ I have forgotten, what is $d(x)$? $\endgroup$ – Mankind Jun 21 '15 at 11:00
  • $\begingroup$ Degree of the vertex $x$ $\endgroup$ – shinzou Jun 21 '15 at 11:01
  • $\begingroup$ I assume $d(x)$ is the degree of vertex $x$. However, there is just one moe pigeon than there are holes, hence how do you find three (and not just on) common neighbours? $\endgroup$ – Hagen von Eitzen Jun 21 '15 at 11:01
  • $\begingroup$ @HagenvonEitzen Oh I see I made a small typo, just a moment. $\endgroup$ – shinzou Jun 21 '15 at 11:02
  • $\begingroup$ A neighbor of $x$ is (in your definition) just a vertex $v$ for which there is a path $x \leftrightarrow v$? And "simple" also means that $G$ is connected? $\endgroup$ – Stefan Mesken Jun 21 '15 at 11:03

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)

| cite | improve this answer | |
  • $\begingroup$ So what I did is also valid use of the PHP. Thank you. $\endgroup$ – shinzou Jun 21 '15 at 11:12
  • 1
    $\begingroup$ @kuhaku That may depend on the exact formulation of the principle in your repertoire. The set-theoretic formulation "If $|A|< |B|$ then any map $f\colon A\to B$ fails to be onto and any $f\colon B\to A$ fails to be injective" is in fact just a restatement of the definition of "$<$", whereas any (including your) refinement using numbers and arithmetic requires (short) proof. $\endgroup$ – Hagen von Eitzen Jun 21 '15 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.