Part II · The Classic Theory

Connectivity

Created by Felipe Casadei

A network survives any two node failures exactly when every pair of its nodes has three routes that never collide. After this chapter you will know why those two statements are the same statement, and you will be able to build every 2-connected and 3-connected graph from scratch.

Why connectivity deserves a chapter

Chapter 1 defined \(k\)-connected by what you cannot do to a graph. A graph is \(k\)-connected if it has more than \(k\) vertices and stays in one piece however you delete fewer than \(k\) of them. That is a negative description: it lists a kind of damage the graph resists. It says nothing about what the graph offers you while it is intact.

Here is the positive description. Suppose every two vertices of your network are joined by \(k\) routes sharing nothing except their two endpoints. Any \(k-1\) failures spoil at most \(k-1\) of those routes, so one always survives and the network stays connected. Route redundancy implies damage resistance in two lines.

The surprise is that the implication runs the other way too. If no set of \(k-1\) vertices can break your network apart, then the \(k\) non-colliding routes really are there, between every pair. Nothing in the definition of \(k\)-connectedness mentions paths, and yet the paths exist. That equivalence is Menger's theorem of 1927, and it is why "connectivity" names a useful quantity rather than a bookkeeping convention.

The practical reading is immediate. "How much punishment can this network take?" is a question about deletions, awkward to check because there are astronomically many vertex sets to try. "How many independent routes join these two nodes?" is a question about construction, which an algorithm answers by building routes one at a time. Menger's theorem says the two questions have the same numerical answer, so compute whichever side is convenient and certify the other.

The chapter has four more jobs beyond Menger. It gives build recipes: every 2-connected graph is a cycle with paths glued on one at a time, and every 3-connected graph grows out of \(K^4\), the complete graph on four vertices, by simple local moves. It decomposes merely connected graphs into blocks, the largest chunks with no internal single point of failure, which hang together in a tree. It counts paths that begin and end on one chosen set. And it asks the hardest routing question here: can you insist that path number one join this specific pair? Graphs where you always can are called \(k\)-linked, and they are strictly rarer than \(k\)-connected graphs.

New notation in this chapter

Thirteen symbols are new here; the rest are recalled from Chapter 1 and re-explained the first time they appear. If set language such as \(X \subseteq V(G)\) ("X is a subset of the vertices of G") is still unfamiliar, Chapter 0 is the bootstrap.

Building every 2-connected graph out of ears

Start at the bottom of the scale. What does a 2-connected graph look like? The definition says only that it has at least three vertices and no cutvertex, meaning no single vertex whose deletion splits the graph. That is a prohibition, and prohibitions are hard to work with. We want a recipe.

The recipe uses one move. Take a graph \(H\) you have already built and glue on an \(H\)-path: a path whose two end vertices lie in \(H\) and whose interior lies entirely outside \(H\). Such a path is called an ear, attached to a head at two points. An ear may be long, or a single new edge between two vertices of \(H\) with no interior at all.

Proof idea. Gluing an ear never creates a cutvertex, since the survivors of any deletion stay tied together through the old graph, which had none either. So everything built this way is 2-connected. Conversely, in a 2-connected \(G\) let \(H\) be the largest subgraph the recipe can build. Any edge of \(G\) between two vertices of \(H\) is itself a legal ear, so \(H\) contains those; and if \(H\) missed a vertex, 2-connectedness would supply a path from it back into \(H\), another legal ear. Either way \(H\) was not maximal. Diestel §3.1 has the details.^[1]

The recipe pays off at once. Any statement about all 2-connected graphs can be proved by induction along the construction: check it for a cycle, then check that gluing an ear preserves it. One example: in a 2-connected graph any two vertices lie on a common cycle, which is the case \(k=2\) of Menger's theorem obtained without Menger's theorem.

Blocks: the pieces a connected graph falls into

Most real networks are not 2-connected. They have weak joints. The right response is not to give up but to chop the graph at its weak joints and study the pieces, which are 2-connected or trivially small. Those pieces are called blocks.

Why "no cutvertex" rather than the cleaner-sounding "2-connected"? Because a decomposition should cover everything. Bridges and isolated vertices are not 2-connected, and excluding them would leave parts of the graph in no block at all. The chosen wording lets them in, so every edge of \(G\) lies in exactly one block.

One piece of fine print trips up nearly everyone: a block may contain a cutvertex of the whole graph. The condition is only that it has no cutvertex of its own, judged inside the block. In Figure 3.2 the triangle \(abc\) is a block and \(c\) is a cutvertex of the whole graph, yet deleting \(c\) from the triangle leaves the connected edge \(ab\).

