Highly connected sets and the excluded grid theorem

Reinhard Diestel Tommy R. Jensen

Faculty of Mathematics Technical University of Chemnitz D-09107 Chemnitz Germany

Konstantin Yu. Gorbunov

Institute of New Technologies Nizhnyaya Radishchevskaya 10 Moscow, 109004 Russia

Carsten Thomassen

Mathematics Institute Technical University of Denmark DK-2800 Lyngby Denmark

June 7, 2000

Abstract We present a short proof of the excluded grid theorem of Robertson and Seymour, the fact that a graph has no large grid minor if and only if it has small tree-width. We further propose a very simple obstruction to small tree-width inspired by that proof, showing that a graph has small tree-width if and only if it contains no large highly connected set of vertices.

1 Introduction

The following theorem of Robertson and Seymour [5] plays a fundamental role in their theory of graph minors:

Theorem 1 Given any graph X, the graphs without an X minor have bounded tree-width if and only if X is planar.

Since planar grids can have arbitrarily large tree-width (see below), the ‘only if’ direction here is immediate: if X is non-planar then no grid has an X minor, and hence the graphs without an X minor have unbounded tree-width. Conversely, we have to show that forbidding any planar minor bounds the treewidth of a graph. And again, since every planar graph G is the minor of some large enough grid (take a drawing of G with ‘fat’ vertices and superimpose a drawing of a sufficiently fine grid), it suffices to show the following:

Theorem 2 For every integer r there is an integer k such that every graph of tree-width at least k has an r × r grid minor.

Proofs of Theorem 2 have been given by Robertson & Seymour [5], by Robertson, Seymour & Thomas [7], and by Reed [3]. All these proofs are long and technical. Our main purpose in this paper is to offer a short and selfcontained new proof of Theorem 2. This will be given in Section 3, which can be read independently of the rest of the paper.

We remark that our proof of Theorem 2 may be combined with [4] and [8] to give the shortest known proof of one of the main corollaries of the Robertson-Seymour graph minor theorem (‘Wagner’s conjecture’), the ‘generalized Kuratowski’ result that the graphs embeddable in any fixed surface are characterized by finitely many forbidden minors. A proof of the graph minor theorem itself is sketched in [1, Chapter 12]; among other things, the sketch indicates the role that Theorem 1 plays in that proof.

Our second aim in this paper is to draw attention to another obstruction to small tree-width, implied by (but different from) large grid minors: large ‘highly connected’ sets of vertices. In Section 2 we give a very simple proof that a graph has small tree-width if and only if it contains no such set of vertices. A result with a similar flavour has been obtained by Reed as a spin-off of the theory of ‘brambles’ [3, combine Lemma 3.4 with Theorem 2.11].

Our terminology follows [1]. (A general introduction to tree-decompositions and graph minors may also be found there, as well as in [9].) The vertex sets into which a tree-decomposition decomposes a graph will be called the parts of that decomposition. For the notion of tree-width, we just recall that treedecompositions of width < k may have parts containing up to k vertices; thus, trees have tree-width 1. If C is a subgraph of a graph G, we write N(C) for its set of neighbours in G − C, the set of vertices in G − C adjacent to a vertex in C. A separation of G is an ordered pair (A, B) of subgraphs of G such that A∪B = G and E(A)∩E(B) = ∅; its order is the number |A∩B|. The n×n grid is the graph on {1, …, n}^{2} with edge set {(i, j)(i′, j′) : |i−i′|+|j −j′| = 1}. We call a set X ⊆ V (G) k-connected in G if |X| ≥ k and for all subsets Y, Z ⊆ X with |Y | = |Z| ≤ k there are |Y | disjoint Y –Z paths in G. (The sets Y and Z are not required to be disjoint.) X is externally k-connected if, in addition, the required paths can be chosen without an inner vertex or edge in G[X]. For example, the vertex set of any k-connected subgraph of G is k-connected in G (though not necessarily externally), but also any horizontal path of the k × k grid is k-connected in the grid, even externally.

2 Highly connected sets

In this section we show that a graph has small tree-width if and only if it has no large highly connected sets of vertices. The proof of the first part of the following proposition uses no more than standard tree-decomposition techniques; we include it for the convenience of those readers new to the subject.

Proposition 3 Let G be a graph and k > 0 an integer.

(i) If G has tree-width < k then G contains no (k + 1)-connected set of size ≥ 3k.

(ii) Conversely, if G contains no externally (k + 1)-connected set of size ≥ 3k then G has tree-width < 4k.

