Menger's theorem - Graphs & Stuff

After discussing connectivity and edge-connectivity, I want to present a theorem that gives us a different prespecive about those terms. To do so, I will present and prove Menger’s theorem, this theorem will help us deduce some great conclusions about connectivity!

Before I’ll present the theorem though, I want to define a new term – a contraction of a graph:

Contraction

Suppose that $G=(V,E)$ is a graph and $e_0\in E$ is an edge in it. Intuitively, the contraction along $e_0$ is the new graph that you get when you ‘squish’ the edge $e_0$ and identify it’s endpoints as the same vertex:

Now that we have intuition let’s define it formally. The new graph will be denoted as $G|_{e_0}$ The vertices that are not the endpoints of $e_0$ will still be on this graph. The endpoint of $e_0$ on the other hand, are now considered as one. We will think of them as they removed and induced a new vertex – $\{v_{e_0}$ .

Just for comfort purposes, let’s denote the endpoints of $e_0$ as $v$ and $u$ . Hence that set of vertices is:

(V\setminus\{u,v\})\cup\{v_{e_0}\}

So Now, what about the edges?

Well, if $e\neq e_0$ and neither of it’s endpoints are $u$ or $v$ , then $e$ will also be in $G|_{e_0}$ . Those are exactly the edges that are in the set:

\{e\in E:e\cap\{u,v\}=\emptyset\}

But that’s not all, we still have the edges with one endpoint that is $u$ or $v$ . But they are exactly the edges that have one endpoint in the new vertex – $\{v_{e_0}\}$ . Therefore, the set of edges will be:

\{e\in E:e\cap\{u,v\}=\emptyset\}\cup\{e\neq e_0:u\in e \text{ or } v\in e\}

In total, we define the contraction along $e_0$ to be the graph:

G|_{e_0}=((V\setminus\{u,v\})\cup\{v_{e_0}\},\{e\in E:e\cap\{u,v\}=\emptyset\}\cup\{e\neq e_0:u\in e \text{ or } v\in e\} )

I think it’s clear now why I prefered to show the intuition first… It’s definition seems pretty comlicated even though it is absolutely not!

Vertex separator

Suppose that $A,B\sub V$ are sets of vertices in a graph $G=(V,E)$ . We say that a set $S$ is an $AB$ -separator if in $G\setminus S$ there are no paths between vertices in $A$ to vertices in $B$ .

Here, we can clearly see that removing $S$ yields a graph with no paths from $A$ to $B$

I thinks that this definition is pretty clear and this image makes it 10 times clearer, so I let’s see the next definition.

Vertex Disjoint paths

Vertex disjoint paths are just what you think they are. They are paths that don’t share a common vertex. We will be interested in the number of vertex disjoint paths between two sets, $A$ and $B$ .

For example, Here:

There are 3 dijoint paths from $A$ to $B$ . However, there are other ways to select different dijoint paths, and those might lead to different number of paths…

Moreover, if $A$ and $B$ interesects, then each vertex in the intersection forms a path – from and to itself (it is a path of length 0, since it involved no edges). Remember this fact, we’ll need it soon.

The theorem

Menger’s theorem shows us a connection between the maximal number of disjoint paths and the minimal size of a vertex separator set. The goes like this:

Let $G=(V,E)$ be a graph. Suppose that $A\neq B$ are sets of vertices of $G$ . Then, the maximal size of collection of disjoint paths from $A$ to $B$ is the same as the minimal size of an $AB$ -separator set.

If we denote the maximal size disjoint paths from $A$ to $B$ as $P_{\text{max}}(AB)$ and the minimal size of an $AB$ -separator set as $S_{\text{min}}(AB)$ then the theorem states that:

P_{\text{max}}(AB)=S_{\text{min}}(AB)

The proof

I am going to prove it in two parts, first I’ll show that $P_{\text{max}}(AB)\leq S_{\text{min}}(AB)$ and then I’ll prove that $P_{\text{max}}(AB)\geq S_{\text{min}}(AB)$ . Let’s do it:

Part 1 – $P_{\text{max}}(AB)\leq S_{\text{min}}(AB)$

Let’s denote $P_{\text{max}}(AB) = k$ . And now, let $P_1,P_2,\dots,P_k$ be vertex disjoint paths from $A$ to $B$ .

Now, Suppose that $S$ is some arbitrary $AB$ -separator. Since after removing $S$ , there are no paths from $A$ to $B$ , at least one vertex has been removed from each of the paths $P_1,P_2,\dots,P_k$ . That is:

|P_i\cap S|\geq 1\text{ for every } 1\leq i\leq k

However, since the paths are vertex dijoint, we have removed a different vertex from every path $P_i$ . Hence, $S$ contains at least $k$ vertices and we can now conclude:

P_{\text{max}}(AB)=k\leq |S|

However, $S$ was an arbitrary $AB$ -separator, thus, this inequality applies to the minimal $AB$ -separator as well. Therefore:

P_{\text{max}}(AB)\leq S_{\text{min}}(AB)

As we wanted.

Part 2 – $P_{\text{max}}(AB)\geq S_{\text{min}}(AB)$

This part is going to be done by induction on the number of edges in $G$ .

Base case

If $E$ is empty then the the only paths we have between $A,B$ are the path with zero-length from a vertex to itself. And how many are there? exactly $|A\cap B|$ . However, this is also the number of the minimal separator set. So not only $P_{\text{max}}(AB)$ is smaller than $S_{\text{min}}(AB)$ , they are actually the same!

General case

For the general case, we will have to work harder. We are going to aim for contradiction and assume that:

P_{\text{max}}(AB)< S_{\text{min}}(AB)=k

That is, there are no $k$ vertex disjoint paths from $A$ to $B$ . The trick here is to look at a contraction of the graph and apply the induction on it. So let’s pick some edge $e=\{x,y\}\in E$ and denote the contraction $G|_{e}$ by $G^\prime$ .

Now, what happened to the sets $A$ and $B$ ?

If $x\in A$ or $y\in A$ then $A$ now ‘lost’ one vertex (or two) and ‘gained’ the new vertex – $v_e$ . If both $x$ and $y$ are not in $A$ , then it hasn’t changed. Either way, we’ll denote the ‘new’ $A$ by $A^\prime$ .

The same arguments apply to $B$ as well, so we’ll denote the new $B$ by $B^\prime$ .

Note that every collection of $m$ disjoint paths from $A^\prime$ to $B^\prime$ can be ‘lifted’ to a collection of $m$ disjoint paths from $A$ to $B$ :

There is at most one path that goes through $v_{e}$ (since the path are vertex disjoint). This one can be ‘lifted’ to $G$ such that instead of it goes through $v_{e}$ , it wil now go from $x$ to $y$ through $e$ .
All the other paths can be ‘lifted’ with no change since they weren’t ‘affected’ by the contraction and they won’t go through $x$ or $y$ .

So if $G^\prime$ had $k$ vertex disjoint paths from $A^\prime$ to $B^\prime$ , we would have $k$ vertex disjoint paths from $A$ to $B$ .

However, we assumed that there aren’t $k$ vertex disjoint paths from $A$ to $B$ so there is no way there are $k$ vertex disjoint paths from $A^\prime$ to $B^\prime$ .

Recall that $G^\prime$ has one less edge than $G$ , and the induction is on the edges. Therefore we can apply the induction on $G^\prime$ and conclude that:

P_{\text{max}}(A^\prime B^\prime )\geq S_{\text{min}}(A^\prime B^\prime )

But we also know that $P_{\text{max}}(A^\prime B^\prime)< k$ . Therefore:

S_{\text{min}}(A^\prime B^\prime )< k

This means we can pick an $A^\prime B^\prime$ -separator with $k-1$ vertices (it may not be the minimal one, but it is a separator…). Let’s call it $Y$ .

The $A^\prime B^\prime$ -separator

This is the most important part of the proof: I state that $v_e$ must be in $Y$ . Why?

If $v_e$ wasn’t in $Y$ , then we could ‘lift’ $Y$ to $G$ and get that $Y$ is an $AB$ -separator in $G$ :

Pick a path from $A$ to $B$ . Now look at it in $G^\prime$ . This is a path from $A^\prime$ to $B^\prime$ . Therefore, there exists some $u\in Y$ that ‘breaks’ this path. By the assumption, $u\neq v_e$ , therefore, $u$ is a vetrex in $G$ that separates the path.

We can repeat this process for all the paths to get that $Y$ separates them all, and by doing so, it separtates $A$ and $B$ .

Ok, but how is that a problem exactly? what’s the problem with $Y$ being an $AB$ -separator?

The problem is that $|Y|< k-1$ . But $k$ is the minimal size of an $AB$ -separator in $G$ . And that’s clearly a contradiction – there is no way that we have found an $AB$ -separator with size smaller than the minimal size – $k$ .

Getting to the contradiction

Great, now that we know that $v_{e}$ must be in $Y$ , we can lift $Y$ back to $G$ by defining:

S=(Y\setminus\{v_e\})\cup\{x,y\}

Now, since $|Y|=k-1$ , we know that $|S|=k$ . and $S$ is a separator in $G$ (from the same argument I’ve already presented with slight changes, covince yourself that it is true). Now, we can remove $e$ and it won’t affect the fact that $S$ is a separator. So we are dealing with the graph:

G^{\prime\prime}=G\setminus\{e\}

Now, every set that separates $A$ and $S$ in $G^{\prime\prime}$ , separates them in $G$ as well. Moreover, such sets also separates $A$ from $B$ in $G$ (since $S$ separates $A$ and $B$ ). Hence, it has a size of at least $k$ – the minimal size of an $AB$ -separator.

However, $G^{\prime\prime}$ has one less edge than $G$ , so the induction applies on it. Therefore, there are $k$ disjoint paths from $A$ to $S$ . With a similar process, we find that there are $k$ disjoint paths from $S$ to $B$ .

Each path from $A$ to $S$ end in some point in $S$ , and since there are $k$ paths & elements in $S$ , we can conclude that every element in $S$ is an endpoint of a path from $A$ . The same thing applies to $B$ as well.

Thus, we can join two path toghether – a path from $A$ to $S$ and the path from $S$ to $B$ that starts exactly where the path from $A$ to $S$ ends.

By doing so, we can create $k$ disjoint paths from $A$ to $B$ . But we assumes that there aren’t $k$ disjoint paths from $A$ to $B$ so we’ve got a contradiction!

Hence, $P_{\text{max}}(AB)\geq S_{\text{min}}$ and this completes the proof.

Conclusions

Now that we’ve proved this theorem we deduce some great results!

First, if $a\neq b$ are two vertices in a graph such that there is no edge between them. Then the minimal number of vertices in $G\setminus\{a,b\}$ that separates $a$ and $b$ is the maximal number of disjoint paths from $a$ to $b$ .

Before I’ll prove it in one row, I just want to mention that when I mean that paths from $a$ to $b$ are disjoint, I mean that they have different vertices expect the endpoints – $a,b$ . Ok, now for the proof:

Using menger’s theorem, the sets:

N_G(a)=\{u\in V(G):\{u,a\}\in E\} \\ N_G(b)=\{u\in V(G):\{u,b\}\in E\}

Will do the job.

That’s it.

But I kind of want to explain it a little. By mengers theorem:

The maximal size of collection of disjoint paths from $N_G(a)$ to $N_G(b)$ is the same as the minimal size of an $N_G(a)N_G(b)$ -separator set.

Now paths from $a$ to $b$ must go through vertices in $N_G(a),N_G(b)$ . So the maximal size of collection of disjoint paths from $N_G(a)$ to $N_G(b)$ is in fact the maximal size of collection of disjoint paths from $a$ to $b$ .

Similarly, the minimal size of an $N_G(a)N_G(b)$ -separator set. is in fact the minimal number of vertices in $G\setminus\{a,b\}$ that separates $a$ and $b$ .

Ok, now that it’s clear, I want to present what I was really aiming for:

Criteria for being a $k$ -connected graph

$G$ is $k$ -connected $\iff$ every pair of vertices $a\neq b$ has $k$ vertex disjoint paths from $a$ to $b$ .

That’s a really nice criteria, since it allows us to translate the question of “is the graph $k$ -connected?” to the question : “How many paths can I find between two vertices?” and sometimes, one is easier to determine than the other.

Let’s prove it:

$\Leftarrow$

Suppose that every pair of vertices $a\neq b$ has $k$ vertex disjoint paths from $a$ to $b$ . Aiming for contradiction, I’ll assume that the graph is not $k$ -connected.

So there is a set $S$ of vertices such that $|S|\leq k-1$ and $G\setminus S$ is not connected. So let’s pick $u,v\in G\setminus S$ that are not on the same component.

But there are $k$ disjoint paths from $u$ to $v$ in $G$ and we’ve only removed $k-1$ vertices, thus there still exists a path between those two. And that’s a contradiction to them being on different components.

$\Rightarrow$

Suppose that $G$ is $k$ -connected and let $a,b\in V(G)$ be some vertices.

If $\{a,b\}\notin E$ then by the statement I just proved, there are $k$ vertex disjoint paths between them (the graph is $k$ connected, so we need at least $k$ vertices to separate $a$ and $b$ ).

If $\{a,b\}\in E$ , then we’ll consider the graph:

G^\prime=G\setminus\{a,b\}

Now if $G$ has at most $k-1$ vertex disjoint paths between $a$ and $b$ , then there are at most $k-2$ vertex disjoint paths between $a$ and $b$ (since we’ve removed one – the edge between them).

Now, by the statment I just proved, we can conclude that there exists a minimal set $X$ with at most $k-2$ vertices that separates $a$ and $b$ .

Since the graph is $k$ -connected there are at least $k+1$ vertices.

Note that in the set $X\cup\{a,b\}$ there are $k-2+2=k$ vertices. Therefore, there exists some $v\notin X\cup\{a,b\}$ .

$X$ must separate $v$ and $a$ or $v$ and $b$ . If it isn’t we would get a path from $a$ to $b$ (that goes through $v$ ).

WLOG Suppose that it separates $a$ and $v$ . Now consider the set $X\cup\{b\}$ . This set is of size $k-1$ and it separates $a$ and $v$ but that’s a contradiction to $G$ being $k$ -connected!

Summary

So we’ve seen menger’s theorem and a nice result of it. I want to mention that we can also conclude results on the edge-connectivity of the graph, similar to the connectivity. However, the process is similar, and really technical, so I decided to skip it. However, If you are still interested in those results, I reccomend you read about the Line Graph, and try to think how can you implement menger’s theroem to it.

Menger’s theorem

Contraction

Vertex separator

Vertex Disjoint paths

The theorem