A short proof of the path-width theorem

Reinhard Diestel

Robertson and Seymour proved that excluding any fixed forest F as a minor imposes a bound on the path-width of a graph. We give a short proof of this, reobtaining the best possible bound of |F | − 2.

1. Introduction

At the start of their Graph Minors series, Robertson and Seymour [ 1 ] proved, by a long and involved argument, that for every forest F there exists an integer n such that every graph without an F minor has path-width at most n. This bound was brought down to the best possible value by Bienstock, Robertson, Seymour and Thomas [ 2 ], who proved the following:

Theorem 1. [ 2 ] For every forest F, every graph of path-width ⩾ |F | − 1 has a minor isomorphic to F.

The authors remark that this result is best possible in two ways. First, the value of |F | − 1 is sharp, because the complete graph K_{n−1} has path-width n − 2 but has no (forest) minor on n vertices. Second, if F is not a forest then the exclusion of F as a minor does not bound the path-width of a graph: as noted without proof in [ 1 ], trees can have arbitrarily large path-width (but will never contain F as a minor if F contains a cycle).

The proof of Theorem 1 in [ 2 ], already much shorter than [ 1 ], relies on a non-trivial minimax theorem involving the concept of “blockages”. (These were adapted from “tangles”, a central concept in the Graph Minors series concerning tree-width.) Although interesting in its own right, it turns out that this minimax theorem is not needed for a proof of Theorem 1; the purpose of this note is to give a short direct proof.

2. Definitions

Graphs in this paper are finite, and they may have loops or multiple edges. Let G be a graph. If X ⊆ V (G) or X ⊆ G, then G [ X] denotes the subgraph of G induced by the vertices in X. Following [ 2 ], we denote by att (X) (for “attachment”) the set of those vertices in X that have a neighbour in G − X, and write α(X) := |att (X)|. A minor of G is a graph obtained from a subgraph of G by contracting edges.

A path-decomposition of G is a non-empty sequence (W_{1}, …, W_{s}) of subsets of V (G) such that

(i) W_{1} ∪ … ∪ W_{s} = V (G), and for every edge e of G there exists an r ⩽ s such that both endvertices of e are in W_{r};

(ii) W_{p} ∩ W_{r} ⊆ W_{q} whenever 1 ⩽ p ⩽ q ⩽ r ⩽ s. The width of a path-decomposition as above is the number

max { |W_{r}| − 1 : 1 ⩽ r ⩽ s } ,

and the path-width of G is the smallest width of any path-decomposition of G.

For each positive integer n, we denote by B_{n} = B_{n}(G) the unique minimal subset of the power set of V (G) satisfying the following two conditions:

(i) ∅ ^{∈} B_{n};

(ii) if X ^{∈} B_{n}, X ⊆ Y ⊆ V (G) and α(X) + |Y \X| ⩽ n, then Y ^{∈} B_{n}. Thus, a set X ⊆ V (G) is in B_{n} if and only if there is a sequence

∅ = X_{0} ⊆ … ⊆ X_{s} = X

such that α(X_{r}) + |X_{r+1}\X_{r}| ⩽ n for all r < s.

For example, if (W_{1}, …, W_{s}) is a path-decomposition of G of width < n, then all the sets W_{1} ∪ … ∪ W_{r} for r ⩽ s, including V (G) (for r = s), are in B_{n}. This is easy to verify by induction on r from the axioms of a pathdecomposition, but will not be used below. Its converse is also true, and will be needed later:

(2.1) If V (G) ^{∈} B_{n} then G has path-width < n.

Indeed, if V (G) ^{∈} B_{n} then there is a sequence ∅ = X_{0} ⊆ … ⊆ X_{s} = V (G) such that α(X_{r}) + |X_{r+1}\X_{r}| ⩽ n for all r < s. With

W_{r} := att (X_{r−1}) ∪ (X_{r}\X_{r−1})

for all 1 ⩽ r ⩽ s, the sequence (W_{1}, …, W_{s}) is easily seen to be a pathdecomposition of G of width < n.

3. Proof of the theorem

In our proof of Theorem 1, we essentially follow the proof of [ 2, (3.1) ], albeit in a less elegant and rather more straighforward inductive set-up (for a bit of mathematical glasnost). Instead of [ 2 ]’s minimax theorem on blockages, we shall use the following lemma.

Lemma. Let G be a graph, Y ^{∈} B_{n}(G), and Z ⊆ Y. Assume that there is a set { P (z) : z ^{∈} att (Z) } of disjoint paths in G such that each P (z) starts in z, has no other vertex in Z, and ends in att (Y). Then Z ^{∈} B_{n}(G).

Proof. By definition of B_{n}, there are sets ∅ = Y_{0} ⊆ … ⊆ Y_{s} = Y such that α(Y_{r}) + |Y_{r+1}\Y_{r}| ⩽ n for all r < s. We claim that, with

Z_{r} := Y_{r} ∩ Z,

we likewise have α(Z_{r}) + |Z_{r+1}\Z_{r}| ⩽ n for all r < s, showing that Z = Z_{s} ^{∈} B_{n}.

Fix r. Since

Z_{r+1}\Z_{r} = Z_{r+1}\Y_{r} ⊆ Y_{r+1}\Y_{r} ,

it suffices to show that α(Z_{r}) ⩽ α(Y_{r}). We prove this by constructing a 1–1 map z ↦ y from att (Z_{r})\att (Y_{r}) to att (Y_{r})\att (Z_{r}).