Proof (i) Choose a tree-decomposition (T, (V_{t})_{t∈T}) of G of width < k, without loss of generality so that none of the parts V_{t} is contained in another. Then for every edge e = rs of T, the set V_{r} ∩ V_{s} has < k vertices and separates the sets U_{r} := ⋃_{t∈T_{r}} V_{t} and U_{s} := ⋃_{t∈T_{s}} V_{t} in G; here, T_{r} and T_{s} denote the components of T − e containing r and s, respectively. Any separation (A, B) of G with vertex sets {V (A), V (B)} = {U_{r}, U_{s}} (and hence V (A ∩ B) = V_{r} ∩ V_{s}) is said to correspond to e.

Suppose X is a (k + 1)-connected set of size ≥ 3k in G. Orient every edge e of T towards the component T′ of T − e for which |X ∩ ⋃_{t∈T′} V_{t}| is greater, breaking ties arbitrarily. Choose a vertex t ∈ T so that all the edges e_{1}, …, e_{n} of T at t point towards t. For every i = 1, …, n pick a separation (A_{i}, B_{i}) corresponding to e_{i}, with V_{t} ⊆ B_{i}. Then |V (A_{i}) ∩ X| < k: otherwise, both A_{i} and B_{i} would have k vertices in X, and we could extend V (A_{i} ∩ B_{i}) ∩ X to k-subsets Y ⊆ V (A_{i}) ∩ X and Z ⊆ V (B_{i}) ∩ X that cannot be linked by k disjoint paths in G (since |A_{i} ∩ B_{i}| < k).

Now let i ≤ n be minimal such that |V (A_{1} ∪ … ∪ A_{i}) ∩ X| > k, and put A := A_{1} ∪ … ∪ A_{i} and B := B_{1} ∩ … ∩ B_{i}. By the minimality of i and since |V (A_{i}) ∩ X| < k, we have |V (A) ∩ X| < 2k, so |V (B) ∩ X| > |X| − 2k ≥ k. As before, we may extend V (A ∩ B) ∩ X to (k + 1)-sets Y ⊆ V (A) ∩ X and Z ⊆ V (B) ∩ X. As V_{t} separates these sets in G and |V_{t}| ≤ k, this contradicts our assumption that X is (k + 1)-connected in G.

(ii) We prove the following more general assertion:

If h ≥ k and G contains no externally k-connected set of size h, then G has tree-width < h + k − 1.

Let U ⊆ V (G) be maximal such that G[U] has a tree-decomposition D of width < h + k − 1 such that every component C of G − U has at most h neighbours in U and these lie in one part of D (depending on C).

We claim that U = V (G). Suppose not. Let C be a component of G−U and write X := N(C). By assumption, |X| ≤ h. In fact |X| = h, since otherwise for any v ∈ V (C) we could add X ∪ {v} to D as a new part, contradicting the maximality of U. Hence by assumption, X is not externally k-connected in G; let Y, Z ⊆ X be sets to witness this.

By Menger’s theorem, Y and Z are separated in H := G[V (C) ∪ Y ∪ Z] − E(G[Y ∪ Z]) by a set S of fewer than |Y | = |Z| ≤ k vertices. Let X_{Y} := (X \ Z) ∪ S and X_{Z} := (X \ Y) ∪ S. Clearly, |X ∪ S| ≤ h + k − 1 and |X_{Y} |, |X_{Z}| < |X| = h. Moreover, any component C′ ⊆ C of G − (U ∪ S) has all its neighbours in X ∪ S, and hence either in X_{Y} or in X_{Z}: otherwise H − S would contain a Y –Z path through C′.

Extending U to U ∪ S and adding X ∪ S to D as a new part, we obtain a contradiction to the maximality of U. (Note that S∩C ≠ ∅, since |S| < |Y | = |Z| and Y, Z ⊆ N(C).) □

It is perhaps interesting to note that Proposition 3(i) is best possible (or nearly so) in various ways, and remains so even if we weaken its assertion by inserting ‘externally’ before ‘(k + 1)-connected’. For example, a complete bipartite graph with vertex sets X and Y of sizes k − 1 and n ≥ k − 1, respectively, has tree-width < k (with parts X ∪ {y}, y ∈ Y) and clearly Y is an externally (k −1)-connected set whose size is not bounded as a function of k. Only slightly less trivially, consider the complete bipartite graph G with vertex sets X and Y of sizes k ≥ 5 and 3k, respectively. Partition Y into three sets Y_{1}, Y_{2}, Y_{3} of size k, and delete a perfect matching from each of the three bipartite subgraphs G[X ∪ Y_{i}]. The resulting graph again has tree-width < k (with parts X and (X \ {x}) ∪ {y} for all y ∈ Y, where x is the unique non-neighbour of y), and an easy application of Hall’s theorem shows that Y is externally k-connected in it.

