¿Por qué se considera incorrecta esta demostración del teorema de los cuatro colores?
Nautilo
Me gustaría pensar que encontré una prueba para el teorema de los cuatro colores, pero también sé que se necesitó gente mucho más inteligente que yo para demostrarlo. Aún así, no veo por qué esta lógica debería ser defectuosa. Si me lo explicas claro, me encantaría:
1- Podrías comenzar conectando dos regiones de diferentes colores sin agujeros, pero agregar un agujero en el medio permite que las otras regiones estén adentro o afuera, así:
Agregar varios agujeros también es una opción, pero equivale a un solo agujero rodeado por dos regiones de todos modos, sin desafiar más la prueba.
2a- Si la tercera región está adentro, el mejor de los casos que permite la mayor cantidad de posibilidades es algo como esto:
El "mejor escenario posible" aquí es el que agrega tantas adyacencias entre colores como sea posible. Si ni siquiera puede refutar el teorema, debe ser cierto.
3a- Entonces la cuarta región de diferente color debe estar en uno de los huecos. Sea el espacio superior derecho:
4a- Entonces todos los huecos tendrán 3 colores alrededor como en la etapa anterior, y no se avanzará.
2b- Si la tercera región está afuera, es algo como esto:
3b- Para evitar 4a, que el cuarto también quede afuera:
4b- Mientras tratamos de evitar 4a, terminamos con una situación similar a 3b con solo 3 regiones exteriores para rodear.
PD. Se basa en el razonamiento inductivo. Si no se necesita un quinto color durante todos estos pasos, tampoco se necesitará nunca después, porque los agujeros y el exterior son solo versiones más pequeñas de las áreas blancas al principio (agujero rodeado por un color o 2 o 3 colores) .
Respuestas (1)
Misha Lavrov
En su esfuerzo por conectar las regiones que dibuja tanto como sea posible de inmediato , en realidad está terminando con mapas que son mucho más fáciles de colorear que el mapa más difícil. Las adyacencias entre sus regiones forman una red apolínea , y es fácil probar que son -de colores.
Pero considere, por ejemplo, el problema de colorear todas las caras de un dodecaedro . (Técnicamente, eso está en la esfera, pero el teorema de los cuatro colores aún debería aplicarse: simplemente haga un agujero en la esfera y estírelo como un globo, y obtendrá un mapa plano).
- Todos sus mapas tienen un punto débil obvio: una región que solo limita con otras tres regiones. Tal región siempre se puede colorear al final, una vez que se haya coloreado todo lo demás.
- El dodecaedro no tiene tal punto débil. Si coloreo alguno de las regiones y me olvido de eso, entonces cuando llego a la , ¡podría terminar teniendo los cuatro colores al lado!
De hecho, estás coloreando regiones a medida que aparecen, lo cual es un problema mucho más difícil: se llama un problema de coloración "en línea". En el caso de colorear en línea, el análogo de la -¡El teorema del color es falso! (Esa es otra razón por la que sabemos que su prueba no es lo suficientemente general: si lo fuera, probaría un resultado falso más fuerte). Si consigo dibujar regiones una a la vez y le pido que las coloree, entonces puedo dibujar un mapa en el que eventualmente fallarás.
¿Como podría hacerlo? Comenzaría dibujando dos regiones que no son adyacentes en absoluto, y luego decidiría qué hacer a continuación según los colores que les dé:
- Si les da el mismo color, entonces puedo dibujar cuatro regiones más que son todas adyacentes entre sí, y cada una es adyacente a una de las dos primeras regiones (como en la primera imagen a continuación). Esos necesitarán cuatro colores diferentes por sí solos, pero luego entrarán en conflicto con el primer color que usó.
- Si les da diferentes colores, entonces puedo dibujar tres regiones más que son todas adyacentes entre sí y las dos primeras (como en la segunda imagen a continuación). Ahora las cinco regiones necesitan colores diferentes.
Por supuesto, ambos mapas son -Colorable, si razonamos sobre los colores de antemano. Pero esto requiere una lógica más sofisticada.
¿Por qué la homología no puede distinguir entre gráficos planos y no planos?
¿Cómo podemos formalizar la noción de la cara de un gráfico plano?
Número cromático total de ciclos
Grafica el número cromático del vértice en una unión de 2 subgrafos
Una pregunta sobre la expectativa del número cromático
NP-completitud del problema de grafos planos no dirigidos
¿T1+T2T1+T2T_1+T_2 es plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?
Demostrar que todo gráfico kkk-cromático tiene tamaño m≥(k2)m≥(k2)m\geq \binom k2
Confusión sobre una demostración sobre la construcción de Mycielski y el número cromático
¿Cómo funciona la colorabilidad en gráficos infinitos (contables e incontables)?
Maximiliano Janisch
Michal Adamaszek
stefano albrecht
Nautilo
Jaap Scherphuis