El método de descarga es una técnica utilizada para probar lemas en la teoría de grafos estructurales . [1] La descarga es más conocida por su papel central en la demostración del teorema de los cuatro colores . El método de descarga se utiliza para demostrar que cada gráfico de una determinada clase contiene algún subgrafo de una lista específica. La presencia del subgrafo deseado se utiliza a menudo para demostrar un resultado de coloración . [1]
Lo más común es que la descarga se aplique a gráficos planos . Inicialmente se asigna una carga a cada cara y a cada vértice del gráfico. Las cargas se asignan de modo que suman un pequeño número positivo. Durante la fase de descarga, la carga en cada cara o vértice puede redistribuirse a caras y vértices cercanos, según lo exige un conjunto de reglas de descarga. Sin embargo, cada regla de descarga mantiene la suma de los cargos. Las reglas están diseñadas para que después de la fase de descarga cada cara o vértice con carga positiva se encuentre en uno de los subgrafos deseados. Como la suma de las cargas es positiva, alguna cara o vértice debe tener carga positiva. Muchos argumentos de descarga utilizan una de las pocas funciones de carga inicial estándar (se enumeran a continuación). La aplicación exitosa del método de descarga requiere un diseño creativo de las reglas de descarga.
En 1904, Wernicke introdujo el método de descarga para demostrar el siguiente teorema, que era parte de un intento de demostrar el teorema de los cuatro colores.
Teorema: si un gráfico plano tiene un grado mínimo de 5, entonces tiene una arista con puntos finales de grado 5 o una con puntos finales de grados 5 y 6.
Prueba: Usamos , y para denotar los conjuntos de vértices, caras y aristas, respectivamente. Llamamos luz de borde si sus puntos finales son ambos de grado 5 o de grados 5 y 6. Incrusta el gráfico en el plano. Para probar el teorema, basta con considerar solo triangulaciones planas (porque, si se cumple una triangulación, al eliminar nodos para volver al gráfico original, ninguno de los nodos a ambos lados del borde deseado se puede eliminar sin reducir el grado mínimo del gráfico siguiente 5). Agregamos arbitrariamente aristas al gráfico hasta que sea una triangulación. Dado que el gráfico original tenía un grado mínimo de 5, cada punto final de una nueva arista tiene un grado de al menos 6. Por lo tanto, ninguna de las nuevas aristas es clara. Por lo tanto, si la triangulación contiene un borde claro, entonces ese borde debe haber estado en el gráfico original.
Le damos la carga a cada vértice y la carga a cada cara , donde denota el grado de un vértice y la longitud de una cara. (Dado que la gráfica es una triangulación, la carga en cada cara es 0). Recuerde que la suma de todos los grados en la gráfica es igual al doble del número de aristas; de manera similar, la suma de todas las longitudes de las caras es igual al doble del número de aristas. Usando la fórmula de Euler , es fácil ver que la suma de todas las cargas es 12:
Usamos solo una única regla de descarga:
Consideramos qué vértices podrían tener carga final positiva. Los únicos vértices con carga inicial positiva son los de grado 5. Cada vértice de grado 5 da una carga de 1/5 a cada vecino. Entonces, a cada vértice se le da una carga total de como máximo . La carga inicial de cada vértice v es . Entonces, la carga final de cada vértice es como máximo . Por lo tanto, un vértice solo puede tener carga final positiva si tiene grado como máximo 7. Ahora mostramos que cada vértice con carga final positiva es adyacente a un punto final de un borde ligero.
Si un vértice tiene grado 5 o 6 y tiene carga final positiva, entonces recibe carga de un vértice adyacente de grado 5 , por lo que el borde es ligero. Si un vértice tiene grado 7 y tiene carga final positiva, entonces recibe carga de al menos 6 vértices adyacentes de grado 5. Dado que el gráfico es una triangulación, los vértices adyacentes deben formar un ciclo, y como solo tiene grado 7, los vecinos de grado 5 no pueden estar todos separados por vértices de mayor grado; al menos dos de los vecinos de grado 5 deben estar adyacentes entre sí en este ciclo. Esto produce el borde ligero.