The above example shows that the value of k in the premise and the value of (k + 1) in the conclusion of Proposition 3(i) are best possible. The value of 3k in the conclusion is also essentially best possible. This is exemplified by the following graph G of tree-width < k that contains an externally (k + 1)- connected (even |X|-connected) set X of size 3(k−1). First we define a partially ordered set, as follows. Starting with a linearly ordered (k − 1)-set R, we put three linearly ordered (k − 1)-sets S_{1}, S_{2}, S_{3} above R, letting elements from different S_{i} be incomparable. To make this into a graph, we add all possible edges on R and join every vertex from one of the S_{i} to all the vertices in the (k − 1)-chain directly below it. (Note that this graph has a tree-decomposition into its k-cliques.) Finally, we add new independent (k − 1)-sets X_{1}, X_{2}, X_{3}, joining X_{i} completely to S_{i} for each i = 1, 2, 3. It is now easily checked that any two (disjoint) sets Y, Z ⊆ X_{1} ∪ X_{2} ∪ X_{3} of equal size can be linked in G by |Y | = |Z| disjoint paths: vertices y, z in the same X_{i} can be linked via the corresponding S_{i} using its highest vertices, and any remaining pairs y, z can be joined via the lower vertices of the S_{i} and R.

Proposition 3(ii) is also best possible: the complete graph on 4k vertices shows that we cannot strengthen the conclusion, while the complete graph on 4k+1 vertices shows that we cannot weaken the premise in either way. Similarly, K_{h+k−1} and K_{h+k} (for h ≥ 2k + 2) show that the more general assertion we prove is best possible.

3 Grid minors

We now present our proof of Theorem 2. Very roughly, we shall assume that a given graph G has large tree-width, find a large highly connected set X in G as in Proposition 3(ii), and use its connecting paths P to form a grid. Of course, this will be possible only if those paths intersect sufficiently. If they do not, we shall try instead to partition X into many sets that can be linked pairwise by mutually disjoint paths, so that contracting these sets will give us a subdivision of a large complete graph. Since we may only contract connected sets when forming a minor, our first task will thus be to strengthen Proposition 3(ii) so as to give X a partition into many sets that can be made connected in a part of G not used by the paths P.

In order to make this section self-contained, we prove all the lemmas that we need from first principles. This goes in particular for our first lemma, the strengthening of Proposition 3(ii) indicated above.

Let us call a separation (A, B) a premesh if all the edges of A ∩ B lie in A and A contains a tree T with the following properties:

• T has maximum degree ≤ 3;

• every vertex of A ∩ B lies in T and has degree ≤ 2 in T;

• T has a leaf in A ∩ B (that is, a vertex of degree ≤ 1).

A premesh (A, B) will be called a k-mesh if V (A ∩ B) is externally k-connected in B, and the graph G = A ∪ B is said to have this premesh or k-mesh.

Lemma 4 Let G be a graph and let h ≥ k ≥ 1 be integers. If G has no k-mesh of order h then G has tree-width < h + k − 1.

Proof We may assume that G is connected. Let U ⊆ V (G) be maximal such that G[U] has a tree-decomposition D of width < h + k − 1, with the additional property that, for every component C of G − U, the neighbours of C in U lie in one part of D and (G − C, C̄) is a premesh of order ≤ h, where C̄ := G[V (C) ∪ N(C)] − E(G[N(C)]). Clearly, U ≠ ∅.

We claim that U = V (G). Suppose not. Let C be a component of G − U, put X := N(C), and let T be a tree associated with the premesh (G − C, C̄).

By assumption, |X| ≤ h; let us show that equality holds here. If not, let u ∈ X be a leaf of T and v a neighbour of u in C. Put U′ := U ∪ {v} and X′ := X ∪ {v}, let T′ be the tree obtained from T by joining v to u, and let D′ be the tree-decomposition of G[U′] obtained from D by adding X′ as a new part. Clearly D′ still has width < h + k − 1. Consider a component C′ of G − U′. If C′ ∩ C = ∅ then C′ is also a component of G − U, so N(C′) lies inside a part of D (and hence of D′), and (G − C′, C̄′) is a premesh of order ≤ h by assumption. If C′ ∩ C ≠ ∅, then C′ ⊆ C and N(C′) ⊆ X′. Moreover, v ∈ N(C′): otherwise N(C′) ⊆ X would separate C′ from v, contradicting the fact that C′ and v lie in the same component C of G−X. Since v is a leaf of T′, it is straightforward to check that (G − C′, C̄′) is again a premesh of order ≤ h, contrary to the maximality of U.

