Lema del apretón de manos

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.^[1]​ 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,^[2]​ 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.^[3]​

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 del lema de Sperner y del problema de la escalada de montañas suelen surgir las propiedades geométricas de la fórmula. La clase de complejidad PPA engloba la dificultad de encontrar un segundo vértice impar, dado uno de tales vértices en un gran grafo implícitamente definido.

Un grafo no dirigido está formado por un sistema de vértices y aristas que conectan pares desordenados de vértices. En cualquier grafo, el grado ${\displaystyle \deg(v)}$ de un vértice ${\displaystyle v}$ se define como el número de aristas que tienen ${\displaystyle v}$ como punto final. Para los grafos que pueden contener bucles que conectan un vértice consigo mismo, un bucle debe contarse como una contribución de dos unidades al grado de su punto final para los propósitos del lema del apretón de manos.^[2]​ Entonces, el lema del apretón de manos establece que, en cada grafo finito, debe haber un número par de vértices para los que ${\displaystyle \deg(v)}$ es un número impar.^[1]​ Los vértices de grado impar de un grafo se denominan a veces nodos impares (o vértices impares);^[4]​ en esta terminología, el lema del apretón de manos puede reformularse como la afirmación de que todo grafo tiene un número par de nodos impares.^[4]​^[5]​

La fórmula de la suma de grados establece que:

${\displaystyle \sum _{v\in V}\deg v=2|E|,}$

Donde ${\displaystyle V}$ es el conjunto de nodos (o vértices) del grafo y ${\displaystyle E}$ es el conjunto de aristas del grafo. Es decir, la suma de los grados de los vértices es igual al doble del número de aristas.^[6]​ En los grafos dirigidos, otra forma de la fórmula de la suma de grados establece que la suma de los grados de entrada de todos los vértices y la suma de los grados de salida son iguales al número de aristas. Aquí, el grado de entrada es el número de aristas entrantes y el grado de salida es el número de aristas salientes.^[7]​ Una versión de la fórmula de la suma de grados también se aplica a familias finitas de conjuntos o, equivalentemente, a multigrafos: la suma de los grados de los elementos (donde el grado es igual al número de conjuntos que lo contienen) siempre es igual a la suma de las cardinalidades de los conjuntos.^[8]​

Ambos resultados se aplican también a cualquier subgrafo del grafo dado y, en particular, a sus componentes conectados. Una consecuencia es que, para cualquier vértice impar, debe existir un camino que lo conecte con otro vértice impar.^[9]​

Leonhard Euler demostró por primera vez el lema del apretón de manos en su trabajo sobre los Siete Puentes de Königsberg, en el que pedía un

Vista esquemática de los siete puentes de Königsberg

Gráfico con vértices para cada masa de tierra y una arista para cada puente

recorrido a pie por la ciudad de Königsberg (actual Kaliningrado) cruzando cada uno de sus siete puentes una vez. En la teoría de grafos, esto puede traducirse como una ruta o recorrido de Euler por un grafo conexo que represente la ciudad y sus puentes: un paseo por el grafo que atraviese cada arista una vez y que termine en un vértice distinto del de partida, en el caso de una ruta de Euler, o que regrese al punto de partida, en el caso de un recorrido de Euler. Euler enunció los resultados fundamentales de este problema en términos del número de vértices impares del grafo, que el lema del apretón de manos restringe a un número par. Si este número es cero, existe un recorrido de Euler, y si es dos, existe un camino de Euler. En caso contrario, el problema no puede resolverse. En el caso de los Siete Puentes de Königsberg, el grafo que representa el problema tiene cuatro vértices impares y no tiene ni camino ni recorrido de Euler,^[3]​ por lo que era imposible recorrer los siete puentes de Königsberg sin repetir ninguno.

En el algoritmo Christofides-Serdyukov para aproximar el problema del viajante de comercio, las implicaciones geométricas de la fórmula de la suma de grados desempeñan un papel vital, permitiendo al algoritmo conectar vértices de dos en dos para construir un grafo en el que un recorrido de Euler forme un recorrido aproximado del TSP.^[10]​

