Graph Theory37 sections · 1633 units
Open in Course

Disjoint Paths

(Counting independent routes)

The maximum number of edge-disjoint paths from source to sink equals the max flow when all edges have capacity 11. Each unit of flow corresponds to one path. Since capacities are 11, paths do not share edges. Similarly, the maximum number of vertex-disjoint paths (paths sharing no internal nodes) can be found using vertex capacities set to 11.

This connects flow to graph connectivity. The integer flow theorem guarantees paths are discrete.