Thus |X| = h, so by assumption our premesh (G−C, C̄) cannot be a k-mesh. Hence by Menger’s theorem, there are sets Y, Z ⊆ X of equal size ≤ k that are separated in H := C̄[V (C) ∪ Y ∪ Z] by a set S of k′ < |Y | = |Z| vertices, one from each of a family (P_{s} | s ∈ S) of disjoint Y –Z paths in H. Put X′ := X ∪ S and U′ := U ∪ S, and let D′ be the tree-decomposition of G[U′] obtained from D by adding X′ as a new part. Clearly, |X′| ≤ |X| + |S| ≤ h + k − 1. We show that U′ contradicts the maximality of U.

Since Y ∪ Z ⊆ N(C) and |S| < |Y | = |Z| we have S ∩ C ≠ ∅, so U′ is larger than U. Let C′ be a component of G − U′. If C′ ∩ C = ∅, we argue as earlier. So C′ ⊆ C and N(C′) ⊆ X′. As before, at least one neighbour v of C′ lies in S ∩C. By definition of S, C′ cannot have neighbours in both Y \S and Z \S; we assume it has none in Y \ S. Let T′ be the union of T and all the Y –S subpaths of paths P_{s} with s ∈ N(C′) ∩ C; since these subpaths start in Y \ S and have no inner vertices in X′, they cannot meet C′. Therefore (G − C′, C̄′) is a premesh with tree T′ and leaf v; the degree conditions on T′ are easily checked. Its order is |N(C′)| ≤ |X|−|Y |+|S| = h−|Y |+k′ < h, a contradiction to the maximality of U. □

Lemma 5 Let k ≥ 2 be an integer. Let T be a tree of maximum degree ≤ 3 and X ⊆ V (T), such that every x ∈ X has degree ≤ 2 in T. Then T has a set E of edges such that every component of T − E has between k and 2k − 2 vertices in X, except that one such component may have fewer vertices in X.

Proof Induction on |X|. If |X| ≤ 2k − 2 we put E = ∅. So assume that |X| ≥ 2k − 1. Let e be an edge of T such that some component T′ of T − e has at least k vertices in X and T′ is as small as possible. As Δ(T) ≤ 3, the end of e in T′ has degree at most two in T′, so the minimality of T′ implies that |X ∩ V (T′)| ≤ 2k − 2. We finish by applying the induction hypothesis to T − T′.

□

Lemma 6 Let G be a bipartite graph with bipartition (A, B), |A| = a, |B| = b, and let c ≤ a and d ≤ b be positive integers. Assume that G has at most (a − c)(b − d)/d edges. Then there exist C ⊆ A and D ⊆ B such that |C| = c and |D| = d and C ∪ D is independent in G.

Proof As ||G|| ≤ (a − c)(b − d)/d, fewer than b − d vertices in B have more than (a − c)/d neighbours in A. Choose D ⊆ B so that |D| = d and each vertex in D has at most (a − c)/d neighbours in A. Then D sends a total of at most a − c edges to A, so A has a subset C of c vertices without a neighbour in D. □

Given a tree T, call an r-tuple (x_{1}, …, x_{r}) of distinct vertices of T good if, for every j = 1, …, r − 1, the x_{j}–x_{j+1} path in T contains none of the other vertices in this r-tuple.

Lemma 7 Every tree of order ≥ r(r − 1) has a good r-tuple of vertices.

Proof If x is any vertex of a tree T, then T is the union of its subpaths x … y, where y ranges over its leaves. Hence unless one of these paths has at least r vertices, T has at least |T |/(r − 1) leaves. Since any path of r vertices and any set of r leaves defines a good r-tuple in T, this proves the assertion. □

Our next lemma shows how to obtain a grid from two large systems of paths that intersect in a particularly orderly way.

Lemma 8 Let d, r ≥ 2 be integers such that d ≥ r^{2r+2}. Let G be a graph containing a set H of r^{2} − 1 disjoint paths and a set V = {V_{1}, …, V_{d}} of d disjoint paths. Assume that every path in V meets every path in H, and that each path H ∈ H consists of d consecutive (vertex disjoint) segments such that V_{i} meets H only in its ith segment, for every i = 1, …, d. Then G has an r × r grid minor.

Proof For each i = 1, …, d, consider the graph with vertex set H in which two paths are adjacent whenever V_{i} contains a subpath between them that meets no other path in H. Since V_{i} meets every path in H, this is a connected graph; let T_{i} be a spanning tree in it. Since |H| ≥ r(r − 1), Lemma 7 implies that each of these d ≥ r^{2}(r^{2})^{r} trees T_{i} has a good r-tuple of vertices. Since there are no more than (r^{2})^{r} distinct r-tuples on H, some r^{2} of the trees T_{i} have a common good r-tuple (H^{1}, …, H^{r}). Let I = {i_{1}, …, i_{r^{2}}} be the index set of these trees (with i_{j} < i_{k} for j < k) and put H′ := {H^{1}, …, H^{r}}.

