[Julio_fmat]

Determine si la siguiente proposicion es verdadera o falsa. Justifique su respuesta.

No existe un grafo \( 4 \)-regular bipartito planar.

[martiniano]

Hola.,

Determine si la siguiente proposicion es verdadera o falsa. Justifique su respuesta.

No existe un grafo \( 4 \)-regular bipartito planar.

El siguiente párrafo es erróneo
Sólo hay un grafo bipartito 4-regular. ¿Sabrías decir cuál? Una vez hallado, si quitas un vértice de cada uno de los subconjutos obtienes un conocido grafo no planar, ¿cuál? Al tener un subgrafo no planar el grafo no puede ser planar. No creo que sea necesario, pero si no ves esto último también se puede aplicar Kuratowsky.

Un saludo.

[Luis Fuentes]

Hola

Sólo hay un grafo bipartito 4-regular. ¿Sabrías decir cuál?

¡Ojo!. ¿Seguro? Tenemos por ejemplo con \( 8 \) vértices divididos en dos grupos el grafo bipartito completo \( (4,4). \)

Pero por ejemplo con \( 10 \) vértices, \( \{a_1,a_2,a_3,a_4,a_5\}\cup \{b_1,b_2,b_3,b_4,b_5\} \) el que une cualquier par de vértices \( (a_i,b_j) \) con \( i\neq j. \)

Y hay más...

Saludos.

P.D. Hay un resultado que dice lo siguiente. Si un grafo no tiene ciclos de longitud tres y es planar entonces \( e\leq 2v-4 \), siendo \( e \) el número de aristas y \( v \) el de vértices.

Un grafo bipartito \( (n,m) \)  no tiene ciclos de longitud impar. Por otra parte si es \( 4 \)-regular el número de aristas es:

\( e=4n=4m \)

y por tanto \( n=m \) y los vértices son \( v=2n \). Entonces:

\( e=4n>4n-4=2v-4 \)

y por tanto NO puede ser planar.

[martiniano]

Hola.

Sí Luis. Tienes toda la razón. No sé por qué mi cabeza había asumido grafo bipartito completo. Así que lo que he dicho en mi anterior respuesta no sirve de mucho.

Espero no haber causado muchas confusiones. Un saludo.

[martiniano]

A ver si ahora sí que acierto.

Supongamos que existe un grafo bibartito 4-regular con \( 2n> 3 \) vértices. Sean:

\( A=4n \) el número de aristas.
\( V=2n \) el número de vértices.
\( R \) el número de regiones, incluida la exterior.

Como dicho grafo no tiene circuitos de longitud menor que 4, tenemos \( 2A\geq{}4R \)  \( \Rightarrow{} \)  \( A\geq{2R} \). Metiendo esto en la fórmula de Euler:

\( R+V=A+2\;\Longrightarrow{\;}2R+2V=2A+4\;\Rightarrow{\;}A+2V\geq{}2A+4\;\Rightarrow{\;}A\leq{2V-4} \)

Y esto es una contradicción.

Me he apoyado en la demostración de un corolario que tengo en mis apuntes que dice que en un grafo simple, conexo, planar, sin circuitos de longitud menor o igual que tres, y con tres vértices o más se cumple \( A\leq{2V-4} \)

A ver si ahora es la buena... Un saludo.

[Luis Fuentes]

Hola

A ver si ahora sí que acierto.

Supongamos que existe un grafo bibartito 4-regular con \( 2n> 3 \) vértices. Sean:

\( A=4n \) el número de aristas.
\( V=2n \) el número de vértices.
\( R \) el número de regiones, incluida la exterior.

Como dicho grafo no tiene circuitos de longitud menor que 4, tenemos \( 2A\geq{}4R \)  \( \Rightarrow{} \)  \( A\geq{2R} \). Metiendo esto en la fórmula de Euler:

\( R+V=A+2\;\Longrightarrow{\;}2R+2V=2A+4\;\Rightarrow{\;}A+2V\geq{}2A+4V\;\Rightarrow{\;}A\leq{2V-4} \)

Y esto es una contradicción.

Me he apoyado en la demostración de un corolario que tengo en mis apuntes que dice que en un grafo simple, conexo, planar, sin circuitos de longitud menor o igual que tres, y con tres vértices o más se cumple \( A\leq{2V-4} \)

A ver si ahora es la buena... Un saludo.

Si, era más o menos lo que había añadido en mi postdata. Lo que pasa es que fuiste tan rápido contestando que probablemente aun no lo había escrito. Modifiqué el mensaje a los pocos minutos de escribirlo y no lo indiqué porque no pensé que nadie lo viese tan inminentemente. 

Saludos.

[martiniano]

Hola.

Si, era más o menos lo que había añadido en mi postdata. Lo que pasa es que fuiste tan rápido contestando que probablemente aun no lo había escrito. Modifiqué el mensaje a los pocos minutos de escribirlo y no lo indiqué porque no pensé que nadie lo viese tan inminentemente. 

Sí, justo es lo que ha pasado  . Venga pues, un saludo.