El curioso Lema del Apretón de Manos

El post de esta semana lo vamos a empezar con una afirmación que a primera vista puede resultar extraña:

En una fiesta, el número de personas que estrecha la mano a un número impar de personas, es siempre un número par

La explicación del concepto es muy sencilla, y para ello nos vamos a apoyar en la Teoría de Grafos.

Como muchos ya sabéis, la Teoría de Grafos es una rama de las matemáticas perteneciente a la denominada Matemática Discreta. Fue creada por Euler a partir del famosísimo problema de Los puentes de Königsberg y tiene muchas aplicaciones cotidianas, desde la optimización de rutas de reparto hasta aplicaciones en informática o incluso en estudios genéticos.

Para hacernos una idea de su funcionamiento, vamos a simplificarlo mucho todo, dando un par de definiciones elementales.

Un grafo es un conjunto de vértices que se unen mediante aristas, las cuales describen relaciones entre los vértices

El grado de un vértice, es el número de aristas que salen o llegan a ese vértice concreto

Por lo tanto, ya estamos en condiciones de enunciar un teorema:

Sea G un grafo. La suma de los grados de cada vértice es el doble del número de aristas

Sin entrar en rigurosidad matemática, la idea intuitiva de la demostración es realmente sencilla. Toda arista comienza y termina en un vértice, por lo tanto hay dos vértices por arista, es decir, la suma del grado de los vértices es el doble que el número de aristas.

Tras este teorema, podemos afinar más y enunciar el siguiente resultado importante, conocido como Lema de Handshake o del Apretón de Manos:

En un grafo, siempre hay un número parde vértices con grado impar (tomando el 0 como un número par)

Nuevamente, vamos a realizar un simple esbozo de la demostración. Sabemos por el resultado anterior, que la suma de los grados de los vértices es el doble que el número de aristas, por lo tanto la suma de los grados de los vértices es un número par, ya que el doble de cualquier número siempre es un valor par.

Por otro lado, separamos los vértices entre los que tienen grado par y grado impar. La suma de los de grado par da como resultado un valor par de forma trivial. Entonces, sabiendo que al aplicar el otro sumando, el resultado tiene que ser par, ese sumando tiene que ser necesariamente par (la suma de dos valores pares siempre es par. La suma de un valor par y otro impar, es siempre impar).

Por lo tanto, la suma de los grados de los vértices de grado impar, es par.

Entiendo que con tanto par e impar, esto parezca un poco trabalenguas, pero realizando un esquemita con los pasos, se entiende muy fácil.

Por fin, aplicando este Lema, ya estamos en condiciones de razonar la veracidad de la afirmación del principio del post.

Si tomamos a las personas como vértices, y la acción de darse la mano como arista (puesto que es una acción bidireccional, realizada por dos personas o en este caso vértices), podemos afirmar que, aplicando el Lema de Handshake, el número de personas que dan la mano a un número impar de persona, es par.

@JcVirin