Here is an informal description of how we construct our r × r grid. Its ‘horizontal’ paths will be the paths H^{1}, …, H^{r}. Its ‘vertical’ paths will be pieced together edge by edge, as follows. The r − 1 edges of the first vertical path will come from the first r − 1 trees T_{i}, trees with their index i among the first r elements of I. More precisely, its ‘edge’ between H^{j} and H^{j+1} will be the sequence of subpaths of V_{i_{j}} (together with some connecting horizontal bits taken from paths in H \ H′) induced by the edges of an H^{j}–H^{j+1} path in T_{i_{j}} that has no inner vertices in H′. (This is why we need (H^{1}, …, H^{r}) to be a good r-tuple in every tree T_{i}.) Similarly, the jth edge of the second vertical path will come from an H^{j}–H^{j+1} path in T_{i_{r+j}}, and so on. To merge these individual edges into r vertical paths, we then contract in each H^{j} the initial segment that meets the first r paths V_{i} with i ∈ I, then contract the segment that meets the following r paths V_{i} with i ∈ I, and so on.

Formally, we proceed as follows. For all j, k ∈ {1, …, r}, consider the minimal subpath H_{k}^{j} of H^{j} that contains the ith segment of H^{j} for all i with i_{(k−1)r} < i ≤ i_{kr} (put i_{0} := 0). Let Ĥ^{j} be obtained from H^{j} by first deleting any vertices following its i_{r^{2}}th segment and then contracting every subpath H_{k}^{j} to one vertex v_{k}^{j}. Thus, Ĥ^{j} = v_{1}^{j} … v_{r}^{j}.

Given j ∈ {1, …, r − 1} and k ∈ {1, …, r}, we have to define a path V_{k}^{j} that will form the subdivided ‘vertical edge’ v_{k}^{j}v_{k}^{j+1}. This path will consist of segments of the path V_{i} together with some otherwise unused segments of paths from H\H′, for i := i_{(k−1)r+j}; recall that, by definition of Ĥ^{j} and Ĥ^{j+1}, this V_{i} does indeed meet H^{j} and H^{j+1} precisely in vertices that were contracted into v_{k}^{j} and v_{k}^{j+1}, respectively. To define V_{k}^{j}, consider an H^{j}–H^{j+1} path P = H_{1} … H_{t} in T_{i} that has no inner vertices in H′. Every edge H_{s}H_{s+1} of P corresponds to an H_{s}–H_{s+1} subpath of V_{i} that has no inner vertex on any path in H. Together with (parts of) the ith segments of H_{2}, …, H_{t−1}, these subpaths of V_{i} form an H^{j}–H^{j+1} path P′ that has no inner vertices on any of the paths H^{1}, …, H^{r} and meets no path from H outside its ith segment. Replacing the ends of P′ on H^{j} and H^{j+1} with v_{k}^{j} and v_{k}^{j+1}, respectively, we obtain our desired path V_{k}^{j} forming the jth (subdivided) edge of the kth ‘vertical’ path of our grid. Since the paths P′ are disjoint for different i and different pairs (j, k) do give rise to different i, the paths V_{k}^{j} are disjoint except for possible common ends v_{k}^{j}. Moreover, they have no inner vertices on any of the paths H^{1}, …, H^{r}, because none of these H^{j} is an inner vertex of any of the paths P ⊆ T_{i} used in the construction of V_{k}^{j}.

□

We are now ready to prove the following quantitative version of Theorem 2.

Theorem 9 Let r, m > 0 be integers, and let G be a graph of tree-width at least r^{4m^{2}(r+2)}. Then G contains either K_{m} or the r × r grid as a minor.

Proof Since K_{r^{2}} contains the r × r grid as a subgraph, we may assume that 2 ≤ m ≤ r^{2}. Put c := r^{4(r+2)} and k := c^{2\binom{m}{2}}. Then 2m + 2 ≤ c, so G has tree-width at least c^{m^{2}} ≥ (2m + 2)k: more than enough for Lemma 4 to ensure that G contains a k-mesh (A, B) of order (2m + 1)(k − 1). Let T ⊆ A be a tree associated with the premesh (A, B); thus, X := V (A ∩ B) ⊆ V (T). By Lemma 5, T has (|X| − (k − 1))/(2k − 2) = m disjoint subtrees each containing at least k vertices of X; let A_{1}, …, A_{m} be the vertex sets of these trees. By definition of a k-mesh, B contains for all 1 ≤ i < j ≤ m a set P_{ij} of k disjoint A_{i}–A_{j} paths that have no inner vertices in A. These sets P_{ij} will shrink a little and be otherwise modified later in the proof, but they will always consist of ‘many’ disjoint A_{i}–A_{j} paths.

