4
$\begingroup$

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.

$\endgroup$
2
4
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.