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?
