[manooooh]

Hola a todos! El ejercicio, copiado completo y literal, pide probar o refutar lo siguiente:

"Los grafos \( K_4 \) y \( K_{4,1} \) son isomorfos y existe un camino de Euler en cada caso".


A ver. Entiendo que \( K_4 \) es un grafo completo con 4 vértices, donde no tiene bucles ni aristas paralelas, ¿correcto? ¿El dibujo podría ser este?:



El grafo \( K_{4,1} \) no sé cómo representarlo, ¿quizás así?:



Luego la definición que tengo de Camino de Euler es que el grafo contiene todas las aristas, lo cual se cumple, ¿correcto?

Y por último la definición que tengo sobre dos grafos (simples) isomorfos es cuando sus matrices de adyacencia coinciden, lo cual no se cumple, ¿correcto? ¿Podrían ayudarme a cómo ver esto último, es decir, debo hacer las matrices de adyacencia? ¿Cómo?

Por tanto la proposición es FALSA.

Gracias!

Saludos

[Luis Fuentes]

Hola

Hola a todos! El ejercicio, copiado completo y literal, pide probar o refutar lo siguiente:

"Los grafos \( K_4 \) y \( K_{4,1} \) son isomorfos y existe un camino de Euler en cada caso".


A ver. Entiendo que \( K_4 \) es un grafo completo con 4 vértices, donde no tiene bucles ni aristas paralelas, ¿correcto? ¿El dibujo podría ser este?:



El grafo \( K_{4,1} \) no sé cómo representarlo, ¿quizás así?:



Luego la definición que tengo de Camino de Euler es que el grafo contiene todas las aristas, lo cual se cumple, ¿correcto?

No. Un camino de Euler es un camino que contiene todas las aristas del grafo exactamente una sola vez.

Una grafo conexo tiene un camino de Euler si y sólo si el número de vértices de grado impar es \( 0 \) o \( 2 \).

En el caso de \( K_4 \) todos los vértices tienen grado \( 3 \). Por tanto no tiene camino de Euler.

El el caso de \( K_{4,1} \) hay cuatro vértices de grado \( 1 \). Por tanto tampoco tiene camino de Euler.

Y por último la definición que tengo sobre dos grafos (simples) isomorfos es cuando sus matrices de adyacencia coinciden, lo cual no se cumple, ¿correcto? ¿Podrían ayudarme a cómo ver esto último, es decir, debo hacer las matrices de adyacencia? ¿Cómo?

Si son isomorfos tiene que exisitir una biyección entre su vértices que induzca una biyección entre las aristas. En particular vértices relacionados tienen que tener el mismo grado.

Pero todos los vértices de \( K_4 \) tienen grado \( 3 \); y de hecho ninguno de \( K_{4,1} \) tiene grado \( 3 \). Es imposible que sean isomorfos.

Saludos.

[manooooh]

Hola

Hola

Hola a todos! El ejercicio, copiado completo y literal, pide probar o refutar lo siguiente:

"Los grafos \( K_4 \) y \( K_{4,1} \) son isomorfos y existe un camino de Euler en cada caso".


A ver. Entiendo que \( K_4 \) es un grafo completo con 4 vértices, donde no tiene bucles ni aristas paralelas, ¿correcto? ¿El dibujo podría ser este?:



El grafo \( K_{4,1} \) no sé cómo representarlo, ¿quizás así?:



Luego la definición que tengo de Camino de Euler es que el grafo contiene todas las aristas, lo cual se cumple, ¿correcto?

No. Un camino de Euler es un camino que contiene todas las aristas del grafo exactamente una sola vez.

Una grafo conexo tiene un camino de Euler si y sólo si el número de vértices de grado impar es \( 0 \) o \( 2 \).

En el caso de \( K_4 \) todos los vértices tienen grado \( 3 \). Por tanto no tiene camino de Euler.

El el caso de \( K_{4,1} \) hay cuatro vértices de grado \( 1 \). Por tanto tampoco tiene camino de Euler.

Y por último la definición que tengo sobre dos grafos (simples) isomorfos es cuando sus matrices de adyacencia coinciden, lo cual no se cumple, ¿correcto? ¿Podrían ayudarme a cómo ver esto último, es decir, debo hacer las matrices de adyacencia? ¿Cómo?

Si son isomorfos tiene que exisitir una biyección entre su vértices que induzca una biyección entre las aristas. En particular vértices relacionados tienen que tener el mismo grado.

Pero todos los vértices de \( K_4 \) tienen grado \( 3 \); y de hecho ninguno de \( K_{4,1} \) tiene grado \( 3 \). Es imposible que sean isomorfos.

Saludos.

¡Entendido!

Gracias,
Saludos