Dado un grafo $G$ $7$ vértices, $G$ o su complemento debe ser plana.
La cosa más cercana a esta pregunta, que he encontrado en internet es este , pero ya que se utiliza la fórmula de Euler, no los puedo usar para probar planaridad. He tratado de enfoque es el uso de Kuratowski y de Wagner Teorema pero no puedo averiguar cómo. La suma de los bordes de $G$ y su complemento debe ser igual a $21$, con lo cual no me ayuda porque dos $K_5$ subdiagramas sólo tienen $20$ bordes.
Respuesta
¿Demasiados anuncios?
bof
Puntos
19273
Supongamos $G$ es un no plana gráfico de la orden de $7.$ Por el teorema de Kuratowski, $G$ tiene un subgrafo $H$ que es una subdivisión de la $K_5$ o de una subdivisión de $K_{3,3}.$ Una subdivisión de $K_5$ $5$ vértices de grado $4$; una subdivisión de $K_{3,3}$ $6$ vértices de grado $3.$ Si $H$ es una subdivisión de $K_5,$ $\bar G$ tiene al menos $5$ vértices de grado $\le2,$ y por tanto (por el teorema de Kuratowski) debe ser plana. Por lo tanto, podemos suponer que la $H$ es una subdivisión de $K_{3,3}.$ Desde $G$ sólo ha $7$ vértices, $H=K_{3,3},$ o de lo $H$ se obtiene a partir de a $K_{3,3}$ mediante la sustitución de uno de los bordes de $K_{3,3}$ con un camino de longitud $2.$ En cualquiera de los casos es fácil comprobar que la gráfica de $K_7-E(H)$ (y por tanto su subgrafo $\bar G$) es planar.
Por otro lado, el gráfico de $G=K_{3,3}+2K_1$ es un no plana gráfico de la orden de $8$ cuyo número de independencia es $5$; por lo tanto $G$ $\bar G$ son no plana gráficos.
