Gráfico conectado $G$ sin puentes, de manera que $G\!\setminus\!e$ es un árbol

Question

Dejemos que $G$ sea un grafo conexo de orden $n \ge 3$ sin puentes y supongamos que $G\!\setminus\!e$ es un árbol para cada arista $e$ del gráfico $G$ . ¿Qué es? $G$ ? Demuestre su respuesta

Mi intento:

Prueba : Afirmo que $G$ es $C_{n}$ . Dejemos que $G=(V,E)$ , entonces para todos los $e \in E$ , $G\!\setminus\!e$ será $P_{n-1}$ que es un árbol.

¿Es esto correcto? ¿Cómo puedo mejorarlo?

Answer 1

Como se explica en los comentarios su prueba sólo muestra que todas las gráficas de los ciclos $C_n$ tienen la propiedad deseada, pero todavía hay que demostrar que sólo Los gráficos de los ciclos tienen esa propiedad. El resto de tu prueba podría ser algo así:

Suponga que tiene un gráfico $G$ que no es un gráfico de ciclo $C_n$ . Si $G$ es un árbol, entonces debe contener un puente, por lo que no puede tener la propiedad deseada. En caso contrario, $G$ contiene un ciclo y al menos una arista $e$ que no forma parte de ese ciclo. Desde $G\!\setminus\!e$ todavía tiene un ciclo, no puede ser un árbol. Así que sólo los gráficos de ciclos $C_n$ tienen la propiedad deseada.