# How to find the maxium number of edge-disjoint paths using flow network

Given a graph $G=(V,E)$ and $2$ vertices $s,t \in V$, how can I find the maximum number of edge-disjoint paths from $s$ to $t$ using a flow network? $2$ paths are edge disjoint if they don't have any common edge, though they may share some common vertices.

Thank you.

-

## 2 Answers

Hint: if each edge has a capacity of one unit, different units of stuff flowing from $s$ to $t$ must go on edge-disjoint paths.

-

This is a well known problem.

See https://en.wikipedia.org/wiki/Maximum_flow_problem, section 5.5.

-