[Julio_fmat]

Sea \( G=(V,E) \) un grafo no trivial \( k \)-regular con \( k\ge 1. \) Pruebe que si \( k \) es par, entonces \( G \) no tiene puentes. ¿Es verdadera la recíproca?

[Luis Fuentes]

Hola

Sea \( G=(V,E) \) un grafo no trivial \( k \)-regular con \( k\ge 1. \) Pruebe que si \( k \) es par, entonces \( G \) no tiene puentes. ¿Es verdadera la recíproca?

Supón que tiene un puente y lo retiras. Considera una de las nuevas componentes conexas del grafo obtenida. Por una parte sabemos que en cualquier grafo conexo la suma de los grados de sus vértices es par; por otro lado los vértices de esa componente tienen grado \( k \), excepto el vértice anexo al puente que tiene grado \( k-1 \). Por tano la suma de los grados de sus vértices sería impar: contradicción.

En cuanto al recíproco piensa en el grafo completo de cuatro vértices.

Saludos.