2
$\begingroup$

So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ?


$\text{My Attempt at the Proof}$:-

Suppose there isn't , then there must be at-least one edge common in both the paths , and if we remove it then it disconnects $G$ and thus is a bridge. As there are no Bridges , Hence Proved !


$\text{Why I feel this Proof is incorrect }$:-

Suppose the exits three paths from u to v.

Path 1 :- $u$ ----> $E_1$ -----> $E_2$ -----> $v$

Path 2 :- $u$ ----> $E_2$ -----> $E_3$ -----> $v$

Path 3 :- $u$ ----> $E_1$ -----> $E_3$ -----> $v$

(here -----> represents some path and $E_1 , E_2 , E_3$ represent Edges.

This is an example which violates the above property. It has no bridges as well as no edge disjoint paths.

Can someone either Prove or disprove this Property ? I am really confused.

$\endgroup$
2
  • $\begingroup$ I'm confused. Paths 1 and 3 share edge $E_1$ so they are not edge-disjoint. And you want to prove the existence of two, not three edge-disjoint paths in your statement. $\endgroup$ Apr 3, 2020 at 9:53
  • $\begingroup$ I was just trying to think of a counter example to my proof. My Proof is wrong for sure. I wanted to prove the statement , could you help me with the proof. I want to prove the existence of atleast two edge disjoin paths in $G$ $\endgroup$ Apr 3, 2020 at 11:17

1 Answer 1

1
$\begingroup$

Yes, it is true that there exist two edge-disjoint paths between any two vertices in a connected bridgeless graph.

Define a closed trail as a trail whose last vertex is its first vertex. Note, a trail contains two edge-disjoint paths between any two of its vertices.

Trail combining lemma. Let $G$ be a graph. Suppose a closed trail passes vertex $v$. Another closed trail passes vertex $u$. If those two trails share one vertex, there is a closed trail that passes both $u$ and $v$.

Proof. You can convince yourself easily by drawing a few situations. Done.


Let us prove the following proposition.

A graph is connect and bridgeless if and only if any two vertices are included in a closed trail.

Proof.

"$\Leftarrow$": Obvious.

"$\Rightarrow$": Suppose $G$ is connected and bridgeless. $v$ and $w$ are two vertices.

Let $$T_v=\{u : u \text{ is a vertex of } G \text{ such that there is closed trail that passes }v\text{ and } u\}.$$ Suppose $u\in T_v$ and $s$ be a neighboring vertex of $u$, i.e., $\{u,s\}$ is an edge.

  • There is a closed trail that passes $v$ and $u$ by the definition of $T_v$.

  • There is a closed trail that passes $u$ and $s$, since edge $\{u,s\}$ is not a bridge.

Thanks to the lemma, we have a closed trail that passes $v$ and $s$. In other words, $T_v$ contains all neighborhoods of all its vertices. That means $T_v$ (with all edges between its points) is a connected component, which must be $G$ itself. In particular, there is a closed trail that passes $v$ and $w$. Proof is complete.


A very similar characterization of bridgeless connected graphs is Robbins' theorem. If $G$ is connected and bridgeless, that theorem says we can choose a direction for each edge of $G$, turning it into a directed graph that has a path from every vertex to every other vertex.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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