¿Por qué un gráfico de 9 vértices cuyo complemento está en 3 componentes no puede ser plano?

Question

Dejemos que $G$ sea un gráfico con 9 vértices cuyo complemento $\overline{G}$ tiene tres componentes.

He leído que no puede ser planar, pero estoy teniendo problemas para completar una prueba.

La mayoría de las formas de distribuir los 9 vértices entre los 3 componentes de $\overline{G}$ obligaría a $G$ para ser no planar, está claro para mí. Por ejemplo, si 6 vértices estuvieran en un componente, 2 en otro y 1 en el último, entonces en $G$ 3 vértices cualesquiera de ese componente de 6 vértices estarían completamente conectados a los vértices de los otros 2 componentes, es decir $K_{3,3}$ sería un subgrafo de $G$ Así que $G$ sería no planar.

Este argumento funciona cuando el componente mayor tiene 5 vértices, 4 vértices o incluso 3 vértices.

Queda un caso: cuando 7 vértices se conectan en un componente en $\overline{G}$ y los otros 2 vértices son puntos aislados. ¿Por qué debe $G$ ser no planas en este caso?

Answer 1

De hecho, la afirmación es errónea: $G$ pueden ser planas.

Supongamos que el componente de tamaño 7 en $\overline{G}$ es la camarilla; entonces $G$ es el gráfico tripartito $K_{1,1,7}$ , que es planar: