(Actualización: para encontrar el resultado que termina la prueba.)
El muy grafos planares son precisamente las gráficas con el no $K_4$ menor. (Por cierto, estos son precisamente los de la serie-paralelo de los gráficos, a pesar de que estoy seguro de no ver la conexión.)
Comenzamos por probar los siguientes dos resultados, que nos $90\%$.
Si un gráfico de $G$ contiene una subdivisión de $K_4$, entonces no es muy plana.
Deje $v_1, v_2, v_3, v_4$ ser los vértices de $G$ tal, que hay distintos caminos de $v_i$ $v_j$cualquier $i \ne j$. A continuación, los caminos $v_1$ a $v_2$, $v_2$ a $v_3$, $v_3$ a $v_4$, e $v_4$ $v_1$forma un ciclo de $C$, lo que yo reclamo no es una cara de cualquier incrustación.
Si lo fuera, podríamos elegir una incrustación en el que $C$ es la cara exterior. Pero luego el camino de $v_1$ $v_3$divide $C$ en dos partes, con $v_2$ $v_4$ en diferentes partes; no puede ser conectado por un camino que no se vaya fuera de $C$ o se cruzan en el camino de$v_1$$v_3$.
Si un gráfico de $G$ no es muy plana, a continuación, contiene un $K_4$ menor.
(Nota: si un gráfico de $G$ no es plana, entonces tiene un $K_4$ menor, debido a que tanto $K_5$ $K_{3,3}$ $K_4$ menor. Así que voy a suponer que $G$ es plana, aunque no muy plana.)
Deje $C$ ser un ciclo de $G$ que no se puede convertir en una cara. Si nos quitan los vértices de $C$$G$, nos gustaría que nos dejó con la inconexión de la unión de los componentes conectados a $G_1, G_2, \dots, G_k$. Vamos a empezar con un plano de la incrustación de sólo $C$ (que obviamente ha $C$ como una cara), y añadir los componentes $G_1, \dots, G_k$ nuevo, de una en una, de modo que en cada paso, ya sea:
- continuamos con una planar de la incrustación de con $C$ como un rostro, o
- nos encontramos con un $K_4$ menor.
Cuando añadimos $G_i$ nuevo, contar cuántos vértices de $C$ tienen vecinos en $G_i$. Si es una o menos, entonces siempre podemos combinar el actual plano de la incrustación de $C$ con un plano de la incorporación de la $G_i$, poniendo a $G_i$ fuera de la cara $C$. Si es de tres o más, entonces podemos eliminar los bordes hasta que es tres, eliminar los componentes de $G_1, \dots, G_{i-1}$, y el contrato de $G_i$ a un punto a la izquierda con una subdivisión de $K_4$, que es un $K_4$ menor. Así que el único caso interesante es cuando sólo dos vértices $v_1, v_2$ $C$ tienen vecinos en $G_i$.
En ese caso, podemos combinar nuestros planos de la incrustación de $C$ con un plano de la incorporación de la $G_i$, poniendo a $G_i$ fuera de $C$, siempre podemos trazar un camino de$v_1$$v_2$, fuera de $C$, sin cruzar cualquiera de los bordes anteriores. Esto es posible, a condición de que ninguna anterior $G_j$, $j<i$, han tenido dos vecinos, $w_1, w_2$ $C$ ejemplo de que el camino de $w_1$ $w_2$le cruzan en el camino de$v_1$$v_2$. Pero si eso sucede, podemos contratar $G_i$ $G_j$ a un punto de desechar todos los demás componentes, y también obtener un $K_4$ menor.
Normalmente sería un problema para hacer malabares con las subdivisiones menores de edad y la manera en que yo estoy haciendo, pero resulta que en el caso de $K_4$, son equivalentes, por el siguiente reclamo.
Deje $H$ un gráfico con el máximo grado en la mayoría de los 3. A continuación, $H$ es menor de $G$ si y sólo si $G$ contiene una subdivisión de $H$.
Hay una cierta discusión de esta demanda en el MSE aquí, con tal vez una prueba y tal vez una fuente de darle una prueba, aunque la pregunta que el enlace podría merece algo más de atención.