Consider a vertex z ^{∈} att (Z_{r})\att (Y_{r}). Then z has a neighbour in Y_{r}\Z_{r} = Y_{r}\Z, so z ^{∈} att (Z). Now P (z) is a path from (Z_{r} ⊆) Y_{r} to att (Y), and att (Y_{r}) separates these two sets in G. Therefore P (z) has a vertex y in att (Y_{r}); note that y ≠ z by the choice of z. As z is the only vertex of P (z) in Z, we thus have y ^{∈} att (Y_{r}) ∖ att (Z_{r}). By definition of the paths P (z), the vertices y are distinct for different z, so α(Z_{r}) ⩽ α(Y_{r}) as claimed. □

We are now ready to prove Theorem 1. Let us assume, without loss of generality, that F is a tree. Let G be a graph of path-width at least n = |F | − 1, and let (v_{1}, …, v_{n+1}) be an enumeration of V (F) such that F [ v_{1}, …, v_{i}] is connected for all i. Then, for each i ⩽ n, exactly one vertex in { v_{1}, …, v_{i} } is adjacent to v_{i+1}.

For every i = 0, …, n, we shall define a set C^{i} = { C_{0}^{i}, …, C_{i}^{i} } of disjoint subgraphs of G, so that C_{j}^{k} ⊆ C_{j}^{ℓ} whenever j ⩽ k ⩽ ℓ, and all C_{j}^{i} with j > 0 are connected. We shall write X^{i} := V ( ⋃ C^{i}). For each i, the following four statements will hold:

(i) G contains an edge between C_{j}^{i} and C_{k}^{i} whenever 1 ⩽ j < k ⩽ i and v_{j}v_{k} ^{∈} E(F) (so F [ v_{1}, …, v_{i}] is a minor of G [ C_{1}^{i} ∪ … ∪ C_{i}^{i}]);

(ii) α(X^{i}) = i, and |V (C_{j}^{i}) ∩ att (X^{i})| = 1 for all 1 ⩽ j ⩽ i; (iii) X^{i} ^{∈} B_{n}; (iv) α(X) > i for all X ^{∈} B_{n} with X^{i} ⫋ X.

Let C_{0}^{0} be an inclusion-maximal subgraph of G with V (C_{0}^{0}) ^{∈} B_{n} and α(C_{0}^{0}) = 0 (possibly C_{0}^{0} = ∅). Then (i)–(iv) hold for i = 0. Assume now that C^{i} has been defined so that (i)–(iv) holds, for some i ⩽ n. If i = 0, let x be any vertex of G − C_{0}^{0}; note that G − C_{0}^{0} ≠ ∅, since V (C_{0}^{0}) ^{∈} B_{n} but V (G) /^{∈} B_{n} by (2.1). If i > 0, consider the unique j ⩽ i such that v_{j}v_{i+1} ^{∈} E(F), and let x ^{∈} G − X^{i} be a neighbour of the unique vertex in V (C_{j}^{i}) ∩ att (X^{i}). Let X := X^{i} ∪ { x }.

If i = n, then (i) and the choice of x imply that F is a minor of G [ X] and we are done. So we assume that i < n. Then, by (ii), (iii) and the definition of B_{n}, we have X ^{∈} B_{n}. Thus, α(X) > i by (iv). As clearly att (X) ∩ X^{i} ⊆ att (X^{i}), this means that att (X) = att (X^{i}) ∪ { x } and α(X) = i + 1. Let Y be inclusion-maximal in B_{n} with X ⊆ Y and α(Y) = i + 1. (This set Y will later be our X^{i+1}.)

By Menger’s theorem, G [ Y ] contains a set P of disjoint paths from X to att (Y) and a separator S ⊆ Y between these sets consisting of a choice of exactly one vertex from every path in P. Let Z denote the union of S and all the vertex sets of components of G − S meeting X. Then X^{i} ⫋ X ⊆ Z. By the choice of S and definition of att (Y), we further have Z ⊆ Y. Since att (Z) = S, this means that Z ^{∈} B_{n} by the Lemma. By (iv), then, |P| = |S| = α(Z) > i. By definition of att (X), each of the paths in P meets att (X). Thus i < |P| ⩽ α(X) = i + 1, so |P| = i + 1 and the paths in P contain a perfect path matching between att (X) and att (Y).

We now define C^{i+1}. Let C_{0}^{i+1} := C_{0}^{i} ∪G[Y ∖(X ∪V (⋃ P))]. For 1 ⩽ j ⩽ i, let x_{j} be the unique vertex of C_{j}^{i} in att (X^{i}) and P_{j} the path in P containing it, and define C_{j}^{i+1} as the union of C_{j}^{i} with the final segment of P_{j} starting at x_{j}. Finally, let C_{i+1}^{i+1} be the final segment from x of the path in P containing x. Then X^{i+1} = V (⋃ C^{i+1}) = Y. Now C^{i+1} = { C_{0}^{i+1}, …, C_{i+1}^{i+1} } satisfies, for i + 1, condition (i) by the choice of x and of C_{i+1}^{i+1}; conditions (ii) and (iii) since X^{i+1} = Y; condition (iv) by the choice of Y and X^{i} ⊆ Y = X^{i+1} together with (iv) for i.

As remarked before, the assertion of the theorem follows from the definition of X in the case of i = n.

References

[ [ 1 ]] N. Robertson and P.D. Seymour, Graph minors. I. excluding a forest, J. Combin. Theo-

ry B 35 (1983), 39–61. [ [ 2 ]] D. Bienstock, N. Robertson, P.D. Seymour and R. Thomas, Quickly excluding a forest,

J. Combin. Theory B 52 (1991), 274–283.