Can edge-connectivity version of Menger's theorem be generalized for two subsets of vertices?

693 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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