Deje $P_k$ ser la persona que sacudió $k$ manos. $P_{2n-2}$ estrechó la mano de todos, pero su pareja, por lo $P_0$ debe haber sido la pareja. Déjelos a un lado, dejando $P_1,\dots,P_{2n-3}$ y el matemático. Cada una de estas personas que quedan estrecharon las manos con $P_{2n-2}$, por lo que dentro del grupo que sigue cada sacudió una mano menos: $P_k$ sacudió $k-1$ manos para $k=1,\dots,2n-3$. Por el mismo razonamiento (o por inducción) $P_1$ $P_{2n-3}$ debe ser una pareja. En general debemos tener $P_k$ $P_{2n-2-k}$ la formación de un par de $k=0,\dots,n-2$. En particular, $P_{n-2}$ $P_n$ son pareja. Esto deja a $P_{n-1}$ a ser el matemático del marido: él sacudió $n-1$ manos.
En teoría de grafos términos tenemos un gráfico de $G_n$ con vértices $v_k$ $k=0,\dots,2n-2$ tal que $\deg v_k=k$, y contamos con un vértice $v$ correspondiente para el matemático. La gráfica es sencilla (sin bucles o varios bordes), y se sabe que los vértices se puede dividir en $n$ parejas cuyos miembros no son adyacentes. Queremos mostrar que $v$ está vinculado con $v_{n-1}$. Este es claramente el caso de al $n=1$, por lo que asumir que $n>1$.
Vértice $c_{2n-2}$ es adyacente a cada vértice, pero en sí y el uno emparejado con ella, por lo que cada vértice, pero el uno emparejado con ella ha positivos grado; por lo tanto, $\{v_0,v_{2n-2}\}$ debe formar un par. Quitar $v_0$, $v_{2n-2}$, y todas las aristas adyacentes, y usted tiene un gráfico de $G_{n-1}$ $2(n-1)$ vértices con mutatis mutandis, las mismas propiedades. Por la obvia hipótesis de inducción vértice $v$ está vinculado con el vértice de grado $n-2$$G_{n-1}$,$v_{n-1}$$G_n$, como se desee.
