Demostrar que cada arista de un árbol es un puente

Question

He encontrado este enlace

Que al parecer se preguntan lo mismo que yo ahora mismo. Pero, las respuestas no me proporcionan información para resolver el problema. Una vez más, he leído muchas veces sobre lo que se discutió en los comentarios, pero todavía no entiendo. Este: @JAEMTO Ok. Supongamos que hay una arista AB que no es un puente. Entonces después de quitarla hay un camino de A a B. Ese camino no puede involucrar la arista AB porque la acabas de quitar. Entonces, ¿cómo te da eso una contradicción?

El teorema puede ser sencillo de resolver, pero de alguna manera no puedo proceder a demostrarlo.

Por favor, ayúdenme. Saludos.

Answer 1

Si hay dos caminos desde un vértice $A$ a un vértice $B$ debe haber un ciclo que contenga los vértices $A$ y $B$ también. Por lo tanto, cuando eliminamos el borde $AB$ en un árbol, si todavía hay un camino desde $A$ a $B$ entonces el gráfico no puede ser un árbol porque tiene un ciclo.

Pero te sugiero que uses la inducción para este tipo de pruebas. Supongamos que tenemos un árbol con $n$ vértices $T_n$ (los vértices son $x_0$ , $x_1$ ,..., $x_n$ ). El caso $n=1$ es trivial. Para $n = 2$ , $T_2$ sólo tiene una arista $x_0x_1$ y cuando lo quitamos, obtenemos unos componentes desconectados $x_0$ y $x_1$ así que $x_0x_1$ es un puente. Ahora, supongamos inductivamente que $n \ge 3$ y cada borde de $T_n$ es un puente. Entonces, para $n+1$ ya que estamos añadiendo un nuevo vértice a $T_n$ también añadimos una sola arista a $T_n$ . Sin pérdida de generalidad, digamos que añadimos $x_{n+1}$ como vértice y la nueva arista es $x_nx_{n+1}$ . Entonces, cuando eliminamos $x_nx_{n+1}$ obtendremos dos componentes desconectados $T_n$ y $x_{n+1}$ así que $x_nx_{n+1}$ es un puente. Recuerda que en el argumento inductivo, asumimos que cada arista de $T_n$ es un puente, por lo que cada arista en $T_{n+1}$ también es un puente. Entonces, por inducción, el argumento es válido para todos $n$ .

Answer 2

No necesitas la inducción: Deja que $G$ sea un árbol, y supongamos que una de sus aristas $\{v,w\}$ no es un puente. Esto implica que la eliminación de esta arista no desconecta $G$ es decir, si $G'$ es el gráfico $G$ con $\{v,w\}$ eliminado, $G'$ está conectado. Por lo tanto, existe un camino que conecta los vértices $v$ y $w$ en $G'$ . Este camino junto con $\{v,w\}$ forma un ciclo en $G$ lo que contradice la suposición de que $G$ es un árbol. Por lo tanto, cada arista en $G$ debe ser un puente.