0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ I have forgotten, what is $d(x)$? $\endgroup$
    – Mankind
    Jun 21, 2015 at 11:00
  • $\begingroup$ Degree of the vertex $x$ $\endgroup$
    – shinzou
    Jun 21, 2015 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, 2015 at 11:01
  • $\begingroup$ @HagenvonEitzen Oh I see I made a small typo, just a moment. $\endgroup$
    – shinzou
    Jun 21, 2015 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, 2015 at 11:03

1 Answer 1

Reset to default
1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ So what I did is also valid use of the PHP. Thank you. $\endgroup$
    – shinzou
    Jun 21, 2015 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, 2015 at 11:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .