Deje $G$ ser un simple plano gráfico con al menos $2$ vértices, y deje $G^*$ ser el doble de un plano de la incorporación de la $G$. Probar que si $G$ es isomorfo a$G^*$ ,, a continuación, $G$ no es bipartito.
No tengo absolutamente ninguna idea de cómo empezar esto, alguien puede darme algunas buenas sugerencias? TY.
Si es bipartito puede el color de sus vértices (alternando) en blanco y negro. Ya que es isomorfo a su doble, a continuación, también puede color alternando entre rojo y verde de las caras (en un plano de incrustación de objetos). Esto significa que ningún vértice tiene grado mayor que tres. De manera que la gráfica debe ser distinto de la unión de un montón de ciclos, junto con las cadenas. Si el ciclo tiene más de dos bordes, a continuación, el dual y, por tanto, la gráfica tiene vértices con más de dos filos. Así, sólo los ciclos de dos vértices. No hay cadenas, porque entonces el dual tiene bucles y un bipartito no pueden tener ellos. No puede haber muchos ciclos disjuntos, ya que tenemos en el doble y, a continuación, en el gráfico de los vértices con más de dos filos. Por lo tanto es sólo un ciclo con dos bordes. Pero esto funciona, ¿no?
Supongo que el problema debe decir "más de $2$ vértices".
Oh! Se dice, simple gráfico. Esto no es un simple gráfico. Así, ok. Entonces es correcto. El ciclo con dos bordes no funciona bien. QED el gráfico no puede ser bipartito.
Deje $n$ el número de vértices de $G$. A continuación, $G^*$ también ha $n$ vértices que significa $G$ ha $n$ caras. El uso de $V-E+F=2$, obtenemos $$E=2n-2 \,.$$
Si $n=2$ entonces $V=E=2$ que no es posible.
De lo contrario, el grafo es planar y bipartito*, tenemos $E\leq 2V-4$, y por lo tanto $$2n-2 \leq 2n-4$$ contradicción.
*Que realmente sólo se utiliza ese $G$ no tiene ningún tipo de $3$-ciclo.
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.
