[Nub]

Hola, tengo el siguiente ejercicio:

1) Demostrar que existen infinitos grafos conexos,simples y 3-regulares.

No tengo idea de como empezar, lo que si se me viene a la mente es la formula de la suma de los grados es igual a la cantidad de aristas multiplicado por 2.

Gracias

[manooooh]

Hola

1) Demostrar que existen infinitos grafos conexos,simples y 3-regulares.

Lo que estuve experimentando con el grafo \( G \) que es conexo, simple y 3-regular es que mi conclusión ha sido que para generar otro grafo \( G' \) con las mismas condiciones, a \( G \) se le debe insertar 2 vértices unidos entre sí y que estén "en el medio" de dos aristas ya existentes (no sé si hay un nombre para esto).

Voy con un ejemplo:

Sea \( G=(V,E) \) el siguiente grafo que cumple las condiciones:

Ahora construiremos un nuevo grafo, \( G' \), en base a \( G \) de la siguiente manera:

1) Eliminamos una arista y agregamos un vértice que una los dos vértices que quedaron sin la arista que los unía.
2) Repetimos 1).
3) Conectamos los dos vértices con una arista.

Gráficamente:

Este nuevo grafo \( G' \) con 2 vértices y 5 aristas nuevas cumple las condiciones.

Así se puede repetir el proceso infinitamente. Te dejo que completes los detalles formalmente.

Saludos

[Nub]

Hola

1) Demostrar que existen infinitos grafos conexos,simples y 3-regulares.

Lo que estuve experimentando con el grafo \( G \) que es conexo, simple y 3-regular es que mi conclusión ha sido que para generar otro grafo \( G' \) con las mismas condiciones, a \( G \) se le debe insertar 2 vértices unidos entre sí y que estén "en el medio" de dos aristas ya existentes (no sé si hay un nombre para esto).

Voy con un ejemplo:

Sea \( G=(V,E) \) el siguiente grafo que cumple las condiciones:

Ahora construiremos un nuevo grafo, \( G' \), en base a \( G \) de la siguiente manera:

1) Eliminamos una arista y agregamos un vértice que una los dos vértices que quedaron sin la arista que los unía.
2) Repetimos 1).
3) Conectamos los dos vértices con una arista.

Gráficamente:

Este nuevo grafo \( G' \) con 2 vértices y 5 aristas nuevas cumple las condiciones.

Así se puede repetir el proceso infinitamente. Te dejo que completes los detalles formalmente.

Saludos

Es como medio algorítmico, se podría considerar como una demostración? y como lo formalizo, lo único que podría agregar es alguna notación o similar

[Luis Fuentes]

Hola

 Dada un grafo 3-regular con \( n \) vértices puedes demostrar que existe uno 3-regular de \( n+2 \) vertices.

 Para ello haces lo siguiente: dado un vértice \( v_1 \) del grafo original estará unido a otros dos (a tres, pero nos fijamos en dos) \( v_2,v_3 \). Eliminamos las aristas \( v_1-v_2 \) y \( v_1-v_3 \). Añadimos dos vértices más \( s,t \) y las aristas \( v_1-s,s-v_2,v_1-t,t-\color{red}v_3\color{black},s-t \).

 Al vértice \( v_1 \) le quitamos dos aristas adyacentes \( v_1-v_2 \) y \( v_1-v_3 \), pero le añadimos dos \( v_1-s \) y \( v_1-t \). Sigue teniendo grado \( 3 \).

 Al vértice \( v_2 \) le quitamos una arista adyacente \( v_1-v_2 \), pero le añadimos dos \( s-v_2 \). Sigue teniendo grado \( 3 \).

 Al vértice \( v_3 \) le quitamos una arista adyacente \( v_1-v_3 \), pero le añadimos dos \( t-v_3 \). Sigue teniendo grado \( 3 \).

 Los vértices \( s,t \) tienen grado \( 3 \) (fíjate en las aristas \( v_1-s,s-v_2,v_1-t,t-\color{red}v_3\color{black},s-t \)).

 Los demás vértices y sus aristas adyacentes no los hemos tocado.

 Por tanto tenemos un grafo de grado \( 3 \) con dos vértices más.

Saludos.

CORREGIDO

[Nub]

Para ello haces lo siguiente: dado un vértice \( v_1 \) del grafo original estará unido a otros dos (a tres, pero nos fijamos en dos) \( v_2,v_3 \). Eliminamos las aristas \( v_1-v_2 \) y \( v_1-v_3 \). Añadimos dos vértices más \( s,t \) y las aristas \( v_1-s,s-v_2,v_1-t,t-v_2,s-t \).

aquí hay un error de tipeo o estas haciendo algo diferente que manooooh?. No se como marcar pero añades una arista que va de \( v_1 \) a \( s \) y luego una de \( s \) a \( v_2 \) y luego otra de \( v_1 \) a \( t \) y luego de \( t \) a \( v_2 \) aca lo ultimo no seria a \( v_3 \)?

[Luis Fuentes]

Hola

Para ello haces lo siguiente: dado un vértice \( v_1 \) del grafo original estará unido a otros dos (a tres, pero nos fijamos en dos) \( v_2,v_3 \). Eliminamos las aristas \( v_1-v_2 \) y \( v_1-v_3 \). Añadimos dos vértices más \( s,t \) y las aristas \( v_1-s,s-v_2,v_1-t,t-v_2,s-t \).

aquí hay un error de tipeo o estas haciendo algo diferente que manooooh?. No se como marcar pero añades una arista que va de \( v_1 \) a \( s \) y luego una de \( s \) a \( v_2 \) y luego otra de \( v_1 \) a \( t \) y luego de \( t \) a \( v_2 \) aca lo ultimo no seria a \( v_3 \)?

Si, claro. Fue una errata al escribir. Ya lo he corregido.

Saludos.

[Nub]

Gracias a los dos