Prove that every edge in a tree is bridge

Question

I have found this link

Which apparently ask same question like me right now. But, the answers don't provide me information to solve the problem. Once again, I have read many times about what was discussed in the comments, but still I don't understand. This one: @JAEMTO Ok. Suppose there is an edge AB which is not a bridge. Then after removing it there is a path from A to B. That path cannot involve the edge AB because you have just removed it. So how does that give you a contradiction?

The theorem may be simple to solve, but somehow I can't proceed how to prove it.

Please help me. Regards.

Answer 1

If there are two paths from a vertex $A$ to a vertex $B$, there must be a cycle containing the vertices $A$ and $B$ as well. Therefore, when we remove the edge $AB$ in a tree, if there is still a path from $A$ to $B$, then the graph cannot be tree because it has a cycle.

But I suggest you to use induction for these kind of proofs. Suppose we have a tree with $n$ vertices $T_n$ (vertices are $x_0$, $x_1$,..., $x_n$). The case $n=1$ is trivial. For $n = 2$, $T_2$ has only one edge $x_0x_1$ and when we remove it, we get a disconnected components $x_0$ and $x_1$ so $x_0x_1$ is a bridge. Now, suppose inductively that $n \ge 3$ and every edge of $T_n$ is a bridge. Then, for $n+1$, since we are adding a new vertex to $T_n$, we also add only one edge to $T_n$. Without loss of generality, say we add $x_{n+1}$ as a vertex and the new edge is $x_nx_{n+1}$. Then, when we remove $x_nx_{n+1}$, we will get two disconnected components $T_n$ and $x_{n+1}$ so $x_nx_{n+1}$ is a bridge. Remember that in the inductive argument, we assumed every edge of $T_n$ is a bridge, therefore every edge in $T_{n+1}$ is also a bridge. So, by induction, the argument holds for all $n$.

Answer 2

Don't need induction: Let $G$ be a tree, and suppose that one of its edges $\{v,w\}$ is not a bridge. This implies that removing this edge does not disconnect $G$, i.e., if $G'$ is the graph $G$ with $\{v,w\}$ removed, $G'$ is connected. Hence, there exists a path connecting vertices $v$ and $w$ in $G'$. This path together with $\{v,w\}$ forms a cycle in $G$, which contradicts the assumption that $G$ is a tree. Therefore, every edge in $G$ must be a bridge.