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?
 A: 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.