Three facts organise the picture, all proved in Diestel §3.1.^[1] The first says the decomposition loses nothing about cycles or minimal cuts. Recall from Chapter 1 that a cut is the set of edges between the two sides of a vertex partition, and a bond is a minimal such set.

Proof idea. A cycle is connected and has no cutvertex, so it enters the "maximal connected without cutvertex" competition and sits inside whichever block wins. For bonds, two vertices joined by an edge of a block \(B\) cannot be connected through anything but \(B\), since a path leaving and returning would build a bigger cutvertex-free subgraph. So a cut made inside \(B\) already separates them in all of \(G\).

Proof idea. Inside one block the ear construction produces a cycle through any two edges. Given such a cycle, deleting \(e\) and \(f\) splits it into two arcs; grow each arc into one side of a vertex partition, and the crossing edges form a bond containing both. A common bond forces a common block by the previous lemma. The value of this is that it identifies blocks without mentioning maximality: two edges share a block precisely when some loop runs through both.

Proof idea. A cycle in the block graph would tie several blocks together into one connected subgraph with no cutvertex of its own, bigger than any block it was made from, contradicting maximality. So the block graph has no cycles; since \(G\) is connected it is connected too, hence a tree.

The structure of 3-connected graphs

One level up, the same question returns. What does a 3-connected graph look like? Again we want a recipe rather than a prohibition, and again there is one, in fact two. Both start from the same seed.

Now the reduction move. Deleting an edge from a 3-connected graph usually ruins 3-connectedness for a silly reason: it can leave a vertex of degree 2, and a vertex of degree 2 is always killed by deleting its two neighbours. The repair is to smooth such a vertex away.

Two lemmas bracket the operation. The first says the move is safe to undo, the second says the move is always available.

Proof idea. Suppose \(G\) had a separator of two vertices. Push it down into \(G \mathbin{\dot{-}} e\), replacing any suppressed vertex by the edge it used to subdivide; the two sides of the split survive the translation. That gives a two-vertex separator in a graph that has none.

Proof idea. Among the subgraphs of \(G\) that are subdivisions of a 3-connected graph, and \(G\) contains a subdivided \(K^4\) so there is one, pick the one with most edges. If it is not all of \(G\), 3-connectedness supplies an \(H\)-path joining two different subdivided edges, and adding it yields a subdivision of a larger 3-connected graph, contradicting the choice.^[2]

Put the two lemmas together and you get a complete generative description.

Read the sequence forwards and it is a growth rule: each step adds one edge whose ends may be existing vertices, or new vertices planted in the middle of existing edges, or one of each. Every 3-connected graph is reachable from \(K^4\), and Lemma 3.2.1 guarantees that no wrong turn leaves the 3-connected world. Figure 3.5 runs one step backwards.

The second recipe uses contraction rather than deletion. Recall \(G/e\) from Chapter 1: merge the two ends of \(e\) into one vertex that inherits all their other neighbours.

Proof idea, by infinite descent. If no edge works then for every edge \(xy\) the graph \(G/xy\) has a two-vertex separator including the merged vertex, so \(G\) has a three-vertex separator \(\{x, y, z\}\). Among all such triples pick one whose leftovers include a smallest component \(C\); contracting an edge from \(z\) into \(C\) and repeating the reasoning yields a strictly smaller component. Components cannot shrink forever.

Forwards, the move is vertex splitting: pick a vertex, split it into two adjacent vertices, and share out its old neighbours so that each new vertex keeps at least two. The degree condition stops you splitting off a vertex of degree 2, which would destroy 3-connectedness for the silly reason met earlier. This is the core of what Tutte called the wheel theorem, and vertex splitting is the standard way to induct over all 3-connected graphs. Chapter 4 reuses Lemma 3.2.4 inside the proof of Kuratowski's planarity theorem.

The section ends with a result of a different flavour, algebraic rather than constructive. Recall the cycle space \(\mathcal{C}(G)\) from Chapter 1: the collection of edge sets that split into disjoint cycles, where adding two sets means keeping the edges that lie in exactly one of them, so shared edges cancel.

Proof idea. Among the cycles that are not such sums, pick one, \(C\), whose largest leftover component is as large as possible. If \(C\) covers every vertex, split it across a chord into two shorter cycles, both leaving strictly larger leftovers and so both good. Otherwise a well-chosen path across \(C\) writes it as a sum of two or three cycles, again with strictly larger leftovers. Either way the extremal choice is contradicted.

