Mi favorita es la prueba de Kempe del teorema de los cuatro colores (cualquier gráfico plano tiene una coloración con solo cuatro colores). Argumentó por inducción sobre el número de vértices. El caso base es fácil: si el gráfico solo tiene un vértice, por supuesto, podemos colorearlo. El paso de inducción es el siguiente:
Primero, usamos la fórmula de Euler para verificar que debe haber un vértice de grado como máximo cinco. Sea [matemática] V [/ matemática] el número de vértices, [matemática] E [/ matemática] la cantidad de aristas y [matemática] F [/ matemática] la cantidad de caras. Cada cara tiene al menos 3 lados, entonces [matemática] 3F \ leq 2E [/ matemática], y entonces [matemática] F \ leq \ frac23 E [\ matemática]. Sustituyendo esto en la fórmula de Euler [matemática] F + V – E = 2 [/ matemática] se obtiene [matemática] V – \ frac13 E \ geq 2 [/ matemática], y se deduce que [matemática] 6V> 2E [/ matemática] , lo que sería imposible si todos los vértices tuvieran un grado de al menos 6. Por lo tanto, hay un vértice [matemático] v [/ matemático] de grado como máximo cinco.
Ahora sabemos que si eliminamos este vértice, podemos colorear el resto del gráfico. Pero el problema es que los cuatro colores podrían usarse para los vecinos de [math] v [/ math], sin dejar colores para [math] v [/ math] en sí. Kempe ahora presentó la siguiente estrategia inteligente de cambio de color. Elegimos dos colores, digamos rojo y azul, y elegimos algún componente conectado del subgrafo en los vértices rojo y azul. Solo en ese componente, volvemos a colorear todos los vértices rojos azules y todos los vértices azules rojos. Si hacemos eso, no terminaremos con dos vértices vecinos del mismo color. El plan de Kempe era volver a colorear de esta manera para reducir el número de colores entre los vecinos de [math] v [/ math] a 3, de modo que podamos colorear [math] v [/ math] con el color restante.
- ¿La probabilidad de regresar al origen al caminar sobre una red d-dimensional converge a cero con el crecimiento de d?
- ¿Por qué nadie ha encontrado un operador autoadjunto con los ceros (parte imaginaria de) de la función zeta como valor propio?
- ¿Existe una prueba simple de la teoría de Galois? ¿Cuál es la diferencia entre la prueba original de Galois y la prueba más moderna?
- ¿Qué es un enfoque DID (diferencia en diferencia)?
- ¿Cuán fuertemente dependen las pruebas de Godel del uso de la serie Fibonaccii? ¿Se ha desarrollado una prueba similar sin comenzar con los números de Fibonacci?
Si [math] v [/ math] tiene como máximo 3 vecinos, entonces no hay problema de todos modos. Si solo tiene 4 vecinos, suponga que los colores de esos vecinos (en el sentido de las agujas del reloj) son rojo, amarillo, azul y verde. Podríamos intentar usar la estrategia de Kempe para volver a colorear el vecino rojo azul. El único problema es que el vecino azul podría estar en el mismo componente rojo-azul que el rojo, de modo que cuando coloreamos el vecino rojo azul también coloreamos el azul rojo. Para que eso suceda, tendría que haber un camino desde el vecino rojo al azul, que consta de solo vértices rojos y azules. ¿Qué pasa si en cambio tratamos de volver a colorear el vecino amarillo verde? Mediante un argumento como el anterior, esto será lo suficientemente bueno a menos que haya un camino desde el vecino amarillo al verde que consista solo en vértices amarillos y verdes. Pero debido a que se supone que todo esto está incrustado en el plano, no puede haber caminos de ambos tipos (tendrían que cruzarse). Por lo tanto, debemos poder cambiar el color del vecino azul rojo o el amarillo vecino verde sin cambiar los colores de los otros vecinos, y eso es lo suficientemente bueno.
El caso más difícil es cuando [math] v [/ math] tiene cinco vecinos. En ese caso, algunos de ellos deben ser del mismo color. Digamos que los colores, en el sentido de las agujas del reloj, son rojo, amarillo, rojo, verde, azul. Una vez más, podemos volver a colorear el vecino amarillo verde a menos que haya un camino amarillo-verde desde el vecino amarillo al verde. Pero si existe ese camino, entonces no hay un camino rojo-azul desde el segundo vecino rojo al azul, por lo que podemos volver a colorear el segundo vecino rojo azul. Un argumento similar muestra que podemos volver a colorear el primer vecino rojo verde. Después de haber recoloreado a ambos vecinos rojos de esta manera, podemos colorear [math] v [/ math] red y listo.
Ese es un argumento claro, y parece probar el teorema de los cuatro colores. Pero incluye un error sutil. En el último párrafo, después de volver a colorear el segundo vértice rojo azul, también hemos cambiado el color de un montón de otros vértices. En particular, podríamos haber destruido el camino amarillo-azul desde el vértice amarillo al azul e introducido en su lugar un camino rojo-verde desde el primer vértice rojo hasta el verde. Entonces, después de volver a colorear el segundo vértice rojo azul, ya no podemos volver a colorear el primero en verde.
