Se trata de un ejercicio sobre un libro de nuevo. Si un simple gráfico $G$ tiene 11 o más vértices, entonces G o su complemento $\overline { G } $ no es planar.
¿Cómo empezar con esto? ¿Inducción?
Gracias por su ayuda.
De la fórmula de Euler se deduce que un gráfico plano simple $G$ con $m$ bordes y $n\geq 3$ vértices debe satisfacer (ver aquí ) $$\tag{1}m\leq 3n-6.$$ Para un gráfico $G$ con $m$ bordes y $n$ vértices, su complemento $\overline{G}$ tiene $\displaystyle\frac{n(n-1)}{2}-m$ bordes. Por lo tanto, si $\overline{G}$ también es planar, por $(1)$ tenemos $$\tag{2}\frac{n(n-1)}{2}-m\leq 3n-6.$$ Añadir $(1)$ y $(2)$ obtenemos $$\frac{n(n-1)}{2}\leq 6n-12,$$ lo que implica que $n\leq 10$ .
Oh, el libro que estoy leyendo ahora no tiene esta fórmula m3n6 ... Ahora parece que no es un buen libro.
@YoTengoUnLCD Por supuesto. Lo que esto demostró fue que al menos uno de $G$ y $\overline{G}$ deben ser no planas. Si desea construcciones específicas de grafos no planos cuyos complementos también son no planos, vea por ejemplo esta pregunta .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Tal vez usando el teorema de Kuratowki.
4 votos
O quizás la fórmula de Euler. ¿Cuál es el número máximo de aristas que puede tener un grafo plano simple con 11 vértices?