One option in our proof will be to find single paths P_{ij} ∈ P_{ij} that are disjoint for different pairs ij and thus link up the sets A_{i} to form a K_{m} minor of G. If this fails, we shall instead exhibit two specific sets P_{ij} and P_{pq} such that many paths of P_{ij} meet many paths of P_{pq}, forming an r × r grid between them by Lemma 8.

Let us impose a linear ordering on the index pairs ij by fixing an arbitrary bijection σ : \{ij | 1 ≤ i < j ≤ m\} → \{0, 1, …, \binom{m}{2}−1\}. For ℓ = 0, 1, … in turn, we shall consider the pair pq with σ(pq) = ℓ and choose an A_{p}–A_{q} path P_{pq} that is disjoint from all previously selected such paths, i.e. from the paths P_{st} with σ(st) < ℓ. At the same time, we shall replace all the ‘later’ sets P_{ij}—or what has become of them—by smaller sets containing only paths that are disjoint from P_{pq}. Thus for each pair ij, we shall define a sequence P_{ij} = P_{ij}^{0}, P_{ij}^{1}, … of smaller and smaller sets of paths, which eventually collapses to P_{ij}^{ℓ} = {P_{ij}} when ℓ has risen to ℓ = σ(ij).

More formally, let ℓ^{∗} ≤ \binom{m}{2} be maximal such that, for all 0 ≤ ℓ < ℓ^{∗} and all 1 ≤ i < j ≤ m, there exist sets P_{ij}^{ℓ} satisfying the following five conditions:

(i) P_{ij}^{ℓ} is a non-empty set of disjoint A_{i}–A_{j} paths in B that meet A only in their endpoints.

As soon as a set P_{ij}^{ℓ} is defined, we shall write H_{ij}^{ℓ} := ⋃ P_{ij}^{ℓ} for the union of its paths.

(ii) If σ(ij) < ℓ then P_{ij}^{ℓ} has exactly one element P_{ij}, and P_{ij} does not meet any path belonging to a set P_{st}^{ℓ} with ij ≠ st.

(iii) If σ(ij) = ℓ, then |P_{ij}^{ℓ}| = k/c^{2ℓ}.

(iv) If σ(ij) > ℓ, then |P_{ij}^{ℓ}| = k/c^{2ℓ+1}.

(v) If ℓ = σ(pq) < σ(ij), then for every e ∈ E(H_{ij}^{ℓ}) \ E(H_{pq}^{ℓ}) there are no k/c^{2ℓ+1} disjoint paths from A_{i} to A_{j} in the graph (H_{pq}^{ℓ} ∪ H_{ij}^{ℓ}) − e.

Note that, since σ(ij) < \binom{m}{2} by definition of σ, conditions (iii) and (iv) imply that |P_{ij}^{ℓ}| ≥ c^{2} whenever σ(ij) ≥ ℓ.

Clearly if ℓ^{∗} = \binom{m}{2}, then by (i) and (ii) we have a (subdivided) K_{m} minor with branch sets A_{1}, …, A_{m} in G. Suppose then that ℓ^{∗} < \binom{m}{2}. Let us show that ℓ^{∗} > 0. Let pq := σ^{−1}(0) and put P_{pq}^{0} := P_{pq}. To define P_{ij}^{0} for σ(ij) > 0 put H_{ij} := ⋃ P_{ij}, and let F ⊆ E(H_{ij})\E(H_{pq}^{0}) be maximal such that (H_{pq}^{0}∪H_{ij})−F still contains k/c disjoint paths from A_{i} to A_{j}; then let P_{ij}^{0} be such a set of paths. As any vertex of A on these paths lies in A_{i} ∪ A_{j} (by definition of H_{pq}^{0} and H_{ij}), we may assume that they have no inner vertices in A. Thus our choice of P_{ij}^{0} satisfies (i)–(v).

Having shown that ℓ^{∗} > 0, let us now consider ℓ := ℓ^{∗} − 1. Thus, conditions (i)–(v) are satisfied for ℓ but cannot be satisfied for ℓ + 1. Let pq := σ^{−1}(ℓ). If P_{pq}^{ℓ} contains a path P that avoids a set Q_{ij} of some |P_{ij}^{ℓ}|/c of the paths in P_{ij}^{ℓ} for all ij with σ(ij) > ℓ, then we can define P_{ij}^{ℓ+1} for all ij as before (with a contradiction). Indeed, let st := σ^{−1}(ℓ + 1) and put P_{st}^{ℓ+1} := Q_{st}. For σ(ij) > ℓ + 1 write H_{ij} := ⋃ Q_{ij}, let F ⊆ E(H_{ij}) \ E(H_{st}^{ℓ+1}) be maximal such that (H_{st}^{ℓ+1} ∪ H_{ij}) − F still contains at least |P_{ij}^{ℓ}|/c^{2} disjoint paths from A_{i} to A_{j}, and let P_{ij}^{ℓ+1} be such a set of paths. Setting P_{pq}^{ℓ+1} := {P } and P_{ij}^{ℓ+1} := P_{ij}^{ℓ} = {P_{ij}^{ℓ}} for σ(ij) < ℓ then gives us a family of sets P_{ij}^{ℓ+1} that contradicts the maximality of ℓ^{∗}.

