# Bridges and Edge Disjoint Paths

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.

• 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. – Anthony Labarre Apr 3 '20 at 9:53
• 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$ – rajdeep dhingra Apr 3 '20 at 11:17

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.