Se puede demostrar que varias estructuras combinatorias son pares en número relacionándolas con los vértices impares de un «grafo de intercambio» apropiado.^[11]​

Por ejemplo, como demostró C. A. B. Smith, en cualquier grafo cúbico ${\displaystyle G}$ debe haber un número par de ciclos hamiltonianos a través de cualquier arista fija ${\displaystyle uv}$; se trata de ciclos que pasan por cada vértice exactamente una vez. Thomason (1978) utilizó una prueba basada en el lema del apretón de manos para extender este resultado a grafos en los que todos los vértices tienen grado impar. Thomason define un grafo de intercambio ${\displaystyle H}$ cuyos vértices están en correspondencia uno a uno con las trayectorias hamiltonianas en ${\displaystyle G}$ comenzando en ${\displaystyle u}$ y continuando por el borde ${\displaystyle uv}$. Dos de estas vías ${\displaystyle p_{1}}$y ${\displaystyle p_{2}}$ se definen como conectadas por una arista en ${\displaystyle H}$ si se puede obtener ${\displaystyle p_{2}}$ añadiendo una nueva arista al final de ${\displaystyle p_{1}}$y quitando otra arista del centro de ${\displaystyle p_{1}}$. Esta operación es reversible, formando una relación simétrica, por lo que ${\displaystyle H}$ es un grafo no dirigido. Si el camino ${\displaystyle p}$ termina en el vértice ${\displaystyle w}$, entonces el vértice correspondiente a ${\displaystyle p}$ en ${\displaystyle H}$ tiene grado igual al número de formas en que ${\displaystyle p}$ puede ampliarse con una arista que no vuelva a conectarse con ${\displaystyle u}$; es decir, el grado de este vértice en ${\displaystyle H}$ es ${\displaystyle \deg(w)-1}$ (un número par) si ${\displaystyle p}$ no forma parte de un ciclo hamiltoniano a través de ${\displaystyle uv}$ o ${\displaystyle \deg(w)-2}$ (un número impar) si ${\displaystyle p}$ forma parte de un ciclo hamiltoniano a través de ${\displaystyle uv}$. Dado que ${\displaystyle H}$ tiene un número par de vértices impares, ${\displaystyle G}$ debe tener un número par de ciclos hamiltonianos a través de ${\displaystyle uv}$.^[12]​

El lema del apretón de manos (o fórmula de la suma de grados) también se utiliza en la demostración de otros resultados matemáticos. Entre ellos se incluyen los siguientes:

• 

  El lema de Sperner establece que, si un triángulo grande se subdivide en triángulos más pequeños que se encuentran borde con borde, y los vértices se etiquetan con tres colores de modo que sólo dos de los colores se utilizan a lo largo de cada borde del triángulo grande, entonces al menos uno de los triángulos más pequeños tiene vértices de los tres colores; tiene aplicaciones en teoremas de punto fijo, algoritmos de búsqueda de raíces, y la división justa. Una prueba de este lema forma un grafo de intercambio cuyos vértices son los triángulos (grandes y pequeños) y cuyas aristas conectan pares de triángulos que comparten dos vértices de dos colores determinados. El triángulo grande tiene necesariamente grado impar en este grafo de intercambio, al igual que un triángulo pequeño con los tres colores, pero no los otros triángulos pequeños. Por el lema del apretón de manos, debe haber un número impar de triángulos pequeños con los tres colores y, por tanto, debe existir al menos uno de estos triángulos.^[13]​

• 

  El problema de la escalada de montañas establece que, para funciones suficientemente bien comportadas en un intervalo unitario, con valores iguales en los extremos del intervalo, es posible coordinar el movimiento de dos puntos, que parten de extremos opuestos del intervalo, de modo que se encuentren en algún punto intermedio permaneciendo en puntos de igual valor durante todo el movimiento. Una prueba de ello consiste en aproximar la función por una función lineal a trozos con los mismos puntos extremos, parametrizar la posición de los dos puntos en movimiento por las coordenadas de un único punto del cuadrado unitario y demostrar que las posiciones disponibles para los dos puntos forman un grafo finito, incrustado en este cuadrado, con sólo la posición inicial y su inversión como vértices impares. Por el lema del apretón de manos, estas dos posiciones pertenecen a la misma componente conexa del grafo, y un camino de una a otra pasa necesariamente por el punto de encuentro deseado.^[14]​
