Menger’s theorem

Proof. We’ve already seen a glimpse of the relationship between \(s-t\) cuts in \(G\) and vertex covers in \(H\), but it will be easier to prove it formally if we first understand the relationship between internally disjoint \(s-t\) paths in \(G\) and matchings in \(H\).

A matching \(M\) in \(H\), like the matching with \(E(M) = \{16, 25, 37\}\) we found in Figure 27.1(b), can always be turned into a set of internally disjoint \(s-t\) paths of the same size. For each edge \(xy \in E(M)\), take the path represented by \((s,x,y,t)\). The internal vertices of this path are precisely the endpoints of \(xy\), and by the definition of a matching, two edges in \(M\) share no endpoints. This means that the paths we get in this way are always internally disjoint.

Not all \(s-t\) paths are like this; in Figure 27.1(a), there are very long paths like the one represented by \((s,2,4,7,3,6,5,t)\). However, each \(s-t\) path must contain an edge \(xy\), where \(x\in A\) and \(y \in B\), or else it will never reach \(t\). Given a set of internally disjoint \(s-t\) paths, let \(M\) be the subgraph of \(H\) containing the first edge between \(A\) and \(B\) from each path. Because the paths were internally disjoint, these edges share no endpoints, so \(M\) is a matching.

This correspondence shows that the largest number of internally disjoint \(s-t\) paths in \(G\) is equal to the matching number \(\alpha'(H)\). For \(s-t\) cuts in \(G\) and vertex covers in \(H\), the relationship appears to be much more simple: they are one and the same! But why is this?

In both cases, we are looking for a set of vertices not including \(s\) or \(t\); a subset \(U \subseteq V(H)\). The definition of a vertex cover is simpler to check than the definition of an \(s-t\) cut: \(U\) is a vertex cover in \(H\) if and only if it contains an endpoint of every edge \(xy\) with \(x \in A\) and \(y \in B\). So let’s check that this also describes when \(U\) is an \(s-t\) cut in \(G\).

This proves that \(s-t\) cuts in \(G\) are exactly the same as vertex covers in \(H\); in particular, \(\kappa'_G(s,t) = \beta(H)\).

We’re now ready to prove the equivalence claimed in the lemma. We have two pairs of equal quantities, one in \(G\) and one in \(H\):

1. The largest size of a set of internally disjoint \(s-t\) paths in \(G\) is equal to the matching number \(\alpha'(H)\).

2. The \(s-t\) connectivity \(\kappa_G(s,t)\) is equal to the vertex cover number \(\beta(H)\).

Both Menger’s theorem for \(G\) and Kőnig’s theorem for \(H\) say that the first pair is also equal to the second pair, so the claims made by the two theorems are equivalent. ◻

Proof. Suppose for the sake of contradiction that \(G\) has such a vertex. Then \(x\) must be part of every \(s-t\) cut: if it is not deleted, there is an \(s-t\) path \(P\) represented by \((s,x,t)\). So every \(s-t\) cut has the form \(U \cup \{x\}\), where \(U\) is an \(s-t\) cut in \(G-x\).

Let \(H = G-x\). Because (as we’ve just proved) every \(s-t\) cut in \(G\) consists of an \(s-t\) cut in \(H\), plus one extra vertex, we have \(\kappa_G(s,t) = \kappa_H(s,t) + 1\).

But we know that \(H\) is smaller than the minimal counterexample to Menger’s theorem! So by Menger’s theorem, \(H\) contains a set of \(\kappa_H(s,t)\) internally disjoint \(s-t\) paths.

All these \(s-t\) paths are also \(s-t\) paths in \(G\), and we can add one more path to the set: the path \(P\) defined above. Therefore \(G\) contains a set of \(\kappa_H(s,t)+1\) internally disjoint \(s-t\) paths. But this is exactly the number of paths Menger’s theorem promises, so we contradict our assumption that \(G\) is a counterexample to Menger’s theorem. ◻

Proof. Let \(x\) be an arbitrary vertex of \(G\), and let \(H = G-x\). As in the previous lemma, \(H\) is smaller than the minimal counterexample to Menger’s theorem, so \(H\) contains a set of \(\kappa_H(s,t)\) internally disjoint \(s-t\) paths.

Therefore \(G\) also contains a set of \(\kappa_H(s,t)\) internally disjoint \(s-t\) paths. Since \(G\) is a counterexample to Menger’s theorem, these paths must not be enough: \(\kappa_G(s,t)\) must be bigger than \(\kappa_H(s,t)\). In other words, \(\kappa_G(s,t) \ge \kappa_H(s,t)+1\).

Let \(U\) be an \(s-t\) cut in \(H\) of size \(\kappa_H(s,t)\). Then \(U \cup \{x\}\) is an \(s-t\) cut in \(G\) of size \(\kappa_H(s,t)+1\), because \(G - (U \cup \{x\})\) is exactly the same graph as \(H - U\). This proves that \(\kappa_G(s,t) \le \kappa_H(s,t)+1\), and since we have the reverse inequality already, we know that \(\kappa_G(s,t)\) and \(\kappa_H(s,t)+1\) are equal.

Therefore \(U \cup \{x\}\) is the \(s-t\) cut containing \(x\) we wanted: it has size \(\kappa_H(s,t)+1 = \kappa_G(s,t)\). ◻

Proof. Let \(U\) be an \(s-t\) cut in \(G\) with \(|U| = \kappa_G(s,t)\). If \(U\) contains all of \(A\), then \(U\) must be equal to \(A\), because otherwise \(A\) would be a smaller \(s-t\) cut. Similarly, if \(U\) contains all of \(B\), then \(U\) must be equal to \(B\). So assume, for the sake of contradiction, that \(U\) does not contain all of either set: there is some \(x \in A\) and some \(y \in B\) such that \(U\) does not contain either \(x\) or \(y\).

The vertices \(x\) and \(y\) will be important eventually, but for the moment, we simply use \(U\) to split up the problem of finding internally disjoint \(s-t\) paths in \(G\) into two smaller subproblems. This is shown by example in Figure 27.2, which is worth a thousand words. Here are a few words to describe what we do in general:

Subproblem 1. Take the subgraph of \(G\) induced by \(U\) and all the vertices in the same connected component of \(G-U\) as \(s\). This does not include \(t\), because in \(G-U\), vertices \(s\) and \(t\) are in different components. But now, add \(t\) back in, with edges from every vertex in \(U\) directly to \(t\). Call the resulting graph \(L\) (for “left”, since in our example, it retains the left half of Figure 27.3).

Subproblem 2. Take the subgraph of \(G\) induced by \(U\) and all the vertices in a different connected component of \(G-U\) from \(s\). (This includes \(t\), but not \(s\).) Add \(s\) back in, with edges from \(s\) directly to every vertex in \(U\). Call the resulting graph \(R\) (for “right”).

The vertices \(x\) (in \(A\), but not in \(U\)) and \(y\) (in \(B\), but not in \(U\)) guarantee that the two subproblems are strictly smaller than \(G\): in \(L\), there is no vertex \(y\), and in \(R\), there is no vertex \(x\). As in Lemma 27.3, the natural next step is to apply Menger’s theorem to \(L\) and \(R\). To do this, the first thing we need to know is \(\kappa_{L}(s,t)\) and \(\kappa_{R}(s,t)\).

This is true in general. To find an \(s-t\) cut in \(L\), we must block all ways to get from \(s\) to \(U\) (since every vertex to \(U\) is adjacent to \(t\)). This also blocks all ways to get from \(s\) to \(U\) in \(G\) (since before we pass through \(U\), we cannot reach a place where \(G\) and \(L\) disagree), so we get an \(s-t\) cut in \(G\) as well, proving \(\kappa_L(s,t) \ge \kappa_G(s,t)\). Similarly, \(\kappa_R(s,t) \ge \kappa_G(s,t)\), because an \(s-t\) cut in \(R\) blocks all ways to get from \(U\) to \(t\), which makes it an \(s-t\) cut in \(G\) as well.

The reverse inequalities \(\kappa_L(s,t) \le \kappa_G(s,t)\) and \(\kappa_R(s,t) \le \kappa_G(s,t)\) hold because \(U\) is a cut of size \(\kappa_G(s,t)\) in all three graphs: \(G\), \(L\), and \(R\).

Because \(L\) is strictly smaller than \(G\), Menger’s theorem holds for \(L\), giving a set of \(\kappa_G(s,t)\) internally disjoint \(s-t\) paths in \(L\). Since \(|U| = \kappa_G(s,t)\) and every \(s-t\) path in \(L\) must first pass through \(U\), this set of paths uses each vertex in \(U\) exactly once. By removing the last step from each path, we get a set of internally disjoint paths from \(s\) to every vertex of \(U\).

Because \(R\) is strictly smaller than \(G\), Menger’s theorem holds for \(R\), giving a set of \(\kappa_G(s,t)\) internally disjoint \(s-t\) paths in \(R\). Since \(|U| = \kappa_G(s,t)\) and every \(s-t\) path in \(R\) must first pass through \(U\), this set of paths uses each vertex in \(U\) exactly once. By removing the first step from each path, we get a set of internally disjoint paths from every vertex of \(U\) to \(t\).

For each vertex \(u \in U\), the union of an \(s-u\) path from the first set and a \(u-t\) path from the second set is an \(s-t\) path in \(G\). (This is shown for our example in Figure 27.3.) All \(\kappa_G(s,t)\) paths obtained in this way are internally disjoint: they cannot intersect in or before \(U\), because that would be an intersection in \(L\), and they cannot intersect after \(U\), because that would be an intersection in \(R\).

But finding a set of \(\kappa_G(s,t)\) internally disjoint \(s-t\) paths in \(G\) contradicts our choice of \(G\): that it was a minimal counterexample to Menger’s theorem. Therefore the \(s-t\) cut \(U\), which we assumed to exist at the beginning of this proof, cannot exist in \(G\). ◻

Proof of Menger’s theorem (Theorem 27.1). Suppose for the sake of contradiction that a minimal counterexample to Menger’s theorem exists: a graph \(G\) with designated not-adjacent vertices \(s\) and \(t\) which does not have a set of \(\kappa_G(s,t)\) internally disjoint \(s-t\) paths.

By Lemma 27.2 and Kőnig’s theorem, we know that \(G\) (a counterexample to Menger’s theorem) cannot be a Kőnig-type graph.

Let \(x\) be one such vertex. If \(x\) is adjacent to both \(s\) and \(t\), this contradicts Lemma 27.3. If \(x\) is adjacent to neither \(s\) nor \(t\), then we need to work harder. First, apply Lemma 27.4 to find a vertex cut \(U\) of size \(\kappa_G(s,t)\) with \(x \in U\).

In all case, \(G\) contradicts one of the lemmas we proved, so we conclude that a counterexample to Menger’s theorem does not exist. ◻

Proof of Theorem 27.6. Define a new graph \(H\) in one of the following two equivalent ways:

• Construct \(G'\) from \(G\) by adding two new vertices: one adjacent only to \(s\) and one adjacent only to \(t\). Then, let \(H = L(G)\).

• Construct \(H\) from \(L(G)\) by adding two new vertices \(s^*\) to \(t^*\). For every vertex of \(L(G)\) which represents an edge incident to \(s\), make it adjacent to \(s^*\) in \(H\); for every vertex of \(L(G)\) which represents an edge incident to \(T\), make it adjacent to \(t^*\) in \(H\).

We must resolve an issue that will otherwise repeatedly bother us throughout this proof: the relationship between \(s^* - t^*\) paths in \(H\) and \(s-t\) paths in \(G\). In one direction, things work out nicely. Given a walk \((x_0, x_1, \dots, x_l)\) in \(G\) where \(x_0 = s\) and \(x_1 = t\), the sequence \((s^*, x_0x_1, x_1x_2, \dots, x_{\ell-1}x_\ell, t^*)\) is an \(s^* - t^*\) walk in \(H\), and if the first walk represents a path, so does the second. (Check this!)

However, given an \(s^* - t^*\) path in \(H\), we can look at the subgraph of \(G\) containing all the edges that were internal vertices of the \(s^* - t^*\) path, and all their endpoints. This is a connected subgraph of \(G\) containing \(s\) and \(t\), so within it we can find an \(s-t\) path.

By applying Menger’s theorem to \(H\), we get a set of \(\kappa_H(s^*, t^*)\) internally disjoint \(s^* - t^*\) paths. We know how to turn each of them into an \(s-t\) path in \(G\), but we want to know that we’ll get a set of edge-disjoint paths when we do so.

We’ve found a set of \(\kappa_H(s^*, t^*)\) edge-disjoint \(s-t\) paths in \(G\), but that’s not enough. We need \(\kappa'_G(s,t)\) edge-disjoint \(s-t\) paths, so we must show that we have at least as many as we need: that \(\kappa_H(s^*, t^*) \ge \kappa'_G(s,t)\). (The two should be equal, but proving that is more than we need.)

In other words, we need to show that every \(s^*-t^*\) cut \(U\) in \(H\) is an \(s-t\) edge cut in \(G\). By definition of an \(s^* - t^*\) cut, every \(s^* - t^*\) path in \(H\) passes through some element of \(U\). We’ve already seen that every \(s-t\) path in \(G\) corresponds to an \(s^* - t^*\) path in \(H\): so every \(s-t\) path in \(G\) uses an edge of \(U\). That’s exactly what it means for \(U\) to be an \(s-t\) edge cut!

Therefore applying Menger’s theorem to \(H\) and turning the paths we get back into paths in \(G\), we get a set of at least \(\kappa'_G(s,t)\) edge-disjoint \(s-t\) paths in \(G\), proving the theorem. ◻

Proof. First, let’s deal with the case \(|T| \ge k\), in which case we want to find an \(s-T\) fan of size \(k\). Define a new graph \(H\) from \(G\) by adding a new vertex \(t\) adjacent to every element of \(T\).

First, we prove that \(\kappa_H(s,t) \ge k\). Suppose not: suppose that \(U\) is an \(s-t\) cut in \(H\) with \(|U| \le k-1\). Then \(|U| < |T|\), so in \(H-U\), there must be at least some vertices of \(T\) left, which are in the same connected component as \(T\), and therefore in a different connected component from \(s\). This means that in \(G-U\), those vertices of \(T\) are still in a different component from \(s\), which makes \(U\) a vertex cut in \(G\). But this contradicts our assumption that \(G\) is \(k\)-connected.

By applying Menger’s theorem to \(H\), we obtain a set of at least \(k\) internally disjoint \(s-t\) paths in \(H\). By removing vertex \(t\) from \(k\) of these paths, what we get is exactly an \(s-T\) fan in \(G\) of size \(k\).

If \(|T| < k\), then we first replace \(T\) by a set \(T'\) containing \(T\) of size exactly \(k\). (A \(k\)-connected graph must have at least \(k+1\) vertices, so this is always possible.) If we find an \(s-T'\) fan in \(G\) of size \(k\), then it contains a path from \(s\) to every vertex of \(T'\); in particular, to every vertex of \(T\). By taking only the paths that go to \(T\), we get an \(s-T\) fan of size \(|T|\). ◻

Proof. If \(\alpha(G)=1\), then \(G\) can’t be missing even a single edge between its vertices, in which case it’s definitely Hamiltonian; so we will assume \(\alpha(G) \ge 2\) and \(\kappa(G) \ge 2\). It’s a good sign that \(G\) is \(2\)-connected; this means that at least it has some cycles, by any of the results in Chapter 25. This proof will proceed by finding longer and longer cycles, until finally getting a Hamilton cycle.

Let \(C\) be the longest cycle we’ve found so far. If we’re not done with the proof yet, we assume that it is not a Hamilton cycle: there is some vertex \(y \notin V(C)\). Our goal will be to find a longer cycle in \(G\), and to make sure it’s longer, we will find a cycle that passes through every vertex in \(V(C)\) and also passes through \(y\).

Take a \(y-V(C)\) fan in \(G\) with as many paths in it as possible; by Dirac’s fan lemma, it has size at least \(\min\{|C|, \kappa(G)\}\), but if we’re lucky, it might be larger. An example is shown in Figure 27.4(a) (with \(y\) in the center). The definition of a fan does not guarantee that the paths it contains do not share any internal vertices with \(C\), though I’ve drawn the fan in this way. However, we can assume that this is true anyway, by stopping every path in the fan as soon as it reaches a vertex of \(C\).

Let \((x_0, x_1, \dots, x_{l-1}, x_0)\) be a walk representing \(C\). Choosing this walk representation also gives us a direction to follow along \(C\). If all we have is the cycle, all we can say is that every vertex on the cycle has two neighbors. With the walk, we can say that every vertex \(x_i \in V(C)\) has a vertex \(x_{i+1}\) that comes after it (taking \(x_l = x_0\)) and a vertex \(x_{i-1}\) that comes before it (taking \(x_{-1} = x_{l-1}\)).

This is important, because I want to define a set of vertices in an usual way. First, let \(I \subseteq \{0,1,\dots,l-1\}\) be the set of positions in the cycle where some path in the \(y-V(C)\) fan ends: that is, the fan contains a \(y - x_i\) path whenever \(i \in I\), and not otherwise. Now, instead of looking at the vertices in the fan, look at the vertices immediately following them on the path: the set \(\{x_{i+1} : i \in I\}\). These are marked in Figure 27.4(b).

Looking at this set of vertices appears unmotivated at first, but it’s a common trick in results about Hamilton cycles, so I want to explain it a bit. We will soon be trying to find a cycle that mostly consists of the edges shown in Figure 27.4(a); although \(G\) has many other edges not shown in the diagram, we don’t know much about those edges. In this figure, each vertex \(x_i\) with \(i \in I\) has degree \(3\), so a cycle through them will use two of their neighbors and neglect the third. Sometimes, \(x_{i-1}\) or \(x_{i+1}\) might be that neglected neighbor, and so we look at it more closely to find some other edge it might have!

In fact, to get a cycle through \(y\) and every vertex of \(C\), it’s enough to find a single edge \(x_{i+1} x_{j+1}\) where \(i,j \in I\). An example of such a cycle is shown in Figure 27.4(c). More formally, the cycle is obtained as follows:

1. By deleting edges \(x_i x_{i+1}\) and \(x_j x_{j+1}\) from \(C\), we break it into two pieces: an \(x_{i+1} - x_j\) path \(P\) and an \(x_i - x_{j+1}\) path \(Q\). Together, \(V(P) \cup V(Q) = V(C)\).

2. By combining the \(y-x_i\) and \(y-x_j\) paths in the fan, we get an \(x_i - x_j\) path \(R\) that passes through \(y\) and shares none of its internal vertices with \(P\) or \(Q\).

3. The union \(P \cup Q \cup R\) combines an \(x_{i+1} - x_j\) path, an \(x_j - x_i\) path, and an \(x_i - x_{j+1}\) path; these paths share no vertices apart from \(x_i\) and \(x_j\). Therefore \(P \cup Q \cup R\) is an \(x_{i+1} - x_{j+1}\) path. Adding the edge \(x_{j+1}x_{i+1}\) gives us the cycle we wanted!

We’ve almost finished the proof, except for one detail: how do we guarantee that an edge \(x_{i+1}x_{j+1}\) exists? I have to wonder if Chvátal and Erdős came up with the proof up until now, and only then asked themselves this question, and that’s how they came up with the hypotheses of this theorem. After all, we’ve barely used the assumption about the independence number of \(G\), so far!

There are two cases. If \(|V(C)| \le \kappa(G)\), then Dirac’s fan lemma guarantees a fan of size \(|V(C)|\), which includes a path to every vertex of \(C\). Therefore every edge of the cycle is an edge of the type we’re looking for! For example, the edge \(x_1x_2\) will work, for \(i=0\) and \(j=1\), because our fan includes an \(y-x_0\) path and a \(y-x_1\) path.

If \(|C| > \kappa(G)\), then Dirac’s fan lemma only guarantees a fan of size \(\kappa(G)\). At this point, we remember that \(\kappa(G) \ge \alpha(G)\). If only we had \(\kappa(G) > \alpha(G)\), instead! Then we’d know that the set \(\{x_{i+1} : i \in I\}\) cannot be independent, because it has size \(\kappa(G)\): it’s bigger than the largest independent set.

But a theorem with \(\kappa(G) > \alpha(G)\) as a hypothesis would not be the best theorem Chvátal and Erdős could prove. We can still finish the proof with the hypothesis \(\kappa(G) \ge \alpha(G)\). For this, consider the set \(\{x_{i+1} : i \in I\} \cup \{y\}\), which has at least \(\kappa(G)+1\) vertices, and therefore isn’t independent. We either get an edge \(x_{i+1}x_{j+1}\) with \(i,j \in I\), which is what we wanted, or an edge \(x_{i+1}y\) with \(i \in I\), which… isn’t what we wanted.

To sum it up: we started with an arbitrary cycle which was not a Hamilton cycle, and were able to make it longer, by incorporating at least one additional vertex. We can repeat this to grow the new cycle, too, as many times as necessary. The only way this process can end is by finding us a Hamilton cycle, proving that \(G\) is Hamiltonian. ◻