El teorema de Erdős-Gallai es un resultado de la teoría de grafos , una rama de las matemáticas combinatorias . Proporciona uno de los dos enfoques conocidos para resolver el problema de realización de gráficos , es decir, proporciona una condición necesaria y suficiente para que una secuencia finita de números naturales sea la secuencia de grados de un gráfico simple . Una secuencia que obedece a estas condiciones se llama "gráfica". El teorema fue publicado en 1960 por Paul Erdős y Tibor Gallai , de quienes lleva su nombre.
Una secuencia de números enteros no negativos se puede representar como la secuencia de grados de un gráfico simple finito en n vértices si y solo si es par y
se mantiene para cada in .
No es difícil demostrar que las condiciones del teorema de Erdős-Gallai son necesarias para que una secuencia de números sea gráfica. El requisito de que la suma de los grados sea par es el lema del apretón de manos , ya utilizado por Euler en su artículo de 1736 sobre los puentes de Königsberg . La desigualdad entre la suma de los grados más grandes y la suma de los grados restantes se puede establecer mediante conteo doble : el lado izquierdo da el número de adyacencias de borde-vértice entre los vértices de mayor grado, cada una de esas adyacencias debe estar en un borde con uno o dos puntos finales de alto grado, el término de la derecha da el número máximo posible de adyacencias borde-vértice en las que ambos puntos finales tienen alto grado, y el término restante en los límites superiores derechos el número de aristas que tienen exactamente un alto grado punto final de grado. Por tanto, la parte más difícil de la prueba es demostrar que, para cualquier secuencia de números que obedezcan estas condiciones, existe una gráfica para la cual es la secuencia de grados.
La demostración original de Erdős y Gallai (1960) era larga y complicada. Choudum (1986) cita una prueba más breve de Claude Berge , basada en ideas de flujo de red . Choudum, en cambio, proporciona una prueba por inducción matemática sobre la suma de los grados: deja ser el primer índice de un número en la secuencia para la cual (o el penúltimo número si todos son iguales), utiliza un análisis de caso para demostrar que la secuencia formada restando uno del último número de la secuencia (y eliminando el último número si esta resta hace que se convierta en cero) es nuevamente gráfico y forma un gráfico que representa la secuencia original agregando un borde entre las dos posiciones de las cuales uno fue restado.
Tripathi, Venugopalan y West (2010) consideran una secuencia de "subrealizaciones", gráficos cuyos grados están delimitados superiormente por la secuencia de grados dada. Muestran que, si G es una subrealización, y i es el índice más pequeño de un vértice en G cuyo grado no es igual a d i , entonces G puede modificarse de manera que produzca otra subrealización, aumentando el grado del vértice i sin cambiando los grados de los vértices anteriores de la secuencia. Los pasos repetidos de este tipo deben llegar eventualmente a la realización de la secuencia dada, demostrando el teorema.
Aigner y Triesch (1994) describen estrechas conexiones entre el teorema de Erdős-Gallai y la teoría de las particiones enteras . Dejar ; entonces las secuencias enteras ordenadas que se suman pueden interpretarse como las particiones de . Bajo la mayorización de sus sumas de prefijos , las particiones forman una red , en la que el cambio mínimo entre una partición individual y otra partición inferior en el orden de partición es restar uno de uno de los números y sumarlo a un número que es al menos más pequeño. menos dos ( podría ser cero). Como muestran Aigner y Triesch, esta operación conserva la propiedad de ser gráfica, por lo que para probar el teorema de Erdős-Gallai basta con caracterizar las secuencias gráficas que son máximas en este orden de mayorización. Proporcionan dicha caracterización, en términos de los diagramas de Ferrers de las particiones correspondientes, y muestran que es equivalente al teorema de Erdős-Gallai.
Teoremas similares describen las secuencias de grados de gráficos dirigidos simples, gráficos dirigidos simples con bucles y gráficos bipartitos simples (Berger 2012). El primer problema se caracteriza por el teorema de Fulkerson-Chen-Anstee . Los dos últimos casos, que son equivalentes, se caracterizan por el teorema de Gale-Ryser .
Tripathi y Vijay (2003) demostraron que basta con considerar la desigualdad tal que con y para . Barrus et al. (2012) restringen el conjunto de desigualdades para gráficas en sentido opuesto. Si una secuencia positiva de suma par no tiene entradas repetidas distintas del máximo y el mínimo (y la longitud excede la entrada más grande), entonces es suficiente verificar solo la enésima desigualdad, donde .
Una secuencia finita de números enteros no negativos es gráfica si es par y existe una secuencia que es gráfica y mayorista . Este resultado fue dado por Aigner y Triesch (1994). Mahadev y Peled (1995) lo reinventaron y dieron una prueba más directa.
