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 is a graph and is an edge in it. Intuitively, the **contraction** along is the new graph that you get when you ‘squish’ the edge 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 The vertices that are not the endpoints of will still be on this graph. The endpoint of on the other hand, are now considered as one. We will think of them as they removed and induced a new vertex – .

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

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

So Now, what about the edges?

Well, if and neither of it’s endpoints are or , then will also be in . 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 or . But they are exactly the edges that have one endpoint in the **new** vertex – . 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 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 are sets of vertices in a graph . We say that a set is an **-separator** if in there are no paths between vertices in to vertices in .

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, and .

For example, Here:

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

Moreover, if and 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 be a graph. Suppose that are sets of vertices of . Then, the **maximal** size of collection of disjoint paths from to is the same as the **minimal** size of an -separator set.

If we denote the maximal size disjoint paths from to as and the minimal size of an -separator set as 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 and then I’ll prove that . Let’s do it:

#### Part 1 –

Let’s denote . And now, let be vertex disjoint paths from to .

Now, Suppose that is some arbitrary -separator. Since after removing , there are no paths from to , **at least one** vertex has been removed from each of the paths . 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 . Hence, contains at least vertices and we can now conclude:

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

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

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

As we wanted.

#### Part 2 –

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

**Base case**

If is empty then the the only paths we have between are the path with zero-length from a vertex to itself. And how many are there? exactly . However, this is also the number of the minimal separator set. So not only is smaller than, 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 vertex disjoint paths from to . The trick here is to look at a **contraction** of the graph and apply the induction on it. So let’s pick some edge and denote the contraction by .

Now, what happened to the sets and ?

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

The same arguments apply to as well, so we’ll denote the new by .

Note that every collection of disjoint paths from to can be ‘lifted’ to a collection of disjoint paths from to :

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

So if had vertex disjoint paths from to , we would have vertex disjoint paths from to .

However, we assumed that there aren’t vertex disjoint paths from to so there is no way there are vertex disjoint paths from to .

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

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

But we also know that . Therefore:

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

This means we can pick an -separator with vertices (it may not be the minimal one, but it is a separator…). Let’s call it .

**The -separator**

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

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

Pick a path from to . Now look at it in . This is a path from to . Therefore, there exists some that ‘breaks’ this path. By the assumption, , therefore, is a vetrex in that separates the path.

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

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

The problem is that . But is the minimal size of an -separator in . And that’s clearly a contradiction – there is no way that we have found an -separator with size smaller than the minimal size – .

**Getting to the contradiction**

Great, now that we know that must be in , we can lift back to by defining:

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

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

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

Now, every set that separates and in , separates them in as well. Moreover, such sets also separates from in (since separates and ). Hence, it has a size of at least – the minimal size of an -separator.

However, has one less edge than , so the induction applies on it. Therefore, there are disjoint paths from to . With a similar process, we find that there are disjoint paths from to .

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

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

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

Hence, and this completes the proof.

## Conclusions

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

First, if are two vertices in a graph such that there is no edge between them. Then the minimal number of vertices in that separates and is the maximal number of disjoint paths from to .

Before I’ll prove it in one row, I just want to mention that when I mean that paths from to are disjoint, I mean that they have different vertices expect the endpoints – . 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 to is the same as the **minimal** size of an -separator set.

Now paths from to must go through vertices in . So the **maximal** size of collection of disjoint paths from to is in fact the maximal size of collection of disjoint paths from to .

Similarly, the **minimal** size of an -separator set. is in fact the minimal number of vertices in that separates and .

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

## Criteria for being a -connected graph

is -connected every pair of vertices has vertex disjoint paths from to .

That’s a really nice criteria, since it allows us to translate the question of “is the graph -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:

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

So there is a set of vertices such that and is not connected. So let’s pick that are not on the same component.

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

Suppose that is -connected and let be some vertices.

If then by the statement I just proved, there are vertex disjoint paths between them (the graph is connected, so we need at least vertices to separate and ).

If , then we’ll consider the graph:

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

Now if has at most vertex disjoint paths between and , then there are at most vertex disjoint paths between and (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 with at most vertices that separates and .

Since the graph is -connected there are at least vertices.

Note that in the set there are vertices. Therefore, there exists some .

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

WLOG Suppose that it separates and . Now consider the set . This set is of size and it separates and but that’s a contradiction to being -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.