Teoría de grafos: ciclos

Question

Demostrar que si dos ciclos distintos de un grafo $G$ contienen cada una una arista $e$ entonces $G$ tiene un ciclo que no contiene $e$ .

Mi planteamiento es que como ambos tienen la arista e entonces si eliminamos la arista $e$ de ambos y luego unir los dos ciclos en el vértice $a$ y $b$ qué borde $e$ conectado a entonces obtendríamos un ciclo. ¿Me he perdido algo?

No es una pregunta de deberes, sino de mi libro de texto.

Answer 1

La idea es correcta. El problema viene cuando los dos ciclos tienen otro borde en común además de "e". ¿Cómo se gestiona ese caso? ¿Es necesario utilizar la hipótesis de que los dos ciclos son distintos?

Answer 2

Otro enfoque sería tomar el componente conectado que contiene ambos ciclos y observar que en este subgrafo $|E| \geq |V|+1$ . Para ser más explícitos:

• $|E| \leq |V|-2$ el gráfico no estaría conectado,
• $|E| = |V|-1$ el grafo sería un árbol (sin ciclos),
• $|E| = |V|$ el gráfico tendría exactamente un ciclo,
• $|E| \geq |V| + 1$ es la única posibilidad.

Entonces, si eliminamos $e$ tenemos $|E - \{e\}| \geq |V|$ lo que sigue implicando la existencia de algún ciclo, que, por supuesto, no puede contener $e$ (no es necesario, pero si te lo preguntas, este componente conectado sigue conectado porque $e$ era una arista de un ciclo).

Espero que le sirva de ayuda ;-)

Answer 3

Creo que es bastante sencillo de ver. Imaginar a los ciclos $C_n$ y $C_m$ que comparten un vértice común $e$ . Si borras esta arista, aún tendrás que ambos ciclos coinciden exactamente en 2 vértices. Ahí tienes el ciclo.