Let be a connected Graph and are not connected
The minimum size of Separator is the maximum number
of disjoint paths from to .
Equivalently if all separators have size at least
then there exist disjoint paths from to .
Proof
Setup
Suppose it is not true.
Then it has a counterexample for some , assume is smallest
Note , as the theorem holds for
Let be the set of counterexamples for that
Let be a counterexample with the least number of edges.
For each in , define to be the size of smallest separator.
Suppose are counterexamples in
with a maximum of disjoint paths from to
Let be the minimum separator
Then
Step 1
There is a minimum separator which is neither nor
To prove this, assume WLOG
If , then let
Consider
In there is at most disjoint paths from to
(if there was more then in we can always add back the path )
By minimality, there is a separator of size in
But then is a separator in
Hence assume
Let be the shortest path from to
where
As this is the shortest path, we know
Also
Now let
Now otherwise there is a smaller counterexample
So let be a separator of in with size
Then and are both separators of in
Now note and
Also if and
then
And thus we found a separator of that is neither nor
Step 2 (main idea)
Let be connected component of in and similarly
Let be the graph with vertices
and added edges
and graph with vertices
and added edges
We can think of as collapsing into
and adding the edges from to all of
Every point of has at least one edge going towards
(otherwise there is a smaller separator)
Also so there is an edge going out of not to
Thus we have removed at least edges.
Now has less edges than
Similar for
Then and
( is a separator, and if there was a smaller one then it would separate )
Now as and are not counterexamples, by minimality,
so there are disjoint paths from to
and disjoint paths from to
and we can concatenate them to find disjoint paths from to
Corollary
Let be connected with
Then is -connected if and only if all pairs of
admit disjoint paths from to .
Corollary
Let be connected with
Then is -connected if and only if
for any with and
there are at least disjoint paths from to