For unconnected graphs, does Menger's Theorem hold?

44 Views Asked by At

If s and t are unconnected vertices, doesn't Menger's theorem not apply?

1

There are 1 best solutions below

0
On

If there are no $s,t$-paths, then Menger's theorem correctly tells us that the following are equal:

  1. The minimum number of vertices in an $s,t$-cut (which is $0$: we don't need to delete any vertices to disconnect $s$ from $t$).
  2. The maximum size of a family of internally disjoint $s,t$-paths (which is $0$: there are no $s,t$-paths).

Menger's theorem applies whenever $s$ and $t$ are not adjacent. That's the only exception (because if there is an edge $st$, then we can never disconnect $s$ and $t$ by deleting vertices).