Un gráfico con 7 vértices de grado 4 no puede ser plano. ¿Alguna pista sobre la prueba?
Respuestas
¿Demasiados anuncios?
Demuestre que el gráfico debe contener un $K_{3,3}$ configuración.
Elige cualquier par de vértices no adyacentes, $v_1$ y $v_2$ . Desde $v_1$ y $v_2$ cada uno tiene un grado $4$ y sólo hay $5$ otros vértices, deben tener al menos $3$ vecinos comunes.
Entonces, trata de encontrar un tercer vértice $v_3$ adyacentes a los mismos vecinos comunes, construyendo así $K_{3,3}$ .
Edición: Toma $v_1$ y $v_2$ como se ha descrito anteriormente. Deben tener al menos $3$ vecinos comunes (y como máximo $4$ ). Si tienen $4$ vecinos comunes, entonces el vértice restante comparte el mismo $4$ vecinos como $v_1$ y $v_2$ , por lo que esto forma un $K_{3,3}$ configuración.
Así que, digamos $v_1$ y $v_2$ compartir $v_3,v_4,v_5$ como vecinos comunes, con $v_1$ junto a $v_6$ y $v_2$ junto a $v_7$ .
Si $v_6$ y $v_7$ no son adyacentes, entonces cada uno comparte $v_3,v_4,v_5$ como vecinos comunes con $v_1$ y $v_2$ , dando un $K_{3,3}$ configuración.
Si $v_6$ y $v_7$ son adyacentes, entonces cada una es adyacente a exactamente dos de $v_3,v_4,v_5$ y, además, no pueden ser adyacentes al mismo par. Por tanto, digamos que $v_6$ es adyacente a $v_3,v_4$ y $v_7$ es adyacente a $v_4,v_5$ . Entonces, tenemos un $K_{3,3}$ configuración hecha de $v_1,v_2,v_6$ y $v_3,v_4,v_5$ donde el "borde" que conecta $v_6$ a $v_5$ pasa por $v_7$ .
Uma kant
Puntos
2160
En lugar de tratar de encontrar $4$ -grafos regulares en $7$ vértices, encontrar complementos de $4$ -grafos regulares en $7$ vértices. Estos son $2$ -regulares, por lo que un $C_7$ y un $C_3 \cup C_4$ .
En $C_7$ podemos tomar vértices $(1,2,3)$ y $(4,5,6)$ en dos particiones. Aunque $3$ y $4$ están conectadas, tendremos un camino entre $3$ y $4$ a través de $7$ en $\overline{C_7}$ por lo que tiene un menor isomorfo a $K_{3,3}$ .
En $C_3 \cup C_4$ , tomaremos $(1,2,3)$ [de $C_3$ ] y $(4,5,6)$ [de $C_4$ ] en dos particiones. Así que en $\overline{C_3 \cup C_4}$ tenemos un $K_{3,3}$ presente.
Por lo tanto, no hay planas $4$ -grafos regulares en $7$ vértices.
bentsai
Puntos
1886
Hasta el isomorfismo, hay dos $4$ -grafos regulares en $7$ vértices, que pueden ser enumerados exhaustivamente utilizando geng que viene con nauty . Son estos dos gráficos siguientes:
En el primer gráfico, destaqué un $K_{3,3}$ subgrafo en naranja (y por lo tanto no puede ser planar ya que $K_{3,3}$ no es planar).
En el segundo gráfico, he destacado un $K_{2,3}$ subgrafo en naranja. Observamos que identificando los dos vértices azules obtenemos un vértice adyacente a los tres vértices rojos, dando así un menor isomorfo a $K_{3,3}$ (eliminamos las aristas innecesarias). Así, Teorema de Wagner implica que esto también es no plano.
