El Lema de los Apretones de Manos

Hace unas semanas, publiqué un problema sobre apretones de manos.
Tras comentarlo con un compañero experto en Teoría de Grafos, me dijo que se trataba de una ejemplificación de un resultado muy conocido: El Lema del Apretón de Manos.

Vamos a hablar un poquito de Teoría de Grafos antes de ver este lema.
Como bien comentan en Gaussianos en un post sobre Los Puentes de Königsberg,

Un grafo es básicamente un conjunto no vacío (al menos contiene un elemento) de puntos llamados vértices y un conjunto de líneas llamadas aristas cada una de las cuales une dos vértices.
[...]
Se dice que un grafo es simple si para cualesquiera dos vértices existe a lo sumo una arista que los une.

Una vez que tenemos los ingredientes básicos, vamos a profundizar un poquito más.

En un grafo simple, se llama valencia⁽¹⁾ grado de un vértice al número de aristas que inciden en él.

Por ejemplo, en el Grafo de arriba, la valencia el grado de cada vértice son:

d(V₁)=2, d(V₂)=2, d(V₃)=1, d(V₄)=1.

Bien, ahora sí que tenemos todos los ingredientes necesarios para hablar del Lema de los Apretones de Mano.

Teorema: Sea G un grafo simple (y finito). La suma de las valencias los grados da cada vértice es, exactamente, el doble del número de aristas.
Comprobación: Bueno, en el grafo del ejemplo anterior vemos que el número de aristas es 3 y la suma de todas las valencias los grados es, precisamente, 6.
Demostración: Para demostrar rigurosamente este teorema, basta con darnos cuenta que cada vez que introduzco 1 arista en un grafo, la valencia el grado del vértice inicial y final aumenta en 1 unidad cada uno, luego la suma de valencias grados aumenta 2 unidades por cada arista.

Muy bien, ya tnemos demostrado un teorema de Teoría de Grafos y nos podemos sentir un poco como Euler cuando resolvió el problema de los Puentes de Königsberg (salvando las distancias espacio-temporales). Ahora sí que podemos empezar a hablar de nuestro Lema.

Lema de los Apretones de Manos (Handshake lemma): En un grafo simple, hay un número par de vértices con valencia grado impar (aceptamos el 0 como número par).
Comprobación: En el grafo del ejemplo, hay 2 vértices con valencia grado 1.
Demostración: Vamos a dividir los vértices entre aquéllos con valencia grado par P y aquellos con valencia grado impar I.
El Teorema anterior nos dice que:
Σ_{V∈ P} d(V)+ Σ_{V∈ I} d(V)= 2·(nº de aristas)Luego, esa suma ha de ser PAR. Pero analicemos cada sumando. El primero de ellos, es una suma de números pares (recordemos que P era el conjunto de vértices con valencia grado par), luego es PAR. Por lo tanto, para que todo cuadre, el segundo sumando tiene que ser también par. Pero resulta que el segundo sumando es una suma de impares (I era el conjunto de vértices con valencia grado impar) por lo tanto para que al final sea par, el número de vértices de I ha de ser par.

¿Y cómo ayuda esto al problema de los apretones de mano? Pues basta con identificar a cada persona de la reunión con un vértice, y cada apretón de manos entre 2 personas, corresponde a una arista que une lso vértices correspondientes.

Tito Eliatron Dixit.

---

Actualización:
⁽¹⁾El término valencia, por lo visto, está tratando de ser eliminado por los expertos en la materia, en detrimento de grado, pues valencia recuerda a los elementos químicos.