El método de descarga es una técnica utilizada para demostrar lemas en la teoría de grafos estructurales . [1] La descarga es más conocida por su papel central en la prueba del teorema de los cuatro colores . El método de descarga se utiliza para demostrar que cada grafo de una determinada clase contiene algún subgrafo de una lista especificada. La presencia del subgrafo deseado se utiliza a menudo para demostrar un resultado de coloración . [1]
La descarga se aplica más comúnmente a los grafos planos . Inicialmente, se asigna una carga a cada cara y a cada vértice del grafo. Las cargas se asignan de modo que sumen un pequeño número positivo. Durante la fase de descarga, la carga en cada cara o vértice puede redistribuirse a las caras y vértices cercanos, según lo requiera un conjunto de reglas de descarga. Sin embargo, cada regla de descarga mantiene la suma de las cargas. Las reglas están diseñadas de modo que después de la fase de descarga, cada cara o vértice con carga positiva se encuentre en uno de los subgrafos deseados. Dado que la suma de las cargas es positiva, alguna cara o vértice debe tener una carga positiva. Muchos argumentos de descarga utilizan una de las pocas funciones de carga inicial estándar (que 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 fue parte de un intento de demostrar el teorema de los cuatro colores.
Teorema: Si un grafo plano tiene un grado mínimo de 5, entonces tiene una arista con extremos de grado 5 o una con extremos de grados 5 y 6.
Demostración: Usamos , , y para denotar los conjuntos de vértices, caras y aristas, respectivamente. Llamamos a una arista ligera si sus puntos finales son ambos de grado 5 o son de grados 5 y 6. Incrustamos el grafo en el plano. Para demostrar el teorema, es suficiente considerar solo triangulaciones planares (porque, si se cumple en una triangulación, al eliminar nodos para volver al grafo original, no se puede eliminar ningún nodo en ninguno de los lados de la arista deseada sin reducir el grado mínimo del grafo por debajo de 5). Agregamos aristas arbitrariamente al grafo hasta que sea una triangulación. Dado que el grafo original tenía un grado mínimo de 5, cada punto final de una nueva arista tiene un grado de al menos 6. Entonces, ninguna de las nuevas aristas es ligera. Por lo tanto, si la triangulación contiene una arista ligera, entonces esa arista debe haber estado en el grafo original.
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. (Como el gráfico es una triangulación, la carga en cada cara es 0). Recordemos que la suma de todos los grados en el gráfico 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:
Utilizamos sólo una única regla de descarga:
Consideremos qué vértices podrían tener carga final positiva. Los únicos vértices con carga inicial positiva son los vértices de grado 5. Cada vértice de grado 5 da una carga de 1/5 a cada vecino. Por lo tanto, a cada vértice se le da una carga total de como máximo . La carga inicial de cada vértice v es . Por lo tanto, 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 un grado como máximo de 7. Ahora demostramos que cada vértice con carga final positiva es adyacente a un punto final de una arista ligera.
Si un vértice tiene grado 5 o 6 y tiene carga final positiva, entonces recibió carga de un vértice adyacente de grado 5 , por lo que la arista es ligera. Si un vértice tiene grado 7 y tiene carga final positiva, entonces recibió carga de al menos 6 vértices adyacentes de grado 5. Como el gráfico es una triangulación, los vértices adyacentes a deben formar un ciclo, y como solo tiene grado 7, los vecinos de grado 5 no pueden estar todos separados por vértices de grado superior; al menos dos de los vecinos de grado 5 de deben ser adyacentes entre sí en este ciclo. Esto produce la arista ligera.
