[Paula PB]

Hola, a ver si me podéis ayudar con el siguiente ejercicio:

Demuéstrese que todos los subgrafos \( (k-2) \)-regulares de \( K_k \) son isomorfos a \( K_{k-1} \) para \( k \) impar.

Entiendo que, siendo k impar, todos los grafos k-regulares tienen un número de vértices par, y lo mismo pasa con los subgrafos (k-2)-regulares. Por contra, los subgrafos (k-1) pueden tener un número de vértices par o impar.

Por otra parte, para que dos grafos sean isomorfos han de tener el mismo número de vértices y estos han de guardar las relaciones de adyacencia con el resto de vértices, ¿no?

Bueno, entonces, ¿cómo puede ser un grafo k-2 isomorfo a otro k-1 si el grado de sus vértices es distinto?

[Luis Fuentes]

Hola

Hola, a ver si me podéis ayudar con el siguiente ejercicio:

Demuéstrese que todos los subgrafos \( (k-2) \)-regulares de \( K_k \) son isomorfos a \( K_{k-1} \) para \( k \) impar.

Entiendo que, siendo k impar, todos los grafos k-regulares tienen un número de vértices par, y lo mismo pasa con los subgrafos (k-2)-regulares. Por contra, los subgrafos (k-1) pueden tener un número de vértices par o impar.

Correcto.

Por otra parte, para que dos grafos sean isomorfos han de tener el mismo número de vértices y estos han de guardar las relaciones de adyacencia con el resto de vértices, ¿no?

Correcto.

Bueno, entonces, ¿cómo puede ser un grafo k-2 isomorfo a otro k-1 si el grado de sus vértices es distinto?

Aquí te estás liando. El grado \( K_{k-1} \) es el grafo completo con \( k-1 \) vértices; todos sus vértices tienen grado \( k-2 \). Por tanto es un grafo \( k-2 \) regular.

Entonces la prueba de lo que te piden iría así:

1- Sea \( G \) un subgrafo de \( K_k \), \( k-2 \) regular. Por ser subgrafo de \( K_k \), a lo sumo tiene \( k \) vertices.
2- Dado que todo vértice de \( G \) tiene grado \( k-2 \) al menos tiene que tener \( k-1 \) vértices.
3- De (1) y (2), \( G \) tiene \( k \) vértices o \( k-1 \) vértices.  Pero como bien dijiste si \( k \) es impar, el número de un grafo \( k-2 \) regular tiene que ser par; por tanto \( G \) NO puede tener \( k \) vértices y necesariamente tiene \( k-1 \) vértices.
4- Pero en un grafo \( k-2 \) regular con \( k-1 \) vértices, todo vértice tiene grado \( k-2 \) y por tanto está conectado con todos los otros \( k-1 \) vértices: es decir es el grado completo \( K_{k-1} \).

Saludos.

[Paula PB]

Muchas gracias.

Entonces, si te piden que encuentres un subgrafo 2-regular de \( K_4 \) no isomorfo a \( K_3 \), sería imposible porque todos los grafos 2-regulares con tres vértices son completos, ¿no?

[Luis Fuentes]

Hola

Muchas gracias.

Entonces, si te piden que encuentres un subgrafo 2-regular de \( K_4 \) no isomorfo a \( K_3 \), sería imposible porque todos los grafos 2-regulares con tres vértices son completos, ¿no?

No. Es cierto que todos los grafos 2-regulares con tres vértices son completos, pero podríamos tomar un grafo con \( 4 \) vértices y \( 2 \)-regular: un  cuadrado.

Saludos.