Lema del apretón de manos

Carta Común · N.º 459845

En teoría de grafos, el lema del apretón de manos es la afirmación de que, en todo grafo finito no dirigido, el número de vértices que tocan un número impar de aristas es par. Por ejemplo, si hay un grupo de personas que se dan la mano, el número de personas que dan la mano a un número impar de otras personas es par.​ El lema del apretón de manos es una consecuencia de la fórmula de la suma de grados, también llamada a veces lema del apretón de manos,​ según la cual la suma de los grados (el número de veces que se toca cada vértice) es igual al doble del número de aristas del grafo. Ambos resultados fueron demostrados por Leonhard Euler (1736) en su famoso artículo sobre los Siete Puentes de Königsberg, que inició el estudio de la teoría de grafos.​ Más allá del problema de los siete puentes de Königsberg, que formalizó posteriormente los ciclos eulerianos, otras aplicaciones de la fórmula de la suma de grados incluyen pruebas de ciertas estructuras combinatorias. Por ejemplo, en las pruebas…

Leer en Wikipedia · Imagen AzaToth, Public domain