¿Dónde puedo encontrar una prueba del teorema de Tutte?

Question

No me gusta la prueba de que el teorema de Kuratowski en mi libro, pero el libro se menciona un teorema de William Tutte:

Teorema: Un gráfico de $G$ es planar si y sólo si el conflicto gráfica de cada ciclo de $G$ es bipartito.

Donde el conflicto gráfico del ciclo es, más o menos, el gráfico de tener los "acordes" de el ciclo de vértices, y dos acordes son adyacentes en el conflicto gráfico iff de conflicto, en el sentido de que va necesariamente de la cruz, si bien ambos se dibuja dentro del ciclo, o ambos son atraídos fuera del ciclo.

Me gustaría una prueba del teorema anterior que no se basa en el teorema de Kuratowski.

El libro de referencias de este artículo, pero no puedo encontrar nada que se asemeja a el teorema estoy buscando. No sé nada acerca de matroids a todos, así que es de suponer que el teorema es de allí, pero se expresan en un lenguaje que la hace irreconocible para mí.

Te agradecería un enlace a una más gráfico-teórico de la prueba, o una explicación de por que la proposición en el ligado de papel es la que yo quiero, y cómo puedo descifrar desde el lenguaje de la matroids en algo voy a entender.

Answer 1

AFAIS "acordes" de ciclo en su nota es un camino que no tiene vértices de ciclo, excepto el primero y el último (en oposición a la definición habitual que acorde es una ventaja). De lo contrario, subdividir cada borde de cualquier no-planar gráfico para obtener contraejemplo. También supongo que para dos "acordes" su vértice común puede ser considerado como virtual "acorde" en conflicto con ninguno de ellos. De lo contrario, otro contraejemplo puede ser dado. Sin embargo dice que esas virual "acorde" debe ser dentro del ciclo me refiero a que el correspondiente vértice debe estar fuera y viceversa.

$\Rightarrow$. Si el gráfico de $G$ tiene un ciclo de $C$ con los no-bipartita conflicto gráfico de $H$ $G$ no es planar.

Supongamos que $G$ es plano y considerar la posibilidad de longitud impar ciclo de $h_1h_2\ldots h_{2k+1}h_1$ en el gráfico $H$ donde $h_i$ son "acordes" de $C$. Si $h_i$ está dentro de $C$ $h_{i+1}$ debe ser fuera de $C$ no se cruzan con $h_i$ y viceversa. Si $h_1$ está dentro de $C$ $h_{2k+1}$ está dentro de $C$, demasiado, y que se cruzan. De la misma forma si $h_1$ es de fuera $C$. $\square$

$\Leftarrow$. Si el gráfico de $G$ no tiene ningún ciclo con los no-bipartita conflicto gráfica a continuación, $G$ es planar.

Vamos a empezar con el vacío gráfico (que es plana) y de manera inductiva agregar bordes de $G$. Por hipótesis de inducción $G - e$ es planar. Si no hay ningún ciclo en $G$ agrupa $e = uv$ $G$ es, obviamente, plano (desde $e$ sólo conecta dos planas de los componentes conectados a $G_u$ $G_v$ y es posible hacer cualquier cara de la plana gráfico cara exterior; por lo que puede hacer $u$ a pertenecer cara exterior de $G_u$, $v$ pertenecer cara exterior de $G_v$ y añadir $e = uv$). Así que vamos a $e$ pertenecen a algún ciclo de $G$. Ahora, para cada ciclo $C$ $G - e$ tal que $\{\,u, v\,\} \subset V(C)$ sabemos si $e$ tiene que ser dentro o fuera de $C$ no se cruzan con otros acordes (para algunos ciclos dentro y fuera de las ubicaciones son posibles, pero estos ciclos dar ningún tipo de restricción). El único problema para $G$ a ser planar es que hay pocos ciclos con $e$ acorde han requisitos contradictorios. A continuación, podemos producir la ultraperiféricas ciclo de $C$ contiene $u$ $v$ el uso de vértices y aristas de estos ciclos. Ciclo de dos acordes en conflicto con $e$, y cualquiera que entre en conflicto el uno con el otro o en el interior de acordes tiene al menos un vértice común con otro acorde que entra en conflicto con el exterior. En ambos casos se obtiene ello con la condición de que el conflicto gráfica de $C$ es bipartito. $\square$

P. S. yo entiendo que la última parte de mi prueba no es lo suficientemente estricta sin embargo, si no está claro que puedo hacer foto o pensar acerca de la mejor descripción.