• La conjetura de reconstrucción se refiere al problema de determinar de forma única la estructura de un grafo a partir del conjunto de subgrafos formados al eliminar un único vértice del mismo. Dada esta información, la fórmula de la suma de grados puede utilizarse para recuperar el número de aristas del grafo dado y los grados de cada vértice. A partir de ahí, es posible determinar si el grafo es regular y, en caso afirmativo, determinarlo de forma única a partir de cualquier subgrafo con vértices eliminados añadiendo un nuevo vecino a todos los vértices del subgrafo con un grado demasiado bajo. Por lo tanto, se pueden reconstruir todos los grafos regulares.^[15]​
• El juego del Hexágono lo juegan dos jugadores, que colocan piezas de su color en un tablero en forma de paralelogramo embaldosado por hexágonos hasta que uno de los jugadores tenga un camino conectado de piezas adyacentes de un lado al otro del tablero. Nunca puede acabar en empate: en el momento en que el tablero se haya llenado completamente de piezas, uno de los jugadores habrá formado un camino ganador. Una prueba de ello es que se forma un gráfico a partir de un tablero lleno, con vértices en las esquinas de los hexágonos y con aristas en los lados de los hexágonos que separan los colores de los dos jugadores. Este grafo tiene cuatro vértices impares en las esquinas del tablero, y vértices pares en el resto, por lo que debe contener un camino que conecte dos esquinas, que necesariamente tiene un camino ganador para un jugador en uno de sus lados.^[16]​

La demostración de Euler de la fórmula de la suma de grados utiliza la técnica del conteo doble: cuenta el número de pares incidentes ${\displaystyle (v,e)}$ donde ${\displaystyle e}$ es una arista y un vértice ${\displaystyle v}$ es uno de sus extremos, de dos maneras diferentes. Vértice ${\displaystyle v}$ pertenece a ${\displaystyle \deg(v)}$ pares, donde ${\displaystyle \deg(v)}$ (el grado de ${\displaystyle v}$) es el número de aristas incidentes en él. Por lo tanto, el número de pares incidentes es la suma de los grados. Sin embargo, cada arista del grafo pertenece exactamente a dos pares incidentes, uno por cada uno de sus extremos; por lo tanto, el número de pares incidentes es ${\displaystyle 2|E|}$. Como estas dos fórmulas cuentan el mismo conjunto de objetos, deben tener valores iguales. La misma demostración puede interpretarse como sumar las entradas de la matriz de incidencia del grafo de dos maneras, por filas para obtener la suma de grados y por columnas para obtener el doble del número de aristas.^[5]​

En el caso de los grafos, el lema del apretón de manos es un corolario de la fórmula de la suma de grados.^[8]​ En una suma de números enteros, la paridad de la suma no se ve afectada por los términos pares de la suma; la suma total es par cuando hay un número par de términos impares, e impar cuando hay un número impar de términos impares. Como uno de los lados de la fórmula de la suma de grados es el número par ${\displaystyle 2|E|}$, la suma del otro lado debe tener un número par de términos impares; es decir, debe haber un número par de vértices de grado impar.^[5]​

Alternativamente, es posible utilizar la inducción matemática para demostrar la fórmula de la suma de grados,^[2]​ o demostrar directamente que el número de vértices de grado impar es par, eliminando una arista cada vez de un grafo dado y utilizando un análisis de casos sobre los grados de sus extremos para determinar el efecto de esta eliminación sobre la paridad del número de vértices de grado impar.^[17]​

La fórmula de la suma de grados implica que cada grafo regular ${\displaystyle r}$ con ${\displaystyle n}$ vértices tiene ${\displaystyle nr/2}$ bordes.^[18]​ Dado que el número de aristas debe ser un

El grafo de Clebsch, regular de grado cinco, tiene un número par de vértices (16) y un número de aristas (40) que es múltiplo de cinco.