Thus for every path P ∈ P_{pq}^{ℓ} there exists a pair ij with σ(ij) > ℓ such that P avoids fewer than |P_{ij}^{ℓ}|/c of the paths in P_{ij}^{ℓ}. For some ⌈|P_{pq}^{ℓ}|/\binom{m}{2}⌉ of these P that pair ij will be the same; let P denote the set of those P, and keep ij fixed from now on. Note that |P| ≥ |P_{pq}^{ℓ}|/\binom{m}{2} = c |P_{ij}^{ℓ}|/\binom{m}{2} by (iii) and (iv).

Let us use Lemma 6 to find sets V ⊆ P ⊆ P_{pq}^{ℓ} and H ⊆ P_{ij}^{ℓ} such that

|V| ≥ \frac{1}{2}|P| ( ≥ \frac{c}{m^{2}} |P_{ij}^{ℓ}| )
|H| = r^{2}

and every path in V meets every path in H. We have to check that the bipartite graph with vertex sets P and P_{ij}^{ℓ} in which P ∈ P is adjacent to Q ∈ P_{ij}^{ℓ} whenever P ∩ Q = ∅ does not have too many edges. Since every P ∈ P has fewer than |P_{ij}^{ℓ}|/c neighbours (by definition of P), this graph has indeed at most

|P||P_{ij}^{ℓ}|/c ≤ |P||P_{ij}^{ℓ}|/6r^{2}
≤ ⌊|P|/2⌋ |P_{ij}^{ℓ}|/2r^{2}
≤ ⌊|P|/2⌋(|P_{ij}^{ℓ}|/r^{2} − 1)
= (|P| − ⌈|P|/2⌉)(|P_{ij}^{ℓ}| − r^{2})/r^{2}

edges, as required. Hence, V and H exist as claimed.

Pick a path Q ∈ H, and put

d := ⌊\sqrt{c}/m⌋ = ⌊r^{2r+4}/m⌋ ≥ r^{2r+2}.

For n = 1, 2, …, d − 1 let e_{n} be the first edge of Q (on its way from A_{i} to A_{j}) such that the initial component Q_{n} of Q − e_{n} meets at least nd |P_{ij}^{ℓ}| different paths from V, and such that e_{n} is not an edge of H_{pq}^{ℓ}. As any two vertices of Q that lie on different paths from V are separated in Q by an edge not in H_{pq}^{ℓ}, each of these Q_{n} meets exactly nd |P_{ij}^{ℓ}| paths from V. Put Q_{0} := ∅ and Q_{d} := Q. Since |V| ≥ d^{2}|P_{ij}^{ℓ}|, we have thus divided Q into d consecutive disjoint segments Q′_{n} := Q_{n} − Q_{n−1} (n = 1, …, d) each meeting at least d |P_{ij}^{ℓ}| paths from V.

For each n = 1, …, d−1, Menger’s theorem and conditions (iv) and (v) imply that H_{pq}^{ℓ} ∪ H_{ij}^{ℓ} has a set S_{n} of |P_{ij}^{ℓ}| − 1 vertices such that (H_{pq}^{ℓ} ∪ H_{ij}^{ℓ}) − e_{n} − S_{n} contains no path from A_{i} to A_{j}. Let S denote the union of all these sets S_{n}. Then |S| < d |P_{ij}^{ℓ}|, so each Q′_{n} meets at least one path V_{n} ∈ V that avoids S.

Clearly, each S_{n} consists of a choice of exactly one vertex x from every path P ∈ P_{ij}^{ℓ} \ {Q}. Denote the initial component of P − x by P_{n}, put P_{0} := ∅ and P_{d} := P, and let P′_{n} := P_{n} − P_{n−1} for n = 1, …, d. The separation properties of the sets S_{n} now imply that V_{n} ∩ P ⊆ P′_{n} for n = 1, …, d (and hence in particular that P′_{n} ≠ ∅, ie. that P_{n−1} ⊂ P_{n}). Indeed V_{n} cannot meet P_{n−1}, because P_{n−1} ∪ V_{n} ∪ (Q − Q_{n−1}) would then contain an A_{i}–A_{j} path in (H_{pq}^{ℓ} ∪ H_{ij}^{ℓ})−e_{n−1} −S_{n−1}, and likewise (consider S_{n}) V_{n} cannot meet P −P_{n}. Thus for all n = 1, …, d, the path V_{n} meets every path P ∈ H \ {Q} precisely in its nth segment P′_{n}. Applying Lemma 8 to the path systems H \ {Q} and {V_{1}, …, V_{d}} now yields the desired grid minor. □

