Probar nonplanarity de un gráfico

Question

Así que estoy trabajando para demostrar que cualquier gráfico $G=(V,E)$ $|V|\geq11$ será ya sea no plana sí mismo, o su complemento $G^\complement$ será no plana.

Mi texto dice que para probar nonplanarity, uno debe demostrar que el gráfico tiene un subgráfico que es homeomorfa a o $K5$ o $K{3,3}$.

Mi pregunta es: ¿Sería suficiente para demostrar que es imposible para $G$ y $G^\complement$ que no plana?

Answer 1

No hay necesidad de aplicar el teorema de Kuratowski aquí. Vamos a utilizar el hecho de que un plano gráfico no tiene demasiadas aristas.

Lema: Si $G(V,\ E)$ satisface $|E| > 3|V| - 6$ $G$ no es planar.

Ahora considere los bordes de la gráfica y el complemento de $\overline{G}(V,\ E')$. Los bordes de satisfacer $$|E| + |E'| = \binom{|V|}{2} = \frac{|V|^2 - |V|}{2}$$ Por tanto, al menos uno de los dos gráficos que debe tener al menos $\frac{|V|^2 - |V|}{4}$ bordes. Mirando la desigualdad $$\frac{|V|^2 - |V|}{4} > 3|V| - 6 \implies |V|^2 - 13|V| + 24 > 0$$ Esta desigualdad se satisface para $|V| \ge 11$ y de ahí el resultado.

Como nota de interés, se ha demostrado (a través de análisis de caso por caso) que se puede reducir el número de vértices a$9$, mientras que la retención de esta propiedad. $9$ es el menor número de vértices tales que cualquiera de las $G$ o $\overline{G}$ no es planar.