The payoff is geometric. In a 3-connected planar graph the non-separating induced cycles are exactly the boundaries of the faces you see when you draw it, so Tutte's theorem supplies a combinatorial stand-in for "face" with no drawing involved. That is the engine of Tutte's planarity criterion in Chapter 4. The paper it came from is titled "How to draw a graph", and its spring-embedding idea is the ancestor of the force-directed layouts that visualisation tools still run.^[2]

Menger's theorem

This is the result the chapter is built around. Before stating it, three words have to be separated, because confusing them wrecks nearly every statement that follows.

Now fix two vertex sets \(A\) and \(B\) inside a graph \(G\). They may overlap, and either may be a single vertex or the whole graph. An \(A\)–\(B\) path starts on one shore, ends on the other, and touches neither shore in between.

One direction of the theorem is free, and worth extracting because it is the part people mistake for the whole result. Suppose you have \(m\) pairwise disjoint \(A\)–\(B\) paths. Every separator must contain at least one vertex of each of them, and since the paths share no vertices, that is \(m\) distinct guards. So the number of disjoint paths never exceeds the number of guards:

\[ \max(\text{disjoint } A\text{--}B \text{ paths}) \;\le\; k(G, A, B). \]

Menger's theorem is the statement that this inequality is never strict.

Diestel gives three complete proofs, which is unusual and deliberate: each one generalises in a different direction.^[3] Here are their ideas in plain terms.

Proof one, by contraction. Induct on the number of edges. Pick an edge \(e = xy\) and squash it, forming \(G/e\). If the squashed graph still needs \(k\) guards, induction hands you \(k\) disjoint paths there, and unsquashing turns them into \(k\) disjoint paths of \(G\). Otherwise the squashed graph has a cheap separator, and pulling it back gives a separator \(X\) of \(G\) containing both \(x\) and \(y\), with exactly \(k\) vertices. Apply induction twice inside \(G - e\): once between \(A\) and \(X\), once between \(X\) and \(B\). Splice the two families at \(X\) and you have \(k\) disjoint \(A\)–\(B\) paths. This is Halin's argument, and its style, cut the graph at a bottleneck and recurse on both sides, recurs throughout the book.

Proof two, by augmentation. Prove something stronger: any system \(\mathcal{P}\) of fewer than \(k\) disjoint paths can be exceeded. To exceed \(\mathcal{P}\) means to find another disjoint system \(\mathcal{Q}\) that uses strictly more of \(A\) as starting points and strictly more of \(B\) as ending points, so in particular \(|\mathcal{Q}| \ge |\mathcal{P}| + 1\). The extra demand on both shores is what makes the induction close: merely having one more path is too weak a target to recurse on. The construction follows a fresh \(A\)–\(B\) path until it first collides with the old system, then reruns the argument on a graph whose far shore has been enlarged to include the collision zone, and reassembles the pieces. This is due to Böhme, Göring and Harant.

Proof three, by alternating walks. This one is modelled on the augmenting-path proof of König's theorem in Chapter 2, and it is the version that survives into infinite graphs. Fix a system \(\mathcal{P}\) of disjoint \(A\)–\(B\) paths. An alternating walk starts at an unused vertex of \(A\) and moves forward through free territory, but whenever it steps onto an edge already used by \(\mathcal{P}\) it must travel that edge backwards, toward \(A\). It may repeat a vertex only if the vertex lies on the path system, and each time it touches a path of \(\mathcal{P}\) it must arrive or leave along that path. Two lemmas then split the world in half.

Proof idea. In the first case, overlay the walk on the path system and keep the edges used by exactly one of them. Counting edges at each vertex shows the overlay falls apart into \(A\)–\(B\) paths, one more than before: riding backwards is exactly what lets the walk cancel a badly chosen stretch and re-route around it. In the second case, take on each path the last vertex alternating walks can still reach and collect those into a set \(X\). A path dodging all of \(X\) would let a walk reach further, contradicting the choice. So \(X\) is a separator with one guard per path, forcing \(k(G,A,B) \le |\mathcal{P}|\), which with the free inequality closes the theorem.

What Menger's theorem gives you

The set-to-set version is the general one, and the useful special cases follow from it by small tricks. Each trick is worth learning on its own, because the same tricks reappear whenever an edge problem or a single-vertex problem needs to be turned into a vertex-set problem.

