3
$\begingroup$

Specifically, let $G$ be an undirected graph and $S$ and $T$ be two (possibly intersected) subsets of vertices, is the size of the minimum edge cut for $S$ and $T$ equal to the maximum number of pairwise edge-disjoint paths from $S$ to $T$?

Here a path from $S$ to $T$ means a path from a vertex $u$ in $S$ to a vertex $v$ in $T$ where $u\neq v$, and the minimum edge cut for $S$ and $T$ is the minimum number of edges whose removal cuts off all paths from $S$ to $T$.

Note the edge-connectivity version of Menger's theorem handles the special case where $S$ and $T$ are sets of a single vertex.

Intuitively this is true, but how to prove it? I tried to prove it from the max-flow min-cut theorem, but the trick of constructing a flow network by adding vertices $s$ and $t$ as well as edges from $s$ to $S$ and from $T$ to $t$ does not work because $S$ and $T$ may be intersected.

$\endgroup$
1
$\begingroup$

Of course, as with the ordinary Menger's theorem, we have a bound in one direction: if you have $k$ edge-disjoint paths from $S$ to $T$, then you need to delete at least $k$ edges to destroy all of them.

The converse does not hold. Consider the graph below, with $S$ the set of vertices circled in red and $T$ the set of vertices circled in blue:

counterexample

Here, the maximum number of pairwise edge-disjoint paths from $S$ to $T$ is just $1$: any path uses at least two edges, and there are only three edges.

On the other hand, if you delete any edge in this picture, the remaining two edges form a path from $S$ to $T$. So the minimum edge cut from $S$ to $T$ has size $2$.

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