El dodecaedro rómbico es birregular con seis vértices de grado cuatro y ocho vértices de grado tres; 6 × 4 = 8 × 3 = 24, su número de aristas.

número entero, se deduce que cuando ${\displaystyle r}$ es impar, el número de vértices debe ser par.^[19]​ Además, para valores impares de ${\displaystyle r}$ el número de aristas debe ser divisible por ${\displaystyle r}$. ^[20]​

Un grafo bipartito tiene sus vértices divididos en dos subconjuntos, y cada arista tiene un extremo en cada subconjunto. Del mismo argumento de la doble cuenta se deduce que, en cada subconjunto, la suma de grados es igual al número de aristas del grafo. En particular, ambos subconjuntos tienen sumas de grados iguales.^[21]​ Para grafos birregulares, con una partición de los vértices en subconjuntos ${\displaystyle V_{1}}$ y ${\displaystyle V_{2}}$ con cada vértice en un subconjunto ${\displaystyle V_{i}}$ con grado ${\displaystyle r_{i}}$ debe darse el caso de que ${\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}$ ambos son iguales al número de aristas.^[22]​

El lema del apretón de manos no se aplica en su forma habitual a los grafos infinitos, incluso cuando sólo tienen un número finito de vértices de grado impar. Por ejemplo, un grafo de camino infinito con un punto final sólo tiene un vértice de grado impar, en lugar de tener un número par de vértices de este tipo. Sin embargo, es posible formular una versión del lema del apretón de manos utilizando el concepto de extremo, una clase de equivalencia de caminos semi-infinitos («rayos») considerando dos rayos como equivalentes cuando existe un tercer rayo que utiliza infinitamente muchos vértices de cada uno de ellos. El grado de un extremo es el número máximo de rayos disjuntos que contiene, y un extremo es impar si su grado es finito e impar. De forma más general, es posible definir un extremo como par o impar, independientemente de si tiene grado infinito, en grafos en los que todos los vértices tienen grado finito. Entonces, en tales grafos, el número de vértices impares y extremos impares, sumados, es par o infinito.^[23]​

Por un teorema de Gallai los vértices de cualquier grafo se pueden particionar como ${\displaystyle V=V_{e}\cup V_{o}}$ donde en los dos subgrafos inducidos resultantes ${\displaystyle G[V_{e}]}$, tiene todos los grados pares y ${\displaystyle G[V_{o}]}$ tiene todos los grados impares. Aquí, ${\displaystyle |V_{o}|}$ debe ser par por el lema del apretón de manos. También es posible encontrar subgrafos inducidos de grado par e impar con muchos vértices. Un subgrafo inducido de grado par se puede encontrar con al menos la mitad de los vértices, y un subgrafo inducido de grado impar (en un grafo sin vértices aislados) se puede encontrar con ${\displaystyle |V_{o}|/|V|>1/10000}$. ^[24]​^[25]​

En relación con el método del grafo de intercambio para demostrar la existencia de estructuras combinatorias, es interesante preguntarse con qué eficacia se pueden encontrar estas estructuras. Por ejemplo, supongamos que se nos da como entrada un ciclo hamiltoniano en un grafo cúbico; del teorema de Smith se deduce que existe un segundo ciclo. ¿En cuánto tiempo se puede encontrar este segundo ciclo? Papadimitriou (1994) investigó la complejidad computacional de cuestiones como ésta o, más en general, de encontrar un segundo vértice de grado impar cuando se da un único vértice impar en un grafo grande definido implícitamente. Definió la clase de complejidad PPA para encapsular problemas como éste;^[26]​ una clase estrechamente relacionada definida en grafos dirigidos, PPAD, ha atraído una atención significativa en la teoría algorítmica de juegos porque calcular un equilibrio de Nash es computacionalmente equivalente a los problemas más difíciles de esta clase.^[27]​

Los problemas computacionales que han demostrado ser completos para la clase de complejidad PPA incluyen tareas computacionales relacionadas con el lema de Sperner^[28]​ y con la subdivisión equitativa de recursos según el teorema de Hobby-Rice.^[29]​