Proof idea, one line: delete \(a\) and apply Menger's theorem in \(G - a\) with the left shore taken to be \(N(a)\), the vertices joined to \(a\) by an edge. Every route out of \(a\) starts at one of them, so disjoint \(N(a)\)–\(B\) paths reattach to \(a\) as fan ribs.

Next, the version people usually quote, between two named vertices.

Proof idea for (i): delete \(a\) and \(b\), then apply Menger's theorem with \(A := N(a)\) and \(B := N(b)\). For (ii): move to the line graph \(L(G)\) from Chapter 1, whose vertices are the edges of \(G\), two of them joined when they share an end. There, edge-disjoint paths of \(G\) become disjoint paths and edge cuts become vertex separators, so the vertex theorem applies and translates back. Turning an edge problem into a vertex problem this way is a reusable pattern.

Finally, the payoff promised at the start of the chapter. This is the version that converts the negative definition of \(k\)-connectedness into a positive one.

Proof idea. One direction is the two-line argument from the chapter opening: \(k\) independent routes cannot all be destroyed by \(k-1\) deletions. Conversely, suppose \(G\) is \(k\)-connected but some pair \(a, b\) has fewer than \(k\) independent paths. By Corollary 3.3.5 (i) that forces \(ab\) to be an edge, so delete it: the pair is now non-adjacent, giving a separator \(X\) of at most \(k-2\) vertices in \(G - ab\). Since \(G\) has more than \(k\) vertices, some vertex lies outside \(X \cup \{a,b\}\), and \(X\) plus whichever of \(a, b\) is on the far side separates \(G\) using at most \(k-1\) vertices, contradicting \(k\)-connectedness. That adjacent case is the fiddly part, and skipping it is a common gap.

Counting round trips: A-paths and Mader's theorem

Menger's theorem counts paths that run between two shores. A different question counts paths that start and end on the same chosen set and go abroad in between. Think of \(A\) as a set of terminals and ask how many non-colliding round trips through the surrounding network you can run at once.

The first result is a packing-versus-covering statement of exactly the kind Chapter 2 trained you to expect: either the thing you want exists in quantity, or a small blocker exists.

Notice the loss. In Menger's theorem the two numbers match exactly. Here, failing to pack \(k\) paths only buys you a blocker of size \(2k-2\) rather than \(k-1\), and the factor of roughly two is not slack in the proof. It is real, and the smallest complete graphs show why.

The general sharpness example is \(K^{2k-1}\) with \(A\) all of its vertices. Disjoint \(A\)-paths are then disjoint edges, and \(2k-1\) vertices cannot host \(k\) of those, so packing maxes out at \(k-1\). Blocking every edge takes \(2k-2\) guards, since two unguarded vertices leave the edge between them free. Both halves of Gallai's statement are tight at once.

Gallai's theorem is an inequality. The exact answer was found seventeen years later by Mader, and getting it exact required changing what counts as a blockade.

Why the strange scoring? A cluster of cut edges is worth less than the number of edges in it. Any \(H\)-path crossing the cluster \(C\) enters and leaves through different boundary vertices, and independent paths cannot reuse one, so the cluster is crossed at most \(\lfloor \frac{1}{2}|\partial C|\rfloor\) times. That makes the score a valid upper bound; counting \(|X| + |F|\) would also be valid but wasteful.

Diestel states this theorem without proving it. The book explains why \(M_H(G)\) is an upper bound, the part you can check by hand, then points to Schrijver's proof for the equality.^[4] This course follows the book: take the equality on trust, and spend your effort on why the refined score is the right thing to minimise. The result swallows two earlier theorems whole, since Gallai's theorem follows from it and so does Tutte's 1-factor theorem from Chapter 2.

Two clean consequences avoid the heavy machinery. Recall \(\kappa_H(G)\), the fewest vertices outside \(H\) that meet every \(H\)-path, and \(\lambda_H(G)\), the fewest edges that do.

Proof idea. Turn an optimal mixed blockade into a pure vertex blockade by keeping \(X\) and adding, for each edge cluster, all but one of its boundary vertices. That at most doubles the score, so \(\kappa_H(G) \le 2 M_H(G)\) and Mader's equality does the rest; the edge version follows by the line graph trick. Whatever it costs to block every round trip with vertices alone, you can run at least half that many, and the factor of two is the price of banning mixed blockades.

Linking prescribed pairs