To conclude, let us remark that our upper bound of r^{4m^{2}(r+2)} ≤ 2^{5r^{5} log r} for the tree-width of a graph without an r × r grid minor is most likely far from best possible. Robertson, Seymour and Thomas [7] obtain an only slightly better bound of about 2^{9r^{5}}, but they suspect that the correct order might be as low as r^{2} log r.

4 Highly connected sets and tangles

The proofs of Theorem 2 given in [7] and [3] rely heavily on a concept central to the Robertson-Seymour theory of minors but not so far considered in this paper, the concept of a tangle introduced in [6]. Both these proofs build on the fact that, if the tree-width of a graph is large, then the graph contains a large tangle, and use the tangle for the construction of a grid minor.

While it is easy to see that graphs with a large tangle must have large treewidth—the proof is similar to our proof of Proposition 3(i), see [6] or [3]—its converse, the direction needed for the proof of Theorem 2 in [7] and [3], is not immediate. However, this direction follows easily from our Proposition 3(ii), and the purpose of this section is to show how.

Let k ≥ 1 be an integer. A tangle of order k in a graph G is a set T of separations of G, each of order < k, that satisfies the following conditions (cf. [6]):

(T1) if (A, B) is any separation of G of order < k, then either (A, B) ∈ T or (B, A) ∈ T ;

(T2) if (A_{1}, B_{1}), (A_{2}, B_{2}), (A_{3}, B_{3}) ∈ T , then A_{1} ∪ A_{2} ∪ A_{3} ≠ G;

(T3) if (A, B) ∈ T , then V (A) ≠ V (G).

As shown in [6, (5.2)], any graph with a tangle of order k has tree-width at least k − 1, and any graph of tree-width at least k − 1 has a tangle of order at least \frac{2}{3}k. Reed [3] gives a simple proof that graphs of tree-width ≥ 3(k − 1) have a tangle of order k; his proof, however, builds on a non-trivial duality theorem for tree-width due to Seymour and Thomas. Trading just a little more quantitative exactness for simplicity of proof, we observe the following corollary to Proposition 3:

Proposition 10 Any graph of tree-width at least 4k has a tangle of order k.

Proof If a graph G has tree-width ≥ 4k then, by Proposition 3(ii), G contains a k-connected set X of size 3k. Let T be the set of all separations (A, B) of order < k in G such that |V (A) ∩ X| ≤ |V (B) ∩ X|. Then |V (A) ∩ X| < k for all (A, B) ∈ T (since X is k-connected in G but |A ∩ B| < k), implying (T2) and (T3). Hence T is a tangle of order k. □

References

[1] R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, Springer 1997.

[2] K.Yu. Gorbunov, Structural properties of context-free grammars, PhD thesis submitted to Moscow State University 1998. For a partial English translation see: An estimate of the tree-width of a graph which has not a given planar grid as a minor, 1998 Workshop on Graph Theoretic Concepts in Computer Science, Springer Lecture Notes in Computer Science, to appear.

[3] B.A. Reed, Tree-width and tangles: a new connectivity measure and some applications, in: R.A. Bailey (ed), Surveys in Combinatorics, Cambridge University Press 1997, pp. 87–162.

[4] N. Robertson & P.D. Seymour, Graph Minors. IV. Tree-width and wellquasi-ordering, J. Combin. Theory B 48 (1990), 227–254.

[5] N. Robertson & P.D. Seymour, Graph Minors. V. Excluding a planar graph, J. Combin. Theory B 41 (1986), 92–114.

[6] N. Robertson & P.D. Seymour, Graph Minors. X. Obstructions to treedecomposition, J. Combin. Theory B 52 (1991), 153–190.

[7] N. Robertson, P.D. Seymour & R. Thomas, Quickly excluding a planar graph, J. Combin. Theory B 62 (1994), 323–348.

[8] C. Thomassen, A simpler proof of the excluded minor theorem for higher surfaces, J. Combin. Theory B 70 (1997), 306–311.

[9] C. Thomassen, Embeddings and minors, in: R.L. Graham, M. Grötschel & L. Lovász (Eds.), Handbook of Combinatorics, Elsevier 1996.