Handshaking puzzle

Question

Problem: At a party there are $n$ people, some people give each other a hand. After the party everyone writes down on a piece of paper how many people he/she shook hands with. It turns out there are $n-1$ different numbers written down.Prove that there were two people at the party, such that every other person has shaken both of their hands or none of their hands.

My attempt: I want to try to prove this with induction on $n$.

Suppose that $n=3$. Then there are two different numbers written down. Without loss of generality, suppose that person 1 ($=p_1$) and person 2 ($=p_2$) have the same amount of handshakes, which is different from the amount of handshakes of $p_3$. Suppose that $p_3$ did a handshake with $p_1$, and not with $p_2$. In order for $p_2$ to get the same amount of handshakes, $p_2$ must shake hands with either $p_1$ or $p_3$. We said that $p_3$ didn't shake hands with $p_2$, so its only possible that $p_1$ shakes hands $p_2$, but then the difference in handshakes between $p_1$ and $p_2$ doesn't change, so contradiction. Conclusion: $p_3$ has either given both $p_1$ and $p_2$ a handshake or none of them.This concludes the induction basis.

Now we suppose that the situation where there are $n$ people, $n-1$ different numbers and $2$ people with the given constraints hold. Now we add another person to the party. The $n-1$ different numbers are numbers from the set $\{0,1,\ldots,n-1\}$ and we see that one number is not used. I will now prove that the number not used is either $0$ or $n-1$. Suppose that the number not used is not $0$ or $n-1$. Then we have a list with both $0$ and $n-1$ on it. But that means that there is a person that has shaken hands with no one and a person that has shaken hands with everyone (except themselves of course), so a contradiction.

My struggle: So at this point I realize that if the new person shakes hands with no one or everyone except themselves, the induction step holds (the same 2 people from the previous situation are the $2$ people in the new situation). But I am not sure how I can show this.

Does someone have suggestions for me about how to prove it/do it differently? I would love the hear feedback/get help.

Answer 1

It is sometimes easier to go in the opposite direction, using the contrapositive. So instead of:

Property true for $n-1$ implies property true for $n$.

you instead prove:

Property false for $n$ implies property false for $n-1$.

The above are equivalent, though if you now chain them together you get more of an infinite descent argument (and a proof by contradiction) than an induction argument.

The $n$ people shake hands somewhere from $0$ times to $n-1$ times. Clearly it is impossible for the party to contain someone who shakes no hands and someone who shakes hands with everybody, so the $n-1$ distinct numbers that are written down are either $0,...,n-2$ or $1,...,n-1$, and one of the numbers is written twice.

Suppose (for a contradiction) the two people who wrote the same number did not shake hands with exactly the same set of other people. Clearly that means they can't have written $0$ or $n-1$. Now remove the person who did write $0$ or $n-1$ from the party, and show that you now have a party of $n-1$ people who wrote $n-2$ numbers, and the two who wrote the same number did not shake hands with exactly the same set of other people.

So you can now repeat the argument until there are only $3$ or even $2$ people left. In that case the condition is impossible - it is not possible that the two people who shook the same number of hands did so with a different set of people. Therefore the assumption that this is possible in the party of $n$ people is also false.

Answer 2

Rewrite the claim in the graph-theoretical form below. I shall use induction and prove the result directly.

Proposition. Let $n\geq 3$ be an integer, and $G(V,E)$ a simple graph on $n$ vertices. Suppose that there are exactly $n-1$ distinct values for the degrees of the vertices of $G$. Write $N_G(v)$ for the neighbor of $v\in V$ in $G$. Then, there are two distinct vertices $x$ and $y$ of $G$ such that $$N_G(x)\setminus\{x,y\}=N_G(y)\setminus\{x,y\}\,.$$

We induct on $n$. The case $n=3$ is proven by the OP. Let now $n>3$. Since the degree of each vertex of $G$ can be $0$, $1$, $2$, $\ldots$, $n-1$, there must exist a vertex of degree $0$ or $n-1$.

Case I: There exists a vertex $u$ of degree $0$. If there is another vertex $v$ of degree $0$, then $u$ and $v$ have the same (empty) neighbor, and we are done. If not, then removing $u$ from $G$, we obtain a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By induction hypothesis, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$ since for each vertex in $H$, its neighbor in $H$ is the same as its neighbor in $G$.

Case II: There exists a vertex $u$ of degree $n-1$. Note that two vertices cannot both have degree $n-1$ (otherwise, the minimum degree of $G$ is $2$). By removing $u$, we get a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By induction hypothesis, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$, since for each vertex in $H$, its neighbor in $G$ is the same as its neighbor in $H$ annexing $u$.

---

You can also prove the proposition by contradiction without induction. Let $G$ be the smallest graph (i.e., with the smallest value of $n$) that satisfies the hypothesis but not the conclusion of the proposition. Clearly, $n>3$. As before, $G$ has a vertex of degree $0$ or $n-1$.

Case I: There exists a vertex $u$ of degree $0$. Since $G$ violates the conclusion of the proposition, every other vertex of $G$ has degree at least $1$. By removing $u$ from $G$, we obtain a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By minimality of $G$, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$, since for each vertex in $H$, its neighbor in $H$ is the same as its neighbor in $G$. This is a contradiction.

Case II: There exists a vertex $u$ of degree $n-1$. Note that two vertices cannot both have degree $n-1$ (otherwise, the minimum degree of $G$ is $2$). By removing $u$, we get a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By minimality of $G$, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$, since for each vertex in $H$, its neighbor in $G$ is the same as its neighbor in $H$ annexing $u$. This is also a contradiction.

---

Remark. My two proofs and Jeap Scherphuis's proof are essentially the same.