Every theorem so far counted paths without caring which endpoint went with which: Menger hands you \(k\) disjoint routes and you take the pairing you are given. Now make the problem harder. You have \(k\) calls to place, call \(i\) running from \(s_i\) to \(t_i\), and the pairing is not negotiable. Can the network carry them all at once without collisions?

The clause forbidding interior vertices in \(X\) earns its place: the leftover vertices of \(X\), the ones not currently serving as terminals, stay untouched and available inside a bigger argument. Stated in the second form, with exactly \(2k\) terminals named, that condition takes care of itself.

Every \(k\)-linked graph is \(k\)-connected, for the same free reason as before: if fewer than \(k\) vertices could separate the graph, pick terminals on both sides and no linkage could cross. The converse fails, and it fails at the smallest possible size.

So \(k\)-linked is strictly stronger than \(k\)-connected. The question of the section is how much stronger. Does high connectivity eventually force linkedness, and if so how high?

The first answer, from 1970, is yes with an appalling constant. Its engine is a result whose proof Diestel postpones to the extremal graph theory chapter: there is a function \(h\) such that any graph whose average degree is at least \(h(r)\) contains a subdivision \(TK^r\), meaning \(r\) branch vertices joined pairwise by internally disjoint paths.^[5]

Proof idea. High connectivity forces high average degree, which produces a subdivided complete graph \(TK^{3k}\) inside \(G\). Its branch vertices form a switchboard in which every pair of ports already owns a private corridor. Menger's theorem carries the \(2k\) terminals into that switchboard along disjoint paths, chosen to use as few outside edges as possible; the economy leaves \(k\) ports spare, one per demand, so each pair \(s_i, t_i\) is stitched through its own spare port.

Thirty-five years later the constant came down to something usable. The improvement replaces "find an enormous switchboard" with "find a small dense one", which needs far less connectivity but does need the graph to be genuinely edge-rich.

Proof idea, in outline. The statement as written is too rigid to induct on, so it is replaced by a flexible claim: if the territory outside the terminal set \(X\) is edge-rich, and every bottleneck cutting a piece away from \(X\) cuts away only an edge-poor piece, then \(X\) is linked. Diestel calls edge-rich sets heavy and edge-poor sets light, measuring \(\|U\|^+\) against \(8k|U|\). The gain is that "everything cut off is light" survives edge deletion and contraction, whereas \(2k\)-connectedness does not.

The induction runs on graph size and on the number of edges outside \(X\). A bottleneck whose far side can itself route any pairing of the interface acts as a black box, and Menger's theorem finishes at once, so assume none exists. Contracting or deleting an edge outside \(X\) then either preserves the hypotheses, letting induction apply, or squeezes the smallest outside degree into a narrow window, where a minimum-degree vertex and its neighbours form a small dense graph.

With that local switchboard in hand, Menger's theorem applies one last time: either it links \(X\) to the switchboard by \(|X|\) disjoint paths, finishing the argument, or it produces exactly the bottleneck already ruled out. The Notes record refinements: edge density \(5k\) is enough, and for graphs of large girth, meaning no short cycles, \(2k\)-connectedness alone suffices.^[5]

What to carry forward

Four things from this chapter deserve permanent residence.

First, the min-max habit in its most quoted form: a quantity defined by destruction, the cheapest way to break something, equals a quantity defined by construction, the largest number of non-colliding routes. Whenever you meet a hard combinatorial minimum, ask what maximum it might secretly equal.

Second, the build recipes. Two-connected means cycle plus ears; three-connected means \(K^4\) plus vertex splittings, or \(K^4\) plus edge additions with subdivisions. A property defined by a prohibition becomes one you can generate, and generation is what makes induction possible.

Third, the three flavours of non-collision: disjoint paths share nothing, independent paths share only their two endpoints, edge-disjoint paths may share vertices freely. Menger's theorem is stated for disjoint paths between sets, and its two-vertex corollaries split into an independent-path version, needing non-adjacent endpoints, and an edge version, which does not.

Fourth, the gap between counting and prescribing. Getting \(k\) routes is a connectivity question; getting \(k\) routes that join the pairs you named is strictly harder, and bringing that gap under a linear bound took from 1970 to 2005.

The threads continue. Menger's theorem returns as the unit-capacity ancestor of max-flow min-cut in Chapter 6, which supplies another proof of it. The alternating-walk lemmas are reused word for word in Chapter 8 for infinite graphs. The block tree becomes the tree-decompositions of Chapter 12. And the planarity arguments of Chapter 4 lean on the 3-connected recipes proved here.