Gráficos no planares

Question

Sé que puede ser una respuesta a este lugar en línea, si es así yo no lo he encontrado. Pero, me pregunto, si hay al menos un poco intuitiva responder a las siguientes:

¿Por qué son todos los no-grafos planares extensiones o super-gráficos de $K_{3,3}$ o $K_5$?

Tengo la prueba de que $K_{3,3}$ $K_5$ son no planas, pero todavía estoy estupefacto. Me siento como con la mayoría de las cosas en las matemáticas, algunos de cierta intuición detrás de teoremas y conceptos. Pero, tal vez yo no estoy pensando en el lugar correcto.

Answer 1

Hay una intuición, por el simple encontrar todos los gráficos sin subdivisiones que la demanda de al menos un cruce?

Asumir que hay es una simple intuición. Ahora bien, el uso que encontrar todos los gráficos sin subdivisiones que demanda al menos dos cruces.

He aquí dos de ellos, el primero es el gráfico de Petersen, pero la aparentemente simple intuición es que acaba de empezar. Será necesario que la lista de los más simples 2-cruzando el cuarto grado gráficos, y otras gráficas sencillas que requieren 2 cruces. Sólo para cúbicos gráficos, supone la intuición tendrá que demostrar que los grandes cúbicos 2-cruce de gráficos tendrán estos dos como una subdivisión, o que más cúbico gráficos son necesarios.

Por desgracia -- este conjunto mínimo de dos cruces es actualmente un problema sin resolver. Es probable equipo solucionable con una búsqueda de fuerza bruta a través de orden inferior de los gráficos en un par de semanas. Probablemente habría una lista de 20 o más gráficos y una muy difícil prueba, en otras palabras, un patán resultado.

Nadie de manera intuitiva se puede escribir una lista completa de todos un mínimo de 2-cruce de los gráficos. Un nivel de intuición no existe.

En lugar de la intuición, la sospecha, por lo general funciona mejor. Cuando Kuratowski empezó a mirar a este problema, encontró a $K_{3,3}$ $K_5$ pero no se detuvo allí, él sospechaba de ella. Que lo ayudaron a construir la prueba.

La iluminación proviene, generalmente, de un proceso de eliminación, y por lo general hay un montón de eliminar. No es el uso de un interruptor de la luz para examinar una gran sala -- es el rastreo de ciegos en la habitación y la sensación de cada superficie. O la programación de una computadora para hacer eso por usted.

Similares-Snark Teorema: Cualquier Snark tiene un Gráfico de Petersen menor de edad. Estos gráficos fueron nombrados snarks por Gardner, Tutte conjeturó el teorema. Probado por Robertson, Sanders, Seymour y Thomas en el 2001, utilizando los métodos más difícil de demostrar que el 4-color teorema.