# Handshake problem

I was given the following math puzzle which (I thought) has an interesting solution.

A mathematician and her husband attended a party with $n-1$ other couples. As is normal at parties, handshaking took place. Of course, no one shook their own hand or the hand of the person they came with. And not everyone shook everyone else's hand. But when the mathematician asked the other $2n-1$ people present how many different people's hands they had shaken they all gave a different answer from $0$ to $2n-2$. Question (this is NOT a trick!): How many different people's hands did the mathematician's husband shake?

Can anyone come up with a graph theory solution that uses an induction proof?

-

Let $P_k$ be the person who shook $k$ hands. $P_{2n-2}$ shook hands with everyone but his or her partner, so $P_0$ must have been the partner. Set them aside, leaving $P_1,\dots,P_{2n-3}$ and the mathematician. Each of these remaining people shook hands with $P_{2n-2}$, so within the group that remains each shook one hand fewer: $P_k$ shook $k-1$ hands for $k=1,\dots,2n-3$. By the same reasoning (or by induction) $P_1$ and $P_{2n-3}$ must be a couple. In general we must have $P_k$ and $P_{2n-2-k}$ forming a couple for $k=0,\dots,n-2$. In particular, $P_{n-2}$ and $P_n$ are a couple. This leaves $P_{n-1}$ to be the mathematician’s husband: he shook $n-1$ hands.
In graph-theoretic terms we have a graph $G_n$ with vertices $v_k$ for $k=0,\dots,2n-2$ such that $\deg v_k=k$, and we have an additional vertex $v$ corresponding to the mathematician. The graph is simple (no loops or multiple edges), and it is known that the vertices can be partitioned into $n$ pairs whose members are not adjacent. We wish to show that $v$ is paired with $v_{n-1}$. This is clearly the case when $n=1$, so assume that $n>1$.
Vertex $c_{2n-2}$ is adjacent to every vertex but itself and the one paired with it, so every vertex but the one paired with it has positive degree; thus, $\{v_0,v_{2n-2}\}$ must form a pair. Remove $v_0$, $v_{2n-2}$, and all adjacent edges, and you have a graph $G_{n-1}$ on $2(n-1)$ vertices with mutatis mutandis the same properties. By the obvious induction hypothesis vertex $v$ is paired with the vertex of degree $n-2$ in $G_{n-1}$, which is $v_{n-1}$ in $G_n$, as desired.
This can easily be converted into an induction proof. Let $Q_k$ be the proposition $H_k=P_{k-1}$ when there are $k$ couples present. The base case, $Q_1$ is trivial. Suppose we have $Q_r$ and we want to establish $Q_{r+1}$ - take out the couple $P_0$ & $P_{2n-2}$ and remove their handshakes as Brian explains. You then have a case of $Q_r$ which is already established, and putting the extreme couple back in adds one handshake to the husband and $H_{k+1} = P_k$ –  Mark Bennet May 26 '12 at 4:00