Esta pregunta es, en parte inspirado por una frase que vi en una respuesta a otra pregunta:
El problema con la correcta pruebas para corregir las declaraciones es que es difícil llegar con un contraejemplo.
Hace poco, asistí a una teoría de grafos curso en el que hubo un capítulo en el gráfico coloraciones. El más famoso problema en esta área es el de cuatro colores teorema, el cual establece que los vértices de cualquier plano gráfico se pueden colorear con cuatro colores de tal manera que no hay dos vértices adyacentes del mismo color. Esto es fácilmente demostrado ser equivalente a la más famosa declaración del teorema relativo a las coloraciones de los países en un mapa. Nuestra profesora nos mostró la más simple de las pruebas de los seis colores y en cinco colores teoremas (es decir, los cuatro-color teorema, pero con 'cinco' y 'seis' sustituido por 'cuatro') y, a continuación, nos mostró un poco más complicado prueba del cuatro-color teorema.
En este punto, los murmullos empezaron a ir alrededor de la habitación. Es bien sabido que la única prueba de la cuatro-color teorema, debido a Appel y Haken, hace indispensable el uso de un ordenador para comprobar los miles de casos y ciertamente no puede ser escritas en una pizarra en menos de una hora. Nuestro leccturer explicó que la prueba era incorrecta, y dejó como un ejercicio para averiguar por qué.
He trabajado en ello un poco, y, finalmente, encontró un problema con la prueba. Busqué en internet para averiguar si estaba en lo correcto, pero era incapaz de hacerlo. Sin embargo, me hizo ver una cosa que me intrigó. La prueba de que nuestro profesor nos había mostrado fue formulado originalmente por Alfred Kempe, y se puso indiscutible durante once años hasta que Percy Heawood encontrado el problema. Lo que me pareció interesante fue la siguiente:
Percy Heawood encontrado un gráfico que fue un contraejemplo para la prueba!
Así que aquí está mi pregunta. Dado que los cuatro-color teorema es correcto, ¿cómo es posible encontrar un contraejemplo a una incorrecta de la prueba? Mi conjetura es lo que Kempe, demostró ser más fuerte que el teorema de los cuatro colores, y el Heawood gráfico es un contraejemplo para que leve fortalecimiento. Pero me interesaría saber si hay más que se puede decir.
Yo estaría especialmente interesado si usted tiene otros ejemplos de contraejemplos para incorrecta de las pruebas para la afirmación correcta.
