The three-in-a-tree problem

Maria Chudnovsky^{1} and Paul Seymour^{2} Princeton University, Princeton NJ 08544 May 10, 2006; revised April 18, 2011

1This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. 2Supported by ONR grant N00014-01-1-0608, and NSF grant DMS-0070912.

Abstract

We show that there is a polynomial time algorithm that, given three vertices of a graph, tests whether there is an induced subgraph that is a tree, containing the three vertices. (Indeed, there is an explicit construction of the cases when there is no such tree.) As a consequence, we show that there is a polynomial time algorithm to test whether a graph contains a “theta” as an induced subgraph (this was an open question of interest) and an alternative way to test whether a graph contains a “pyramid” (a fundamental step in checking whether a graph is perfect).

1 Introduction

All graphs in this paper are finite and simple. If G is a graph, its vertex- and edge-sets are denoted V (G), E(G). If X ⊆ V (G), the subgraph with vertex set X and edge set all edges of G with both ends in X is denoted G|X, and called the subgraph induced on X.

There are many algorithmic questions of interest concerning the existence of an induced subgraph of some specific type containing some specified vertices, but almost all of them seem to be NPcomplete, by virtue of the following result of Bienstock [1]:

1.1 The following problem is NP-complete: Input: A graph G and two edges e, f of G. Question: Is there a subset X ⊆ V (G) such that G|X is a cycle containing e, f?

Bienstock’s result leaves very little room between the trivial problems and the NP-complete problems, but in this paper we report on a problem that falls into the gap. We call the following the “three-in-a-tree” problem:

Input: A graph G, and three vertices v_{1}, v_{2}, v_{3} of G. Question: Does there exist X ⊆ V (G) with v_{1}, v_{2}, v_{3} ∈ X such that G|X is a tree?

For most graphs one would expect a “yes” answer, but there are interesting graphs for which the answer is “no”; for instance, if e_{1}, e_{2}, e_{3} are edges of a graph H each incident with a vertex of degree one, and G is the line graph of H, then e_{1}, e_{2}, e_{3} are vertices of G and there is no induced tree in G containing e_{1}, e_{2}, e_{3}. Nevertheless, we will show that the three-in-a-tree problem can be solved in time O(|V (G)|^{4}). We shall give an explicit construction of all instances (G, v_{1}, v_{2}, v_{3}) such that the desired tree does not exist, and the proof that all such instances must fall under this construction can be converted to an algorithm to check whether the desired tree exists or not.

2 Thetas, pyramids and prisms

We were led to the three-in-a-tree problem while working on the question of deciding if a graph contains a theta, so let us describe that. First we need some definitions. If G, H are graphs, and H is isomorphic to G|X for some X ⊆ V (G), we say that G contains H as an induced subgraph. A path is a graph P whose vertex set and edge set can be labeled as V (P) = {v_{1}, …, v_{k}} and E(P) = {e_{1}, …, e_{k−1}} for some k ≥ 1, such that e_{i} is incident with v_{i}, v_{i+1} for 1 ≤ i ≤ k − 1. A cycle is a graph C with V (C) = {v_{1}, …, v_{k}} and E(C) = {e_{1}, …, e_{k}} for some k ≥ 3, such that e_{i} is incident with v_{i}, v_{i+1} for 1 ≤ i ≤ k − 1, and e_{k} is incident with v_{1}, v_{k}. The length of a path or cycle is the number of edges in it, and a path or cycle if odd or even if its length is odd or even respectively. A path or cycle of G means a subgraph (not necessarily induced) of G that is a path or cycle. A hole of G means a cycle in G that is an induced subgraph and has length at least four. A triangle is a set of three pairwise adjacent vertices.

Here are three types of graph that will be important to us:

• A pyramid is a graph consisting of a vertex a and a triangle {b_{1}, b_{2}, b_{3}}, and three paths P_{1}, P_{2}, P_{3}, such that: P_{i} is between a and b_{i} for i = 1, 2, 3; for 1 ≤ i < j ≤ 3 P_{i}, P_{j} are vertex-disjoint except for a and the subgraph induced on V (P_{i}) ∪ V (P_{j}) is a cycle; and at most one of P_{1}, P_{2}, P_{3} has only one edge.

• A theta is a graph consisting of two nonadjacent vertices a, b and three paths P_{1}, P_{2}, P_{3}, each joining a, b and otherwise vertex-disjoint, such that for 1 ≤ i < j ≤ 3 the subgraph induced on V (P_{i}) ∪ V (P_{j}) is a cycle.

• A prism is a graph consisting of two vertex-disjoint triangles {a_{1}, a_{2}, a_{3}} and {b_{1}, b_{2}, b_{3}}, and three paths P_{1}, P_{2}, P_{3}, pairwise vertex-disjoint, such that for 1 ≤ i < j ≤ 3 the subgraph induced on V (P_{i}) ∪ V (P_{j}) is a cycle.

Perhaps the main reason for interest in pyramids, thetas and prisms is that every graph containing a pyramid as an induced subgraph has an odd hole, and every graph containing a theta or prism has an even hole; and there seems to be some parallel between pyramids and “thetas or prisms”. Yet although pyramids, thetas and prisms are superficially similar, there is a real difference in the difficulty of detecting their presence. We showed in [3] that

2.1 There is an algorithm with running time O(|V (G)|^{9}), that, with input a graph G, tests whether G contains a pyramid as an induced subgraph.

Motivated by the parallel between pyramids and thetas-or-prisms, Chudnovsky and Kapadia [2, 4] proved the following:

2.2 There is a polynomial-time algorithm to test whether a graph G contains either a theta or a prism as an induced subgraph.

In contrast, Maffray and Trotignon[5] showed that

2.3 It is NP-complete to test whether a graph contains a prism as an induced subgraph.

There are two useful applications of the three-in-a-tree algorithm here. First, until now the complexity of testing whether G contains a theta has been open; but it can be solved in polynomial time as follows.

2.4 There is an algorithm to test if a graph G contains a theta as an induced subgraph, with running time O(|V (G)|^{11}).

Proof. Enumerate all four-tuples (a, b_{1}, b_{2}, b_{3}) of distinct vertices such that a is adjacent to b_{1}, b_{2}, b_{3} and b_{1}, b_{2}, b_{3} are pairwise nonadjacent. For each such four-tuple (a, b_{1}, b_{2}, b_{3}), enumerate all subsets X ⊆ V (G) such that a has no neighbour in X, and b_{1}, b_{2}, b_{3} each have exactly one neighbour in X, and each member of X is adjacent to at least one of b_{1}, b_{2}, b_{3} (it follows that |X| ≤ 3). For each such choice of X, let G′ be obtained from G by deleting a and all vertices adjacent to one of a, b_{1}, b_{2}, b_{3} except for the members of {b_{1}, b_{2}, b_{3}} ∪ X; and test whether there is an induced tree in G′ containing all of b_{1}, b_{2}, b_{3}. Thus we have to run the three-in-a-tree algorithm at most |V (G)|^{7} times, and each one takes time O(|V (G)|^{4}). It is easy to see that there is some choice of a, b_{1}, b_{2}, b_{3} and X such that the tree exists, if and only if G contains a theta.

Second, the algorithm of 2.1 depended heavily on some fortuitous properties of the smallest pyramid in a graph, and this was a little disturbing because testing for a pyramid was a crucial step in our algorithm to test whether a graph is perfect. The three-in-a-tree algorithm can be used to give another, less miraculous, way to test for pyramids, as follows.

2.5 There is an algorithm to test if a graph G contains a pyramid as an induced subgraph, with running time O(|V (G)|^{10}).

Proof. Enumerate all six-tuples (a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}) of distinct vertices such that {b_{1}, b_{2}, b_{3}} is a triangle, and a_{i} is adjacent to b_{j} if and only if i = j (for 1 ≤ i, j ≤ 3). For each such six-tuple, let G′ be obtained from G by deleting all vertices with a neighbour in {b_{1}, b_{2}, b_{3}} except for a_{1}, a_{2}, a_{3}, and test whether there is an induced tree in G′ that contains all of a_{1}, a_{2}, a_{3}. It is easy to see that G contains a pyramid if and only if for some six-tuple there is an induced tree as described.

3 Strip structures

Let G be a connected graph. We say that Z ⊆ V (G) is constricted if |Z ∩V (T)| ≤ 2 for every induced tree T of G. We wish to study which three-vertex subsets of V (G) are constricted; but we might as well study which sets are constricted in general, because that question is no more difficult, and does seem to be strictly more general. We will prove that if |Z| ≥ 2, then Z is constricted if and only if G admits a certain decomposition with respect to Z, that we call an “extended strip decomposition”. Our next goal is to define this; but before we do so, let us motivate the definition a little.

First, let us say a leaf edge of a graph is an edge incident with a vertex of degree one. We observe that for any graph H, with line graph G say, if Z ⊆ E(H) = V (G) and every member of Z is a leaf edge of H, then Z is constricted in G. Our main result is an attempt at a converse of this; that for any graph G, if Z ⊆ V (G) is constricted then G is a sort of modified line graph of a graph H in which the members of Z are the leaf edges.

Second, to see that there is some hope of a converse, let us mention the following “toy” version of our main theorem. (This is essentially a reformulation of 5.1, and we postpone the proof.)

3.1 Let G be a connected graph and let Z ⊆ V (G) be constricted with |Z| ≥ 2. Suppose that there is no proper subset X ⊂ V (G) with Z ⊆ X such that G|X is connected. Then there is a tree H with E(H) = X, such that G is the line graph of H, and Z is the set of leaf edges of H.

Thus, we need to modify 3.1, eliminating the hypothesis about the nonexistence of X, and modifying the conclusion appropriately. It is natural to try changing the conclusion from “there is a tree H...” to “there is a connected graph H...”, but this is not sufficiently general; the graph G might admit a 2-join with all the members of Z on one side, and if so then we do not have much information or control about the other side of the 2-join. Such far sides of 2-joins must be incorporated into the theorem as general pieces of graph about which we know nothing, except we know that they attach to the controlled part of the graph via a 2-join structure. (We call these pieces “strips”).

Now let us define an “extended strip decomposition”. Let G be a graph and Z ⊆ V (G). Let H also be a graph, let W be the set of vertices of H that have degree one in H, and let η be a map with domain the union of E(H) and the set of all pairs (e, v) where e ∈ E(H), v ∈ V (H) and e incident with v, satisfying the following conditions:

• for each edge e ∈ E(H), η(e) ⊆ V (G), and for each v ∈ V (H) incident with e, η(e, v) ⊆ η(e)

• η(e) ∩ η(f) = ∅ for all distinct e, f ∈ E(H)

• for all distinct e, f ∈ E(H), let x ∈ η(e) and y ∈ η(f); then x, y are adjacent in G if and only if e, f share an end-vertex v in H, and x ∈ η(e, v) and y ∈ η(f, v)

• |Z| = |W |, and for each z ∈ Z there is a vertex v ∈ W such that η(e, v) = {z}, where e is the (unique) edge of H incident with v.

Let us call such a map η an H-strip structure in (G, Z). (Thus, we have now incorporated the “far sides of 2-joins”, as discussed above. Unfortunately, this still is not enough, and we need a little more, as follows.) Let η be an H-strip structure, and let us extend the domain of η by adding to it the union of V (H) and the set of all triangles of H, as follows. For each vertex v ∈ V (H), let η(v) ⊆ V (G), and for each triangle D of H let η(D) ⊆ V (G), satisfying the following:

• all the sets η(e) (e ∈ E(H)), η(v) (v ∈ V (H)) and η(D) (for all triangles D of H) are pairwise disjoint, and their union is V (G)

• for each v ∈ V (H), if x ∈ η(v) and y ∈ V (G) \ η(v) are adjacent in G then y ∈ η(e, v) for some e ∈ E(H) incident in H with v

• for each triangle D of H, if x ∈ η(D) and y ∈ V (G) \ η(D) are adjacent in G then y ∈ η(e, u) ∩ η(e, v) for some distinct u, v ∈ D, where e is the edge uv of H.

In this case we say that η is an extended H-strip decomposition of (G, Z). Our main theorem asserts the following:

3.2 Let G be a connected graph and let Z ⊆ V (G) with |Z| ≥ 2. Then Z is constricted if and only if for some graph H, (G, Z) admits an extended H-strip decomposition.

Proof of the “if” half of 3.2.

Suppose that Z is not constricted, and yet (G, Z) admits an extended H-strip-decomposition η. Choose an induced tree T in G with |V (T)∩Z| ≥ 3, with V (T) minimal. It follows that every vertex of T that has degree one in T belongs to Z (for otherwise it could be deleted from T); and since there is such a vertex, and it cannot be deleted from T, it follows that |V (T) ∩ Z| = 3. Now either T is an induced path with both end-vertices in Z (in this case there is a unique vertex of Z ∩ V (T) that is an internal vertex of P, say y) or the three members of Z ∩ V (T) all have degree one in T, and T has a unique vertex y of degree three (and possibly some vertices of degree two). If z ∈ Z ∩ V (T) \ {y}, a path P of T is said to be a z-limb if y ∉ V (P) and z ∈ V (P) (and consequently z is an end-vertex of P, and no other vertex of P belongs to Z).

For each v ∈ V (H), let N(v) denote the union of all the sets η(e, v), as e ranges over all edges of H incident with v.

(1) For each v ∈ V (H), there do not exist distinct z_{1}, z_{2} ∈ Z ∩ V (T) \ {y} such that some z_{1}- limb contains a vertex in N(v) and some z_{2}-limb contains a vertex in N(v).

For suppose this is false; then for i = 1, 2 we may choose a z_{i}-limb Q_{i}, with end-vertices z_{i}, y_{i} say, and v ∈ V (H), such that y_{1}, y_{2} ∈ N(v). Choose Q_{1}, Q_{2}, v so that the sum of the lengths of Q_{1}, Q_{2} is minimum. It follows that for i = 1, 2, no vertex of Q_{i} belongs to N(v) except y_{i}. Since y_{1} is not adjacent to y_{2} (from the definition of z_{1}-, z_{2}-limb) it follows that for some e ∈ E(H), y_{1}, y_{2} ∈ η(e, v). Let e be incident with v, u ∈ V (H) say. Since |η(e, v)| > 1, it follows that not both z_{1}, z_{2} ∈ η(e), so we may assume that z_{1} ∉ η(e). Let R_{1} be a maximal z_{1}-limb such that R_{1} is a subpath of Q_{1} and no vertex of R_{1} belongs to η(e). Let R_{1} have ends r_{1}, z_{1} say; and let s_{1} be the neighbour of r_{1} in Q_{1} that does not belong to R_{1}. Thus s_{1} ∈ η(e). If z_{2} ∉ η(e) define R_{2}, r_{2}, s_{2} similarly. Since r_{1} ∉ η(e), it follows that either r_{1} ∈ η(D) for some triangle D of H, or r_{1} ∈ η(w) for some w ∈ V (H), or r_{1} ∈ η(f) for some f ∈ E(H) \ {e}.

Suppose that the first holds, that is, r_{1} ∈ η(D) for some triangle D of H. Since s_{1} ∈ η(e) and r_{1}, s_{1} are adjacent, it follows that u, v ∈ D, and s_{1} ∈ η(e, u) ∩ η(e, v). Let D = {u, v, w} say. Since z_{1} ∉ η(D), there is an edge ab of R_{1} such that a ∈ η(D) and b ∉ η(D). Consequently b belongs to one of

η(uv, u) ∩ η(uv, v), η(vw, v) ∩ η(vw, w), η(uw, u) ∩ η(uw, w).

But from the choice of R_{1}, b ∉ η(e), and from the choice of Q_{1}, b ∉ N(v). Hence b ∈ η(uw, u) ∩ η(uw, w); but then s_{1} ∈ η(uv, u) and b ∈ η(uw, u), and so s_{1}, b are adjacent, contradicting that T is an induced tree. Thus the first case cannot occur.

Suppose that the second holds, and r_{1} ∈ η(w) for some w ∈ V (H). Since r_{1}, s_{1} are adjacent, it follows that s_{1} ∈ N(w), and so s_{1} ∈ η(f, w) for some edge f incident with w; and since s_{1} ∈ η(e), it follows that f = e, so w is one of u, v. Moreover, since z_{1} ∉ η(w), there is an edge ab of R_{1} such that a ∈ η(w) and b ∉ η(w), and therefore b ∈ N(w). Since b ∉ η(v) it follows that w ≠ v, and so w = u, and hence s_{1} ∈ η(e, u). Moreover, since T is an induced tree it follows that b and s_{1} are not adjacent. Since s_{1}, b ∈ N(u), it follows that b ∈ η(e, u), contrary to the choice of R_{1}. Thus the second case cannot hold.

We deduce that the third holds, and so r_{1} ∈ η(f) for some f ∈ E(H) \ {e}. Since r_{1}, s_{1} are adjacent, it follows that there is a vertex w of H incident with e, f such that s_{1} ∈ η(e, w) and r_{1} ∈ η(f, w). Since r_{1} ∉ N(v), it follows that w = u, and so s_{1} ∈ η(e, u).

In particular, η(e, u) ≠ {z_{2}}, and since η(e, v) ≠ {z_{2}}, it follows that z_{2} ∉ η(e), and so R_{2}, r_{2}, s_{2} are defined. By the same argument with z_{1}, z_{2} exchanged, it follows that s_{2} ∈ η(e, u). Since r_{1} ∈ η(f, u) for some f ∈ E(H) \ {e}, and s_{2} ∈ η(e, u), it follows that r_{1}, s_{2} are adjacent, a contradiction. This proves (1).

Let Z ∩ V (T) = {z_{1}, z_{2}, z_{3}}.

(2) y ∈ η(e) for some e ∈ E(H).

For either y ∈ η(D) for some triangle D of H, or y ∈ η(v) for some v ∈ V (H), or y ∈ η(e) for some e ∈ E(H). Suppose that the first holds. Now for i = 1, 2, 3, z_{i} ∉ η(D); let R_{i} be a maximal z_{i}-limb containing no vertex of η(D), with ends z_{i}, r_{i} say, and r_{i} has a neighbour in η(D). Let D = {u, v, w}; then for i = 1, 2, 3, r_{i} belongs to at least two of N(u), N(v), N(w). Hence one of N(u), N(v), N(w) meets both of R_{1}, R_{2}, contrary to (1). Next suppose the second holds, and y ∈ η(v) for some v ∈ V (H). For i = 1, 2, 3, since z_{i} ∉ η(v), there is a maximal z_{i}-limb R_{i} with no vertex in η(v), with ends z_{i}, r_{i} say, and r_{i} has a neighbour in η(v). Hence r_{1}, r_{2}, r_{3} all belong to N(v), contrary to (1). Thus the third holds, that is, y ∈ η(e) for some e ∈ E(H). This proves (2).

Let e be as in (2). For i = 1, 2, 3, if z_{i} ∉ η(e), let R_{i} be a maximal z_{i}-limb containing no vertex of η(e), with ends z_{i}, r_{i} say, and let r_{i} be adjacent in T to s_{i} ∈ η(e). Let e be incident in H with u, v ∈ V (H).

(3) For i = 1, 2, 3, if z_{i} ∉ η(e), then there exists w ∈ {u, v} and an edge f ∈ E(H) \ {e} incident with w such that r_{i} ∈ η(f, w) and s_{i} ∈ η(e, w).

For either r_{i} ∈ η(D) for some triangle D of H, or r_{i} ∈ η(w) for some w ∈ V (H), or r_{i} ∈ η(f) for some f ∈ E(H) \ {e}. Suppose that the first holds, and r_{i} ∈ η(D). Since s_{i} ∉ η(D), and r_{i}, s_{i} are adjacent, and s_{i} ∈ η(e), it follows that u, v ∈ D, and s_{i} ∈ η(e, u) ∩ η(e, v). Let D = {u, v, w} say. Since z_{i} ∉ η(D), there is an edge ab of R_{i} with a ∈ η(D) and b ∉ η(D). Consequently b belongs to one of

η(uv, u) ∩ η(uv, v), η(vw, v) ∩ η(vw, w), η(uw, u) ∩ η(uw, w).

Since b, s_{i} are nonadjacent, it follows that b ∉ η(uw, u) ∪ η(vw, v), and since b ∉ η(e), this is impossible. Thus the first case cannot occur.

Suppose that the second holds, and r_{i} ∈ η(w) for some w ∈ V (H). Since r_{i}, s_{i} are adjacent, and s_{i} ∈ η(e), it follows that w ∈ {u, v} and s_{i} ∈ η(e, w); and we may assume that w = v. Since z_{i} ∉ η(v), there is an edge ab of R_{i} with a ∈ η(v) and b ∉ η(v). Hence b ∈ N(v), and so b ∈ η(f, v) for some edge f ∈ E(H) incident with v. Since s_{i}, b are nonadjacent, it follows that f = e, contrary to the definition of R_{i}. Thus the second case cannot hold. We deduce that the third holds, and r_{i} ∈ η(f) for some f ∈ E(H) \ {e}. Since r_{i}, s_{i} are adjacent, and s_{i} ∈ η(e), there exists w ∈ V (H) incident with both e, f, such that r_{i} ∈ η(f, w) and s_{i} ∈ η(e, w). Hence w ∈ {u, v}. This proves (3).

Now if none of z_{1}, z_{2}, z_{3} belong to η(e), then by (3), we may assume that r_{i} ∈ η(f, u) and s_{i} ∈ η(e, u) for i = 1, 2, contrary to (1). Thus we may assume that z_{3} ∈ η(e), and therefore we may assume that N(u) = η(e, u) = {z_{3}}. If z_{1}, z_{2} ∉ η(e), then for i = 1, 2, r_{i} ∉ N(u), and so r_{i} ∈ N(v) by (3), contrary to (1). Consequently one of z_{1}, z_{2} ∈ η(e), and so we may assume that N(v) = η(e, v) = {z_{2}}. But then z_{1} ∉ η(e), and yet r_{1} ∉ N(u) ∪ N(v), contrary to (3). This completes the proof.

4 A lemma

In this section we prove a lemma needed for the “only if” half of 3.2. If G′ is a subgraph of a graph G, and C is a subgraph of G \ V (G′), and v ∈ V (G′) has a neighbour in V (C), we say that v is an attachment of C (in G′). A separation of a graph K is a pair (A, B) of subsets of V (K) with union V (K), such that no edge joins a vertex in A \ B and a vertex in B \ A. We call |A ∩ B| the order of the separation. Let W ⊆ V (K). We say that (K, W) is a frame if

• every vertex in W has degree one in K

• |W | ≥ 3

• K is connected

• for every separation (A, B) of K of order at most two with W ⊆ B ≠ V (K), we have that |A ∩ B| = 2 and K|A is a path between the two members of A ∩ B.

If (K, W) is a frame, we see that W is the set of all vertices of K that have degree one. A branch of (K, W) is a path of K with distinct ends, such that both its ends have degree in K different from two, and all its internal vertices have degree two in K. Since (K, W) is a frame, it follows that every branch is an induced subgraph of K, and every edge of K belongs to a unique branch. If v ∈ V (K), δ_{K}(v) or δ(v) denotes the set of all edges of K incident with v.

Let (K, W) be a frame and let F ⊆ E(K). An F -line is a path P in K such that one end of P belongs to W and some edge of P belongs to F. A double F -line is a path P such that both ends of P belong to W and exactly one edge of P belongs to F. We say that F ⊆ E(K) is focused if

• there do not exist three F -lines that are pairwise vertex-disjoint, and

• there do not exist an F -line and a double F -line that are vertex-disjoint.

We need to study which subsets F are focused. We shall prove the following:

4.1 Let (K, W) be a frame and let F ⊆ E(K) be focused. Then either:

1. there exists x ∈ V (K) with F ⊆ δ(x), or

2. |F | = 3 and the three edges of F form a triangle, or

3. there exist x, y ∈ V (K), not in the same branch of K, such that F = δ(x) ∪ δ(y), or

4. there is a branch B of (K, W) with F ⊆ E(B), or

5. there is a branch B of (K, W) with ends x, y such that x ∉ W and F \ E(B) = δ(x) \ E(B) and F ∩ E(B) ⊈ δ(x), or

6. there is a branch B of (K, W) with ends x, y such that x, y ∉ W and F \ E(B) = (δ(x) ∪ δ(y)) \ E(B).

Proof. We proceed by induction on |E(K)|.

(1) We may assume that for every X ⊆ V (K) with |X| ≤ 2, there is an F -line with no vertex in X.

For suppose that X ⊆ V (K) with |X| ≤ 2, and every F -line has a vertex in X. Choose such a set X with |X| minimum. Since all vertices in W have degree one and their neighbours are not in W, we may also choose X with X ∩ W = ∅. If |X| = 2 and the two members of X belong to the same branch, let B_{0} be the path in this branch between the two members of X, and otherwise let B_{0} be the subgraph with vertex set X and no edges. Suppose that there exists f ∈ F \ E(B_{0}) not incident with any member of X. There is no path between f and W in K \ X, from the property of X, and so there is a separation (A, B) of K with A ∩ B = X and W ⊆ B such that both ends of f belong to A. Since f has no end in X, it follows that B ≠ V (K), and so |X| = 2 and K|A is a path between the two members of X; but then this path is B_{0} and contains f, a contradiction. This proves that every member of F either belongs to E(B_{0}) or is incident with a member of X. If |X| ≤ 1 then the first outcome holds, so we may assume that X = {x_{1}, x_{2}} say. For i = 1, 2, let V_{i} be the set of all neighbours of x_{i} that are not in V (B_{0}), let Y_{i} be the set of all y ∈ V_{i} such that the edge yx_{i} belongs to F, and let Z_{i} = V_{i} \ Y_{i}. If one of Y_{1}, Z_{1} is empty, and one of Y_{2}, Z_{2} is empty, then one of the outcomes of the theorem holds; so we may assume that Y_{1}, Z_{1} are both nonempty. Let J = K \ V (B_{0}). Since X ∩ W = ∅, it follows that W ⊆ V (J). If G is a graph and X, Y ⊆ V (G), we denote by κ(G, X, Y) the minimum order of a separation (A, B) of G with X ⊆ A and Y ⊆ B. Since (K, W) is a frame, it follows that

• κ(J, Y_{1}, W) ≥ 1, for otherwise there would be a separation (A, B) of K with A ∩ B = X and V (B_{0}) ⊆ A and Y_{1} ⊆ A, which is impossible since (K, W) is a frame and no branch of (K, W) includes V (B_{0}) ∪ Y_{1}, since Z_{1} ≠ ∅

• κ(J, Z_{1}, W) ≥ 1, similarly

• κ(J, V_{2}, W) ≥ 1; indeed, κ(J, V_{2}, W) = κ(K \ {x_{1}}, V_{2}, W), and therefore is at least two unless |V_{2}| = 1

• κ(J, Y_{1} ∪ Z_{1}, W) ≥ 2, similarly

• κ(J, Y_{1} ∪ V_{2}, W), κ(J, Z_{1} ∪ V_{2}, W) ≥ 2, since no branch of (K, W) includes both V (B_{0}) and one of Y_{1}, Z_{1}

• κ(J, Y_{1} ∪ Z_{1} ∪ V_{2}, W) ≥ 3, since κ(J, Y_{1} ∪ Z_{1} ∪ V_{2}, W) = κ(K, V_{1} ∪ V_{2}, W), and the latter is at least three since no branch of K includes x_{1}, x_{2} and all their neighbours.

From this and Menger’s theorem (applied to the graph obtained from J by adding three new vertices with neighbour sets Y_{1}, Z_{1}, V_{2} respectively, and asking for three vertex-disjoint paths between the three new vertices and W), we deduce that there are three vertex-disjoint paths P_{1}, P_{2}, P_{3} of J, from some y_{1} ∈ Y_{1} to w_{1} ∈ W, from z_{1} ∈ Z_{1} to w_{2} ∈ W, and from v_{2} ∈ V_{2} to w_{3} ∈ W respectively. We may assume that v_{2} is the only vertex of P_{3} in V_{2}. The path w_{1}-P_{1}-y_{1}-x_{1}-z_{1}-P_{2}-w_{2} (with the obvious notation) is a double F -line Q say. Hence the path x_{2}-v_{2}-P_{3}-w_{3} is not an F -line, since F is focused, and so v_{2} ∈ Z_{2}. For y_{2} ∈ Y_{2}, the path y_{2}-x_{2}-v_{2}-P_{3}-w_{3} is an F -line, and therefore is not disjoint from Q; and so Y_{2} ⊆ V (Q); and by a similar argument, every edge of B_{0} in F is incident with x_{1}. Thus if Y_{2} = ∅ then the first outcome of the theorem holds, so we assume that Y_{2} ≠ ∅. Let y_{2} ∈ Y_{2}; then we have seen that y_{2} ∈ V (P_{1}) ∪ V (P_{2}). If y_{2} ∈ V (P_{2}), then the path w_{3}-P_{3}-v_{2}-x_{2}-y_{2}-P_{2}-w_{2} is a double F -line (here the notation y_{2}-P_{2}-w_{2} at the end of this sequence of concatenations means that we take the subpath of P_{2} between y_{2} and w_{2}; we will use this and similar notation repeatedly without further explanation); and this double F -line is vertex-disjoint from the F -line x_{1}-y_{1}-P_{1}-w_{1}, a contradiction. Thus y_{2} ∈ V (P_{1}). If y_{2} ≠ y_{1}, then w_{3}-P_{3}-v_{2}-x_{2}-y_{2}-P_{1}-w_{1} is a double F -line vertex-disjoint from the F -line y_{1}-x_{1}-z_{1}-P_{2}-w_{2}, a contradiction; and so y_{2} = y_{1}. This proves that Y_{2} = {y_{1}}. Since Y_{2}, Z_{2} ≠ ∅, this restores the symmetry between x_{1}, x_{2}, and so it follows that Y_{1} = {y_{1}}, and every edge of B_{0} in F is incident with x_{2} (as well as with x_{1}). If no edge of B_{0} belongs to F, then every edge in F is incident with y_{1}, contrary to the minimality of X; so F ∩ E(B_{0}) ≠ ∅, and therefore B_{0} is a path of length one, and the second outcome holds. This proves (1).

Henceforth, therefore, we make the assumption of (1), and will obtain a contradiction.

(2) K is not a tree.

For suppose K is a tree. It follows that for any set C of trees of K, either there are k members of C pairwise vertex-disjoint, or there is a set X ⊆ V (K) with |X| < k meeting every member of C. Since there do not exist three pairwise disjoint F -lines, we deduce (by taking C to be the set of all F -lines, and k = 3) that there exists X ⊆ V (K) with |X| ≤ 2, such that every F -line contains a member of X. But this contradicts (1), and so proves (2).

(3) There is a branch B of (K, W) such that, if K′ denotes the graph obtained from K by deleting the edges and internal vertices of B, then (K′, W) is a frame.

For let T be a minimal connected subgraph of K with W ⊆ V (T); then T is a tree, and it is easy to see that (T, W) is a frame. Since K is not a tree, it follows that T ≠ K, and so there is a frame (K′, W) with K′ a proper subgraph of K. Choose such a frame with as many branches as possible. Suppose that there exist u, v ∈ V (K′) that are joined by a path P of K such that no edges or internal vertices of P belong to K′, such that u, v are not in the same branch of (K′, W). It follows that (K′ ∪ P, W) is a frame, and from our choice of (K′, W), we deduce that K′ ∪ P = K. But then P is a branch of (K, W), and (2) holds taking B = P. We may therefore assume that for every two vertices u, v that are joined by a path with no edges or internal vertices in K′, some branch of (K′, W) contains u, v. In particular every edge of K that does not belong to E(K′) but has both ends in V (K′) is between two vertices in the same branch. For any component C of K \ V (K′), we have seen that every two attachments of C belong to the same branch. If for every such C there is a branch of (K′, W) that contains every attachment of C, this contradicts that (K, W) is a frame. Thus there is a component C of K \ V (K′) such that no branch of (K′, W) contains all attachments of C. In particular C has at least two attachments, and every two of them belong to a branch; let B_{1} be a branch, with ends x_{2}, x_{3}, containing at least two attachments v_{2}, v_{3} of C. Let v_{1} be an attachment of C that is not in B_{1}. Since some branch B_{2} contains v_{1}, v_{3}, it follows that v_{3} is one of x_{2}, x_{3}, say v_{3} = x_{3}, and B_{2} has ends x_{1}, x_{3} say. Similarly there is a branch B_{3} containing v_{1}, v_{2}; so v_{2} = x_{2}, and v_{1} is a common end of B_{2}, B_{3}. Since v_{1}, v_{2}, v_{3} are attachments of C, we may choose a vertex c of C and three paths P_{1}, P_{2}, P_{3} from c to v_{1}, v_{2}, v_{3} respectively, pairwise vertex-disjoint except for c, such that V (P_{i}) ⊆ V (C) ∪ {v_{i}}. But then if K′′ denotes the graph obtained from K′ by deleting the edges and internal vertices of B_{1}, and adding P_{1} ∪ P_{2} ∪ P_{3}, then (K′′, W) is a frame, and K′′ ≠ K, since the edges of B_{1} do not belong to K′′, contrary to the choice of K′. This proves (3).

Henceforth, let B, K′ be as in (3). Let the ends of B be x_{1}, x_{2}. Let F′ = F ∩ E(K′).

(4) There does not exist v ∈ V (K′) such that F′ ⊆ δ_{K′}(v).

For suppose that v has this property. Let Y be the set of neighbours y of v in K such that the edge vy belongs to F. By (1) there is an F -line disjoint from {x_{1}, x_{2}}, and in particular, v ∉ V (B), and Y ⊈ V (B). Since (K, W) is a frame, there are three paths P_{1}, P_{2}, P_{3} from x_{1}, x_{2}, v respectively to W, pairwise vertex-disjoint. Consequently P_{3}, B are vertex-disjoint. For i = 1, 2, 3 let w_{i} be the end of P_{i} in W. By (1), no vertex of B meets every edge in E(B) ∩ F (since otherwise this vertex together with v would meet every edge in F), and so there are two disjoint edges in E(B) ∩ F, and therefore there are two vertex-disjoint F -lines Q_{1}, Q_{2}, both subpaths of P_{1} ∪ B ∪ P_{2}. Hence P_{3} is not an F -line, and for each y ∈ Y \ V (B), y-v-P_{3}-w_{3} is not disjoint from both Q_{1}, Q_{2}, since y-v-P_{3}-w_{3} includes an F -line. In particular, Y ⊆ V (P_{1} ∪ B ∪ P_{2}). We have already seen that there exists y ∈ Y \ V (B), and we may therefore assume that y ∈ V (P_{1}) \ {x_{1}}. The path w_{3}-P_{3}-v-y-P_{1}-w_{1} is a double F -line, and it is disjoint from the F -line B ∪ P_{2}, a contradiction. This proves (4).

(5) It is not the case that |F′| = 3, and the three edges in F′ form a triangle.

For suppose there is a triangle {v_{1}, v_{2}, v_{3}} of K′ such that F′ consists of the three edges v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{1}. (Possibly v_{1}, v_{2}, v_{3}, x_{1}, x_{2} are not all distinct.) By (1) (applied to {v_{1}, v_{2}}) there is an edge of B in F. For any M ⊆ {v_{1}, v_{2}, v_{3}, x_{1}, x_{2}} with |M| = 3, there is no branch of (K, W) including all members of M, and so, since (K, W) is a frame, there exist three vertex-disjoint paths in K between M and W. Consequently there are three vertex-disjoint paths P_{1}, P_{2}, P_{3} from {v_{1}, v_{2}, v_{3}, x_{1}, x_{2}} to W, such that at least one of them has first vertex in {x_{1}, x_{2}}, and at least two of them have first vertex in {v_{1}, v_{2}, v_{3}}. Choose three such paths P_{1}, P_{2}, P_{3} with minimal union, and let P_{i} be between u_{i} and w_{i} ∈ W say. We may assume that u_{1} = x_{1}, u_{2} = v_{2} and u_{3} = v_{3}. Moreover, from the minimality of P_{1} ∪ P_{2} ∪ P_{3}, v_{1} is not a vertex of P_{2} ∪ P_{3}, and x_{2} is not a vertex of P_{1}. Hence B is not a path of any of P_{1}, P_{2}, P_{3}. The path w_{2}-P_{2}-v_{2}-v_{3}-P_{3}-w_{3} is a double F -line, disjoint from P_{1} ∪B \{x_{2}}; so the latter is not an F -line. But some edge of B is in F, and so the edge of B incident with x_{2} is the unique edge of B in F. Since the F -line B ∪ P_{1} is not disjoint from the double F -line w_{2}-P_{2}-v_{2}-v_{3}-P_{3}-w_{3}, it follows that x_{2} belongs to one of P_{2}, P_{3}, say P_{2}. The double F -line w_{1}-P_{1}-x_{1}-B-x_{2}-P_{2}-w_{2} is not vertex-disjoint from the F -line v_{2}-v_{3}-P_{3}-w_{3}, so v_{2} = x_{2}. But then every edge in F is incident with one of v_{2}, v_{3}, contrary to (1). This proves (5).

(6) There do not exist two vertices x_{3}, x_{4} ∈ V (K′) such that F′ = δ_{K′}(x_{3}) ∪ δ_{K′}(x_{4}).

For suppose such x_{3}, x_{4} exist. By (1) (applied to {x_{3}, x_{4}}) there is an edge f of B in F and incident with neither of x_{3}, x_{4}. Also by (1) {x_{1}, x_{2}} ≠ {x_{3}, x_{4}}, so there are three pairwise vertex-disjoint paths P_{2}, P_{3}, P_{4} from {x_{1}, x_{2}, x_{3}, x_{4}} to W, where P_{i} is from u_{i} ∈ {x_{1}, x_{2}, x_{3}, x_{4}} to w_{i} ∈ W, and u_{3} = x_{3}, u_{4} = x_{4}, and u_{2} ∈ {x_{1}, x_{2}}. Choose such paths with P_{2} minimal; then we may assume that u_{2} = x_{2}, and x_{1} ∉ V (P_{2}). Hence B is not a path of any of P_{2}, P_{3}, P_{4}. Moreover, P_{3}, P_{4} are disjoint F -lines, and P_{2} ∪ B \ {x_{1}} is disjoint from both of them; so the latter is not an F -line. Hence f is incident with x_{1}, and therefore x_{1} ≠ x_{3}, x_{4}, and so x_{1}, …, x_{4} are all distinct. Since P_{2} ∪ B is an F -line, it meets one of P_{3}, P_{4}, and so x_{1} ∈ V (P_{3}) ∪ V (P_{4}), and we may assume that x_{1} ∈ V (P_{3}) say. But then the double F -line w_{2}-P_{2}-x_{2}-B-x_{1}-P_{3}-w_{3} is disjoint from the F -line P_{4}, a contradiction. This proves (6).

(7) There is no branch B′ of (K′, W) such that F′ ⊆ E(B′).

For suppose that B′ is such a branch, with ends x_{3}, x_{4}. First suppose that one of x_{1}, x_{2}, say x_{1}, belongs to V (B′). Since (K, W) is a frame, it follows that x_{2} ∉ V (B′), and there are three paths P_{i} of K from x_{i} to w_{i} ∈ W for i = 2, 3, 4, pairwise vertex-disjoint. Consequently P 2, P 3, P 4 contain no edges of B or of B′. For i = 3, 4, let Q_{i} be the subpath of B′ between x_{1} and x_{i}, and let Q_{2} = B. Now F ⊆ E(Q_{2})∪E(Q_{3})∪E(Q_{4}). By (1), not every edge in F is incident with x_{1}, so we may assume that P_{i} ∪ Q_{i} \ {x_{1}} is an F -line for some i ∈ {2, 3, 4}. Let {i, j, k} = {2, 3, 4}. Consequently there do not exist two vertex-disjoint F -lines in P_{j} ∪ Q_{j} ∪ Q_{k} ∪ P_{k}, and so there are at most two edges in F ∩ E(Q_{j} ∪ Q_{k}), and if there are two then they have a common end. By (1) (applied to {x_{1}, x_{i}}) at least one edge of Q_{j} ∪ Q_{k} is in F, and if there is only one then P_{j} ∪ Q_{j} ∪ Q_{k} ∪ P_{k} is a double F -line, disjoint from the F -line P_{i} ∪ Q_{i} \ {x_{1}}, a contradiction. Hence exactly two edges of Q_{j} ∪ Q_{k} belong to F, and they have a common end y_{j} ∈ V (Q_{j}) say. By (1) applied to {x_{1}, x_{i}} it follows that y_{j} ≠ x_{1}, so y_{j} is an internal vertex of Q_{j}, and in particular F ∩ E(Q_{k}) = ∅, and F ∩ E(Q_{j}) = δ(y_{j}). Then P_{j} ∪ Q_{j} \ {x_{1}} is an F -line, and so by the same argument there is an internal vertex y_{i} of Q_{i} such that F ∩ E(Q_{i}) = δ(y_{i}). But this contradicts (1) (applied to {y_{i}, y_{j}}). This completes the proof of (7) in the case when one of x_{1}, x_{2} belongs to B′.

Thus we may assume that B, B′ are vertex-disjoint. There is symmetry between B and B′ (for we will not use any more that (K′, W) is a frame). By two applications of (1), both of B, B′ contain an edge in F. There are three vertex-disjoint paths between {x_{1}, …, x_{4}} and W, and we may assume that none of them has an internal vertex in {x_{1}, …, x_{4}}; and from the symmetry we may assume that these paths are P_{1}, P_{2}, P_{3}, where P_{i} is between x_{i} and w_{i} ∈ W. Now P_{3} ∪ B′ is an F -line, and so P_{1}∪B∪P_{2} is not a double F -line and does not include two disjoint F -lines; so there is an internal vertex y of B such that F ∩E(B) = δ(y). There are three disjoint paths Q_{2}, Q_{3}, Q_{4} from {x_{1}, …, x_{4}} to W, such that for i = 3, 4, Q_{i} has first vertex x_{i}; choose them with Q_{2} minimal, then we may assume that Q_{2} has first vertex x_{2} and x_{1} ∉ V (Q_{2}) (possibly x_{1} ∈ V (Q_{3} ∪ Q_{4})). The path y-B-x_{2}-Q_{2}-w′_{2} (where Q_{2} is from x_{2} to w′_{2} ∈ W) is an F -line, disjoint from the path Q_{3} ∪ B′ ∪ Q_{4}; so the latter is not a double F -line, and does not include two disjoint F -lines. Hence there is an internal vertex y′ of B′ such that F ∩E(B′) = δ(y′); but this contradicts (1) (applied to {y, y′}). This proves (7).

(8) There is no branch B′ of (K′, W) with ends x_{3}, x_{4}, such that F′ \ E(B′) = δ_{K′}(x_{3}).

For suppose B′ is such a branch. Again there are two cases depending whether B, B′ are vertexdisjoint or not. First suppose that x_{1} ∈ V (B′) say, and as in (7) we may choose three paths P_{i} of K from x_{i} to w_{i} ∈ W for i = 2, 3, 4, pairwise vertex-disjoint. For i = 3, 4, let Q_{i} be the subpath of B′ between x_{1} and x_{i}, and let Q_{2} = B. Suppose that x_{1} = x_{3}. By (1) (applied to {x_{2}, x_{3}}), there is an edge of B′\{x_{3}} in F, and similarly an edge of B\{x_{3}} in F. But then P_{2}∪Q_{2}\{x_{3}}, P_{3}, P_{4}∪Q_{4}\{x_{3}} are three disjoint F -lines, a contradiction. Thus x_{1} ≠ x_{3}. By (1) (applied to {x_{1}, x_{3}}), at least one edge of Q_{2} ∪ Q_{4} is in F and not incident with x_{1}. Since P_{3} is an F -line, the path P_{2} ∪ Q_{2} ∪ Q_{4} ∪ P_{4} is not a double F -line, and does not include two disjoint F -lines; so exactly two edges of Q_{2} ∪Q_{4} belong to F and they have a common end y ≠ x_{1}. From the symmetry we may assume that y belongs to the interior of Q_{2} say, and so F ∩ E(Q_{4}) = ∅. By (1) (applied to {x_{3}, y}) there is an edge of Q_{3} \ {x_{3}} in F; but then P_{2} ∪ Q_{2} \ {x_{1}}, P_{3}, P_{4} ∪ Q_{4} ∪ Q_{3} \ {x_{3}} are three vertex-disjoint F -lines, a contradiction. This proves (8) in the case that B, B′ are not disjoint.

We may therefore assume that B, B′ are disjoint. By (1) (applied to {x_{3}, x_{4}}) at least one edge of B is in F. By (4) at least one edge of B′ \ {x_{3}} belongs to F. There are three vertex-disjoint paths P_{2}, P_{3}, P_{4} from {x_{1}, …, x_{4}} to W, such that for i = 3, 4, P_{i} is from x_{i} to w_{i} ∈ W say. We may assume that P_{2} is from x_{2} to w_{2}, and x_{1} ∉ V (P_{2}) (possibly x_{1} ∈ V (P_{3} ∪ P_{4})). Thus P_{3}, P_{4} ∪ B′ \ {x_{3}} are disjoint F -lines, and so P_{2} ∪ B \ {x_{1}} is not an F -line; and therefore the edge of B incident with x_{1} is the unique edge of B in F. Since B ∪ P_{2} is an F -line, it follows that x_{1} belongs to one of P_{3}, P_{4}. If x_{1} ∈ V (P_{3}), then w_{2}-P_{2}-x_{2}-B-x_{1}-P_{3}-w_{3} is a double F -line, and B′ ∪ P_{4} is an F -line, and they are disjoint, a contradiction. If x_{1} ∈ V (P_{4}), then w_{2}-P_{2}-x_{2}-B-x_{1}-P_{4}-w_{4} is a double F -line, and P_{3} is an X-line, and they are disjoint, a contradiction. This proves (8).

(9) There is no branch B′ of (K′, W) with ends x_{3}, x_{4}, such that F′ \ E(B′) = δ_{K′}(x_{3}) ∪ δ_{K′}(x_{4}).

For suppose that B′ is such a branch. Again there are two cases depending whether B, B′ are vertex-disjoint or not. First suppose that x_{1} ∈ V (B′) say, and as in (7) we may choose three paths P_{i} of K from x_{i} to w_{i} ∈ W for i = 2, 3, 4, pairwise vertex-disjoint. For i = 3, 4, let Q_{i} be the subpath of B′ between x_{1} and x_{i}, and let Q_{2} = B. Thus P_{3}, P_{4} are F -lines. Suppose that x_{1} = x_{3}. Then from (1) (applied to {x_{3}, x_{4}}) there is an edge of Q_{2} \ {x_{3}} in F, and so P_{2} ∪ Q_{2} \ {x_{3}} is an F -line disjoint from P_{3}, P_{4}, a contradiction. Thus x_{1} ≠ x_{3}, and similarly x_{1} ≠ x_{4}. By (1) (applied to {x_{3}, x_{4}}) there is an edge of F in Q_{2} ∪ Q_{3} ∪ Q_{4} not incident with either of x_{3}, x_{4}; but hence there is an F -line in P_{2} ∪ Q_{2} ∪ Q_{3} ∪ Q_{4} \ {x_{3}, x_{4}}, and it is disjoint from P_{3}, P_{4}, a contradiction. This proves (9) in the case that B, B′ are not disjoint.

Thus we may assume that B, B′ are disjoint. By (1) (applied to {x_{3}, x_{4}}) at least one edge of B is in F. There are three vertex-disjoint paths P_{2}, P_{3}, P_{4} from {x_{1}, …, x_{4}} to W, such that for i = 3, 4, P_{i} is from x_{i} to w_{i} ∈ W say. We may assume that P_{2} is from x_{2} to w_{2}, and x_{1} ∉ V (P_{2}) (possibly x_{1} ∈ V (P_{3} ∪ P_{4})). Thus P_{3}, P_{4} are disjoint F -lines, and so P_{2} ∪ B \ {x_{1}} is not an F -line; and therefore the edge of B incident with x_{1} is the unique edge of B in F. Since B ∪ P_{2} is an F -line, it follows that x_{1} belongs to one of P_{3}, P_{4}, and we may assume it belongs to P_{3} from the symmetry. Then w_{2}-P_{2}-x_{2}-B-x_{1}-P_{3}-w_{3} is a double F -line, and P_{4} is an F -line, and they are disjoint, a contradiction. This proves (9).

But (4)–(9) are contrary to the inductive hypothesis applied to the frame (K′, W). This proves that our assumption of (1) was false, and so proves 4.1.

5 The main proof

In this section we prove the “only if” half of 3.2. We need to show that if G is a connected graph and Z ⊆ V (G) with |Z| ≥ 2 is constricted, then (G, Z) admits an extended H-strip decomposition for some graph H. The result is trivial if |Z| = 2, so we may assume that |Z| ≥ 3. Therefore, throughout this section we assume that G is a connected graph, Z ⊆ V (G) with |Z| ≥ 3, and Z is constricted in G. We shall prove a series of lemmas about the pair (G, Z).

Let (K, W) be a frame. We say it is a frame for (G, Z) if E(K) ⊆ V (G), and

• for all distinct e, f ∈ E(K), e, f have a common end in K if and only if e, f ∈ V (G) are adjacent in G

• Z is the set of edges of K incident with a vertex in W.

We begin with:

5.1 There is a frame for (G, Z).

Proof. Since G is connected, we may choose X ⊆ V (G) with Z ⊆ X, minimal such that G|X is connected.

(1) For each v ∈ X \ Z, G|(X \ {v}) has exactly two components, and they both contain at least one vertex of Z.

For G|(X \ {v}) is not connected, from the minimality of X. Let its components be C_{1}, …, C_{k} say where k ≥ 2. If C_{i} ∩ Z = ∅, let X′ = X \ V (C_{i}); then G|X′ is connected and Z ⊆ X′, contrary to the minimality of X. Thus each C_{i} contains at least one vertex of Z. Suppose that k ≥ 3, and choose z_{i} ∈ V (C_{i}) ∩ Z for i = 1, 2, 3. Since G|X is connected, there are paths P_{1}, P_{2}, P_{3} of G|X between v and z_{1}, z_{2}, z_{3} respectively, with V (P_{i}) ⊆ C_{i} ∪{v}, and if we choose P_{1}, P_{2}, P_{3} with minimal union then their union is an induced tree of G, containing three members of Z, contradicting that Z is constricted in G. This proves (1).

For each v ∈ X \ Z, let A_{v}, B_{v} be the vertex sets of the two components of G|(X \ {v}).

(2) For each v ∈ X \ Z, the set of neighbours of v in A_{v} is a clique, and so is the the set of neighbours of v in B_{v}.

For suppose that u_{1}, u_{2} ∈ A_{v} are nonadjacent, and are both adjacent to v. Choose z_{3} ∈ B_{v} ∩ Z, and let P_{3} be an induced path between v and z_{3} with vertex set in B_{v} ∪ {v}. From the minimality of X, for i = 1, 2 there exists z_{i} ∈ Z such that every path of G|X between v and z_{i} contains u_{i}; let P_{i} be some such path, induced. Consequently u_{1} ∉ V (P_{2}), since P_{2} is induced and u_{2} ∈ V (P_{2}), and similarly u_{2} ∉ V (P_{1}). Hence z_{1} ≠ z_{2}, and V (P_{1}), V (P_{2}) ⊆ A_{v} ∪ {v}. Since every path of G|X between v and z_{1} contains u_{1}, it follows that V (P_{1}) \ {v, u_{1}} is disjoint from V (P_{2}) \ {v}, and there is no edge between these two sets. Similarly there is no edge between V (P_{1}) \ {v} and V (P_{2}) \ {v, u_{2}}; and therefore there is no edge between V (P_{1}) \ {v} and V (P_{2}) \ {v}, since u_{1}, u_{2} are nonadjacent. Hence P_{1} ∪ P_{2} ∪ P_{3} is an induced tree in G, contradicting that Z is constricted. This proves (2).

(3) For each z ∈ Z, the set of neighbours of z in X \ {z} is a clique.

The proof is similar to that of (2). Suppose that u_{1}, u_{2} ∈ X \ {z} are nonadjacent, and both adjacent to z. From the minimality of X, there exist z_{i} ∈ Z such that every path of G|X between z and z_{i} contains u_{i}; let P_{i} be such a path, induced, for i = 1, 2. Then z_{1}, z_{2} ≠ z, and as in (2), there are no edges between V (P_{1}) \ {z} and V (P_{2}) \ {z}. But then P_{1} ∪ P_{2} is an induced tree containing z, z_{1}, z_{2}, a contradiction. This proves (3).

From (2) and (3) it follows that G|X is the line graph of a tree K; thus E(K) = X, and for x, y ∈ X, x, y are adjacent in G if and only if some vertex of K is incident with them both. Let W be the set of vertices of K that have degree one in K. By (3), every z ∈ Z is incident in K with a member of W. Moreover, if x ∈ E(K) is incident with a member of W, and x ∉ Z, then one of A_{x}, B_{x} is empty, which is impossible; so Z is equal to the set of edges of K incident with members of W. But then (K, W) is a frame for (G, Z). This proves 5.1.

Let η be an H-strip structure in (G, Z). If e ∈ E(H) with ends u, v, an e-rung of η means an induced path G|η(e) with vertices p_{1}, …, p_{k} in order, where for 1 ≤ i ≤ k, p_{i} ∈ η(e, u) if and only if i = 1, and p_{i} ∈ η(e, v) if and only if i = k. (Possibly k = 1.) An H-strip structure η in (G, Z) is said to be connected if for every e ∈ E(H), η(e) is nonempty, and η(e) is the union of the vertex sets of the e-rungs of η.

5.2 There is a graph H with the following properties, where W denotes the set of vertices of H of degree one:

• (H, W) is a frame

• no vertex of H has degree two

• there is a connected H-strip structure in (G, Z)

• subject to these three conditions, |E(H)| is maximum.

Proof. By 5.1, there is a frame (K, W) for (G, Z). Let W_{2} be the set of vertices of K that have degree two, and let W_{3} be the set that have degree at least three; thus W, W_{2}, W_{3} are pairwise disjoint and have union V (K). Let H be the graph with vertex set W ∪ W_{3}, in which vertices u, v are adjacent if there is a branch of K with ends u, v. Hence for each edge e ∈ E(H) there is a branch B_{e} of K with the same ends as e. Thus (H, W) is a frame (though no longer a frame for (G, Z), in general), and no vertex of H has degree two. Define η as follows:

• for each e ∈ E(H), η(e) = E(B_{e}) ⊆ V (G)

• for each e ∈ E(H) incident with v ∈ V (H), η(e, v) = {f} where f ∈ E(B_{e}) ⊆ V (G) is the edge of B_{e} incident with v.

It follows that η is a connected H-strip structure in (G, Z). Thus the first three conditions of the theorem are satisfied. Since the sets η(e) (e ∈ E(H)) are nonempty (since η is connected) and pairwise disjoint, it follows that |E(H)| ≤ |V (G)| for every choice of H satisfying the first three conditions above, and therefore the fourth can also be satisfied. This proves 5.2.

Henceforth in the section, H, W will be as in 5.2. Moreover, η will be a connected H-strip structure in (G, Z), chosen with ∪η maximal, where ∪η denotes the union of all the sets η(e) (e ∈ E(H)). For each e = uv ∈ E(H), define M(e) = η(e, u) ∩ η(e, v). For each v ∈ V (H), define

N(v) = ⋃_{e∈δ_{H}(v)} η(e, v),

and for every triangle D = {v_{1}, v_{2}, v_{3}} of H, define

N(D) = M(v_{1}v_{2}) ∪ M(v_{2}v_{3}) ∪ M(v_{3}v_{1}).

5.3 Let p ∈ V (G) \ ∪η, and let Y denote the set of all neighbours of p in ∪η. Then either

• there is an edge e of H such that Y ⊆ η(e), or

• there is a vertex v of H such that Y ⊆ N(v), or

• there is a triangle D of H such that Y ⊆ N(D).

Proof.

(1) For each e ∈ E(H), let R_{e} be an e-rung. Let R be the union of all the sets V (R_{e}) (e ∈ E(H)). Then one of the following holds:

• there exists e ∈ E(H) with Y ∩ R ⊆ V (R_{e}), or

• there exists v ∈ V (H) such that Y ∩ R ⊆ N(v), or

• there is a triangle {u, v, w} of H such that R_{uv}, R_{vw}, R_{wu} all have length zero, and Y ∩ R = V (R_{uv}) ∪ V (R_{vw}) ∪ V (R_{wu}), or

• there exists e = uv ∈ E(H) such that u ∉ W and Y ∩ (R \ V (R_{e})) = N(u) ∩ (R \ V (R_{e})) and Y ∩ V (R_{e}) ⊈ N(u), or

• there exists e = uv ∈ E(H) such that u, v ∉ W and Y ∩ (R \ V (R_{e})) = (N(u) ∪ N(v)) ∩ (R \ V (R_{e})).

For let K be obtained from H by replacing each edge e ∈ E(H) by a path with edges the vertices of R_{e} in order, in the natural way, so that G|R is the line graph of K. Thus (K, W) is a frame for (G, Z). Let F = R ∩ Y; then F ⊆ E(K). Moreover, F is focused, since Z is constricted in G. Hence one of the six outcomes of 4.1 holds. If 4.1.3 holds and x, y are as in 4.1.3, then there is a frame (K′, W) for G, where K′ is obtained from K by adding p to K as a new edge incident with x, y, contrary to the maximality of |E(H)|. If 4.1.1 holds, then the second outcome of (1) holds. Similarly if one of 4.1.2, 4.1.4, 4.1.5, 4.1.6 holds then respectively the third, first, fourth and fifth outcome of (1) holds. This proves (1).

(2) If there is an edge e = v_{1}v_{2} of H such that Y ⊆ η(e) ∪ N(v_{1}) ∪ N(v_{2}) then the theorem holds.

Suppose there is such an edge e = v_{1}v_{2}. For each f ∈ E(H) choose an f-rung R_{f}. For i = 1, 2, let E_{i} be the set of all edges of H that are incident with v_{i} and different from e; thus |E_{i}| ≠ 1. Let A_{i} be the set of all f ∈ E_{i} such that Y contains the end of R_{f} in N(v_{i}), and let B_{i} = E_{i} \ A_{i}.

Suppose first that Y ∩ N(v_{2}) ⊆ η(e). If also Y ∩ N(v_{1}) ⊆ η(e) then Y ⊆ η(e) and the theorem holds, so we may assume that Y ∩N(v_{1}) ⊈ η(e). Moreover, we may assume that Y ∩η(e) ⊈ N(v_{1}), for otherwise Y ⊆ N(v_{1}) and the theorem holds. Hence we may choose the rungs R_{f} (f ∈ E(H)) such that there exists a_{1} ∈ A_{1} and Y ∩V (R_{e}) ⊈ N(v_{1}). By (1), it follows routinely that B_{1} = ∅. Since this holds for all choices of R_{f} (f ≠ a_{1}, e), we deduce that Y ∩ η(f) = η(f, v_{1}) for all f ∈ E(H) \ {a_{1}, e} incident with v_{1}. Since |E_{1}| ≠ 1, it follows by exchanging the roles of a_{1} and some other member of E_{1} that Y ∩ η(a_{1}) = η(a_{1}, v_{1}), and so N(v_{1}) \ η(e) = Y \ η(e). But then a can be added to η(e) and to η(e, v_{1}), contrary to the maximality of ∪η. Thus we may assume that Y ∩ N(v_{2}) ⊈ η(e), and similarly Y ∩ N(v_{1}) ⊈ η(e). Hence we may choose the R_{f} (f ∈ E(H)) such that A_{1}, A_{2} are both nonempty.

Suppose that there is a choice of the R_{f} (f ∈ E(H)) such that for some a_{1} ∈ A_{1} and a_{2} ∈ A_{2}, either a_{1}, a_{2} are disjoint edges of H, or not both R_{a_{1}}, R_{a_{2}} have length zero. By (1), B_{1}, B_{2} are both empty. Since this holds for all choices of R_{f} (f ≠ a_{1}, a_{2}), we deduce that Y ∩ η(f) = η(f, v_{i}) for i = 1, 2 and for all f ∈ E(G) \ {e, a_{1}, a_{2}} incident with v_{i}. Now there exist a′_{1} ∈ A_{1} and a′_{2} ∈ A_{2} such that a′_{1} ≠ a_{1} and a′_{1}, a′_{2} are disjoint edges of H, since |E_{1}|, |E_{2}| ≥ 2 (possibly a′_{2} = a_{2}). We have seen that we can choose R_{a′_{1}}, R_{a′_{2}} such that they both meet Y, and so by the same argument with a_{1}, a_{2} replaced by a′_{1}, a′_{2}, it follows that Y ∩ η(a_{1}) = η(a_{1}, v_{1}), and so N(v_{i}) \ η(e) ⊆ Y for i = 1, and also for i = 2 by the symmetry. But then a can be added to η(e), η(e, v_{1}) and η(e, v_{2}), contrary to the maximality of ∪η.

Hence for every choice of the R_{f} (f ∈ E(H)) with A_{1}, A_{2} both nonempty, we have that |A_{1}| = |A_{2}| = 1, say A_{i} = {a_{i}} for i = 1, 2, and R_{a_{1}}, R_{a_{2}} both have length zero, and a_{1}, a_{2} have a common end w in H. Take some such choice of the R_{f} (f ∈ E(H)). For f ∈ B_{1}, we deduce that we cannot replace R_{f} with some other f-rung that meets Y, and therefore Y ∩ (N(v_{1}) \ η(e)) ⊆ η(a_{1}, v_{1}). Moreover, there is no a_{1}-rung that meets Y with length greater than zero, and so Y ∩η(a_{1}) ⊆ η(a_{1}, v_{1})∩η(a_{1}, w). Similarly Y ∩ (N(v_{2}) \ η(e)) ⊆ η(a_{2}, v_{2}), and Y ∩ η(a_{2}) ⊆ η(a_{2}, v_{2}) ∩ η(a_{2}, w). We may assume that Y ⊈ N(w), and so Y ∩ η(e) ≠ ∅. Choose R_{e} with Y ∩ V (R_{e}) nonempty. By (1), every such choice of R_{e} has length zero. But then Y ⊆ N(D) where D is the triangle {v_{1}, v_{2}, w}, and the theorem holds. This proves (2).

(3) For each e ∈ E(H), let R_{e} be an e-rung. If either the fourth or fifth outcome of (1) holds, then the theorem holds.

For let R be the union of the sets V (R_{e}) (e ∈ E(H)). Suppose first that there exists e = uv ∈ E(H) such that u ∉ W and Y ∩ (R \ V (R_{e})) = N(u) ∩ (R \ V (R_{e})) and Y ∩ V (R_{e}) ⊈ N(u). Then (1) implies that η(f) ∩ Y = ∅ for all f ∈ E(H) not incident with u (because otherwise we could make another choice of R_{f} so that (1) was violated); and η(f) ∩ Y ⊆ N(u) for each f ≠ e incident with u, for the same reason. But then Y ⊆ η(e) ∪ N(u) ∪ N(v), and so the theorem holds by (2).

Next suppose that there exists e = uv ∈ E(H) such that u, v ∉ W and Y ∩ (R \ V (R_{e})) = (N(u) ∪ N(v)) ∩ (R \ V (R_{e})). Again by (1), Y ∩ η(f) = ∅ for each edge f of H not incident with u, v, and Y ∩ η(f) ⊆ η(f, u) for every f ≠ e incident with u, and a similar result holds with u, v exchanged. But then Y ⊆ η(e) ∪ N(u) ∪ N(v) and the theorem holds by (2). This proves (3).

Suppose that there exists e = v_{1}v_{2} ∈ E(H) such that Y ∩ η(e) ⊈ η(e, v_{1}) ∪ η(e, v_{2}). Choose an e-rung R_{e} such that some internal vertex of R_{e} belongs to Y. By (1) and (3), Y ∩ η(f) = ∅ for all f ∈ E(H)\{e}, and so the theorem holds. Hence every vertex in Y belongs to at least one of the sets N(v) (v ∈ V (H)). Suppose that some y ∈ Y belongs to exactly one such set; say y ∈ η(e, v) \ M(e), where e = uv. By (1), Y \ η(e) ⊆ N(v), and so the theorem holds by (2). Thus we may assume that every vertex in Y belongs to M(e) for some e ∈ E(H). Let F be the set of all f ∈ E(H) with Y ∩ M(f) ≠ ∅. If there exist e, f ∈ F with no common end in H, then the theorem holds by (1) and (3); if there is some vertex v of H incident with every edge in F, then Y ⊆ N(v) and the theorem holds; and if neither of these hold, then |F | = 3, and the three members of F are the edges of a triangle D of H, and Y ⊆ N(D) and the theorem holds. This proves 5.3.

5.4 Let X ⊆ V (G) \ ∪η such that G|X is connected, and let Y be the set of all attachments of G|X in ∪η. Then either

• there is an edge e of H such that Y ⊆ η(e), or

• there is a vertex v of H such that Y ⊆ N(v), or

• there is a triangle D of H such that Y ⊆ N(D).

Proof. Suppose that this is false for some X, and choose X minimal such that 5.4 is false for X.

(1) There exist y_{1}, y_{2} in Y such that {y_{1}, y_{2}} ⊈ η(e) for each e ∈ E(H), and {y_{1}, y_{2}} ⊈ N(v) for each v ∈ V (H), and {y_{1}, y_{2}} ⊈ N(D) for each triangle D of H.

For suppose first that for some e = v_{1}v_{2} ∈ E(H), there exists y_{1} ∈ Y ∩η(e) with y_{1} ∉ η(e, v_{1})∪η(e, v_{2}). Now Y ⊈ η(e); choose y_{2} ∈ Y \ η(e), and then y_{1}, y_{2} satisfy (1). We may therefore assume that Y ⊆ ∪_{v∈V (H)}N(v).

Next suppose that some y_{1} ∈ Y belongs to exactly one of the sets N(v) (v ∈ V (H)); say y_{1} ∈ η(e, v_{1}) \ M(e), where e = v_{1}v_{2} ∈ E(H). Since Y ⊈ N(v_{1}), there exists y_{2} ∈ Y \ N(v_{2}). If also y_{2} ∉ η(e), then the pair y_{1}, y_{2} satisfies (1), so we may assume that y_{2} ∈ η(e) \ N(v_{1}). We already assumed that every member of Y belongs to one of the sets N(v) (v ∈ V (H)), and so y_{2} ∈ η(e, v_{2}) \ M(e). This restores the symmetry between v_{1} and v_{2}. Since Y ⊈ η(e), there exists y_{3} ∈ Y with y_{3} ∉ η(e). Since we may assume that the pair y_{1}, y_{3} does not satisfy (1), it follows that y_{3} ∈ N(v_{1}), and similarly y_{3} ∈ N(v_{2}). Let f ∈ E(H) with y_{3} ∈ η(f); then f is incident with v_{1} since y_{3} ∈ N(v_{1}), and similarly f is incident with v_{2}, and so f = e, a contradiction since y_{3} ∉ η(e). We may therefore assume that every y ∈ Y belongs to M(e) for some e ∈ E(H).

Let F be the set of all edges f ∈ E(H) such that Y ∩ M(f) ≠ ∅. Suppose that there exist e, f ∈ F with no common end in H. Choose y_{1} ∈ Y ∩ M(e) and y_{2} ∈ Y ∩ M(f); then y_{1}, y_{2} satisfy (1). Thus we may assume that every two edges in F share an end. Consequently either there is a vertex v ∈ V (H) incident with every member of F, or |F | = 3 and the three edges in F form a triangle D of H. In the first case Y ⊆ N(v), and in the second Y ⊆ N(D), in either case a contradiction. This proves (1).

For each p ∈ X, let Y (p) denote the set of all v ∈ ∪η adjacent to p; and for P ⊆ X, let Y (P) = ∪_{p∈P} Y (p). Thus Y = Y (X). Let y_{1}, y_{2} be as in (1). Then y_{1}, y_{2} are nonadjacent. Since G|X is connected, there is an induced path of G with vertices y_{1}-p_{1}-p_{2}- ⋯ -p_{k}-y_{2} in order. By 5.3 it follows that k > 1. From the minimality of X, X = {p_{1}, …, p_{k}}. Let P_{1} = X \ {p_{k}}, and P_{2} = X \ {p_{1}}. Then for i = 1, 2, the minimality of X implies that either

• there is an edge e of H such that Y (P_{i}) ⊆ η(e), or

• there is a vertex v of H such that Y (P_{i}) ⊆ N(v), or

• there is a triangle D of H such that Y (P_{i}) ⊆ N(D).

Thus there are three possibilities for Y (P_{1}) and three for Y (P_{2}), and we need to check these nine possibilities individually. For each e ∈ E(H) choose an e-rung R_{e} (in some cases we shall need to choose the e-rungs subject to some further conditions), and let K be the graph obtained from H by replacing every edge e of H by a path whose edges are the vertices of R_{e} in the corresponding order. Then (K, W) is a frame for (G, Z). (Thus K depends on the choice of the rungs R_{e}. In what follows it is sometimes useful to change one or more of the paths R_{e}, and K is assumed to change correspondingly, although we may not say so explicitly.) We remark that the subgraph of G induced on the union of the sets V (R_{e}) (e ∈ E(H)) is the line graph of K.

(2) There do not exist v_{1}, v_{2} ∈ V (H) such that Y (P_{1}) ⊆ N(v_{1}) and Y (P_{2}) ⊆ N(v_{2}).

For suppose that such v_{1}, v_{2} exist. Since Y = Y (P_{1}) ∪ Y (P_{2}), it follows that v_{1} ≠ v_{2}. Now v_{1}, v_{2} may or may not be adjacent in H. If they are adjacent, let f = v_{1}v_{2} ∈ E(H), and otherwise f is undefined. For 1 < i < k,

Y (p_{i}) ⊆ Y (P_{1}) ∩ Y (P_{2}) ⊆ N(v_{1}) ∩ N(v_{2}) = M(f),

(where M(f) = ∅ if f is not defined) and so Y ⊆ Y (p_{1})∪Y (p_{k})∪M(f). Suppose first that for i = 1, 2, either N(v_{i}) \ η(f, v_{i}) ⊆ Y (p_{i}) or (N(v_{i}) \ η(f, v_{i})) ∩ Y (p_{i}) = ∅ (where η(f, v_{i}) = ∅ if f is undefined). If (N(v_{i}) \ η(f, v_{i})) ∩ Y (p_{i}) = ∅ for i = 1, 2, then Y ⊆ η(f) (where η(f) = ∅ if f is undefined), a contradiction, so we may assume that N(v_{1}) \ η(f, v_{1}) ⊆ Y (p_{1}) say. If N(v_{2}) \ η(f, v_{2}) ∩ Y (p_{k}) = ∅, then f is defined since Y (p_{k}) ≠ ∅, and we can add p_{1}, …, p_{k} to η(f), and add p_{1} to η(f, v_{1}), contrary to the maximality of ∪η; if N(v_{2}) \ η(f, v_{2}) ⊆ Y (p_{k}) and f is defined, we can add p_{1}, …, p_{k} to η(f), add p_{1} to η(f, v_{1}), and add p_{k} to η(f, v_{2}), again contrary to the maximality of ∪η; so we may assume that N(v_{2}) \ η(f, v_{2}) ⊆ Y (p_{k}) and f is undefined. Thus Y (p_{1}) = N(v_{1}) and Y (p_{k}) = N(v_{2}). Let K′ be obtained from K by adding a path between v_{1}, v_{2} with edges p_{1}, …, p_{k} in order; then (K′, W) is a frame for (G, Z), contrary to the maximality of |E(H)|.

Thus we may assume that for some i ∈ {1, 2}, N(v_{i}) \ η(f, v_{i}) ⊈ Y (p_{i}) and (N(v_{i}) \ η(f, v_{i})) ∩ Y (p_{i}) ≠ ∅. For i = 1, 2, let E_{i} be the set of edges of K incident with v_{i} if f is undefined, and let E_{i} is the set of edges of K incident with v_{i} not in the branch of K between v_{1}, v_{2} if f is defined. Therefore we may choose the paths R_{e} (e ∈ E(H)) such that at least three of the sets A_{1}, B_{1}, A_{2}, B_{2} are nonempty, where for i = 1, 2, A_{i} = E_{i} ∩ Y (P_{i}), and B_{i} = E_{i} \ A_{i}. We may also assume that for i = 1, 2, either y_{i} ∈ E(K), or |B_{i}| = 1 and one of A_{j}, B_{j} is empty, where {i, j} = {1, 2}. (To see this, observe that if say y_{1} ∉ E(K), let y_{1} ∈ η(e) say, and choose an e-rung R′_{e} containing y_{1}; then if either |B_{1}| ≠ 1, or A_{2}, B_{2} are both nonempty, we may replace R_{e} by R′_{e}, and still satisfy all the other requirements.) From the symmetry we may assume that A_{1}, B_{1} ≠ ∅, and hence y_{2} ∈ E(K). Since (K, W) is a frame, there are three paths Q_{1}, Q_{2}, Q_{3} of K such that

• Q_{1} is between v_{1} and w_{1} ∈ W,

• Q_{2} is between v_{1} and w_{2} ∈ W,

• Q_{3} is between v_{2} and w_{3} ∈ W,

• V (Q_{1} ∩ Q_{2}) = {v_{1}},

• Q_{3} is vertex-disjoint from both Q_{1}, Q_{2},

• the edge a_{1} = u_{1}v_{1} of Q_{1} incident with v_{1} belongs to A_{1},

• the edge of Q_{2} incident with v_{1} belongs to B_{1}, and

• Q_{3} is an induced subgraph of K.

If the edge of Q_{3} incident with v_{2} belongs to A_{2}, then

G|(X ∪ E(Q_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}))

is an induced tree containing three vertices of Z, a contradiction. Thus the first edge of Q_{3} is in B_{2}. If y_{2} ∉ A_{2}, then f is defined and y_{2} belongs to the branch of K between v_{1}, v_{2}, and this branch has length at least two (since y_{2} ∉ N(v_{1})); but then

G|(X ∪ E(Q_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}) ∪ {y_{2}})

is an induced tree containing three vertices of Z, a contradiction. Thus y_{2} ∈ A_{2}. Let a_{2} ∈ A_{2}, with ends v_{2}, u_{2} say. Then u_{2} ∉ V (Q_{3}), since Q_{3} is an induced subgraph of K. If u_{2} ∉ V (Q_{1}) ∪ V (Q_{2}), then

G|(X ∪ E(Q_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}) ∪ {a_{2}})

is an induced tree containing three vertices of Z, a contradiction. Thus u_{2} ∈ V (Q_{1}) ∪ V (Q_{2}). If u_{2} ∈ V (Q_{1}) \ {u_{1}, v_{1}}, let Q′_{1} be the path of Q_{1} between u_{2} and w_{1}; then

G|(X ∪ E(Q′_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}) ∪ {a_{1}, a_{2}})

is an induced tree containing three vertices of Z, a contradiction. If u_{2} ∈ V (Q_{2}) \ {v_{1}}, let Q′_{2} be the path of Q_{2} between u_{2} and w_{2}; then

G|(X ∪ E(Q_{1}) ∪ E(Q′_{2}) ∪ E(Q_{3}) ∪ {a_{1}, a_{2}})

is an induced tree containing three vertices of Z, a contradiction. Thus u_{2} ∈ {u_{1}, v_{1}}. But u_{2} ≠ v_{1} from the definition of A_{2}, and so u_{2} = u_{1}. Hence |A_{2}| = 1, and so A_{2} = {y_{2}}, and B_{2} ≠ ∅. This restores the symmetry between v_{1}, v_{2}. From the same argument with v_{1}, v_{2} exchanged, applied to the paths v_{2}-u_{2}-Q_{1}-w_{1}, Q_{3} and Q_{2}, it follows that A_{1} = {y_{1}}, contradicting that y_{1}, y_{2} are nonadjacent in G. This proves (2).

(3) There do not exist v_{1} ∈ V (H) and e ∈ E(H) such that Y (P_{1}) ⊆ N(v) and Y (P_{2}) ⊆ η(e).

For suppose that such v_{1}, e exist. Then e may or may not be incident with v_{1}. If e is not incident with v_{1}, then Y = Y (p_{1}) ∪ Y (p_{2}), while if e is incident with v_{1} then Y ⊆ Y_{1} ∪ Y_{2} ∪ η(e, v_{1}). Suppose first that N(v_{1}) ⊆ Y (P_{1}) ∪ η(e). Since Y (P_{2}) ⊈ N(v_{1}), we may choose the e-rung R_{e} such that at least one vertex of V (R_{e}) ∩ Y (P_{2}) does not belong to N(v_{1}). If e is incident with v_{1}, then we can add p_{1}, …, p_{k} to η(e) and add p_{1} to η(e, v_{1}), contrary to the maximality of ∪η. Thus e is not incident with v_{1}, and so Y (p_{1}) = N(v_{1}). Let e be incident with v_{2}, v_{3} in H. There are three vertex-disjoint paths Q_{1}, Q_{2}, Q_{3} of K such that for i = 1, 2, 3, Q_{i} is between v_{i} and some w_{i} ∈ W. If exactly one vertex of R_{e} is in Y (p_{2}), then

G|(E(Q_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}) ∪ V (R_{e}) ∪ {p_{1}, …, p_{k}})

is an induced tree of G containing three members of Z, a contradiction. If there are two nonadjacent vertices of R_{e} that are both in Y (p_{2}), let S_{2}, S_{3} be minimal subpaths of R_{e} that meet both Y (p_{2}) and N(v_{2}), N(v_{3}) respectively; then there is no edge between V (S_{2}) and V (S_{3}), and

G|(E(Q_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}) ∪ V (S_{2}) ∪ V (S_{3}) ∪ {p_{1}, …, p_{k}})

is an induced tree of G containing three members of Z, a contradiction. Thus there are exactly two vertices in R_{e} that belong to Y (p_{2}), say x, y, and they are adjacent in G. There is a branch of K with edge set the vertex set of R_{e}; let t be the vertex of this branch that is incident with x, y in K. Let K′ be obtained from K by adding a path between v_{1}, t with edges p_{1}, …, p_{k} in order; then (K′, W) is a frame for (G, Z), contrary to the maximality of |E(H)|. This proves that N(v_{1}) ⊈ Y (P_{1}) ∪ η(e).

Hence we may choose the R_{f} (f ∈ E(H)) such that both A_{1}, B_{1} are nonempty, where E_{1} denotes the set of edges of K incident with v_{1} and not in V (R_{e}), and A_{1} = E_{1} ∩ Y (p_{1}), and B_{1} = E_{1} \ Y (p_{1}).

Let e be incident with v_{2}, v_{3} in H. Since (K, W) is a frame, there are three paths Q_{1}, Q_{2}, Q_{3} of K, such that Q_{1} is from v_{1} to some w_{1} ∈ W, Q_{2} is from v_{1} to some w_{2} ∈ W, Q_{3} is from one of v_{2}, v_{3} to some w_{3} ∈ W, V (Q_{1}) ∩ V (Q_{2}) = {v_{1}}, Q_{3} is vertex-disjoint from both Q_{1} and Q_{2}, the edge of Q_{1} incident with v_{1} belongs to A_{1}, and the edge of Q_{2} incident with v_{1} belongs to B_{1}. Moreover, we may assume that only one of v_{2}, v_{3} belongs to V (Q_{3}), say v_{3}. It follows that v_{1} ≠ v_{3}. Since none of Q_{1}, Q_{2}, Q_{3} contain both v_{2}, v_{3}, we may alter our choice of R_{e} without affecting Q_{1}, Q_{2}, Q_{3}; and since Y (P_{2}) ⊈ N(v_{2}) by (2), we may choose R_{e} such that some vertex of R_{e} belongs to Y (P_{2}) \ N(v_{2}). Let S be a minimal subpath of R_{e} that meets both Y (P_{2}) and N(v_{3}). Then

G|(E(Q_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}) ∪ V (S) ∪ {p_{1}, …, p_{k}})

is an induced tree of G containing three vertices of Z, a contradiction. This proves (3).

(4) There do not exist edges e_{1}, e_{2} of H such that Y (P_{i}) ⊆ η(e_{i}) for i = 1, 2.

For suppose that such edges exist. Then e_{1} ≠ e_{2}; let e_{i} have ends u_{i}, v_{i} for i = 1, 2. For i = 1, 2, let T_{i} be the branch of K with edge set V (R_{e_{i}}). Since η(e_{1}) ∩ η(e_{2}) = ∅, it follows that Y = Y (p_{1}) ∪ Y (p_{2}). We may assume that v_{1} ≠ u_{2}, v_{2} and v_{2} ≠ u_{1}, v_{1}; that is, u_{1}, u_{2}, v_{1}, v_{2} are all distinct except that possibly u_{1} = u_{2}. For i = 1, 2, choose R_{e_{i}} such that some vertex of R_{e_{i}} belongs to Y (P_{i}), and in addition, choose R_{e_{i}} such that some vertex of R_{e_{i}} belongs to Y (P_{i}) and not to N(u_{i}) (this is possible since Y (P_{i}) ⊈ N(u_{i}) by (3)). Suppose first that for i = 1, 2, exactly two vertices x_{i}, y_{i} of R_{e_{i}} belong to Y (P_{i}) and they are adjacent. Thus x_{i}, y_{i} are edges of T_{i} with a common end t_{i} say. Let K′ be obtained from K by adding a new path between t_{1}, t_{2} with edges p_{1}, …, p_{k} in order; then (K′, W) is a frame for (G, Z), contrary to the maximality of |E(H)|. We may therefore assume that either exactly one vertex of R_{e_{1}} belongs to Y (p_{1}), or two nonadjacent vertices of R_{e_{1}} belong to Y (p_{1}). Let Q_{1}, Q_{2}, Q_{3} be vertex-disjoint paths of K between {u_{1}, v_{1}, v_{2}} and W, where Q_{1} is between u_{1} and some w_{1} ∈ W, and Q_{2} is between v_{1} and some w_{2} in W, and Q_{3} is between v_{2} and some w_{3} ∈ W. (Possibly u_{2} belongs to one of these paths.) Then some edge of T_{2} belongs to Y (p_{2}) and is not incident with u_{2}, from the choice of R_{e_{2}}. Hence there is a path S_{3} of T_{2} ∪ Q_{3}, with first vertex in V (T_{2}) and last vertex w_{3}, such that the first edge and no other edge of S_{3} belongs to Y (p_{2}), and Q_{1}, Q_{2}, S_{3} are pairwise vertex-disjoint. If only one vertex of R_{e_{1}} is in Y (p_{1}), then

G|(E(Q_{1}) ∪ E(Q_{2}) ∪ E(S_{3}) ∪ {p_{1}, …, p_{k}})

is an induced tree of G containing three members of Z, a contradiction. Thus there are two nonadjacent vertices in V (R_{e_{1}}) ∩ Y (p_{1}), and so there are vertex-disjoint subpaths S_{1}, S_{2} of Q_{1} ∪ T_{1} ∪ Q_{2}, such that for i = 1, 2, S_{i} has first vertex in V (T_{1}), first edge and no other edge in Y (p_{1}), and last vertex w_{i}. But then

G|(E(S_{1}) ∪ E(S_{2}) ∪ E(S_{3}) ∪ {p_{1}, …, p_{k}})

is an induced tree of G containing three members of Z, a contradiction. This proves (4).

From (2),(3),(4), we may assume that Y (P_{2}) ⊆ N(D) for some triangle D = {u_{1}, u_{2}, u_{3}} of H, and that M(u_{1}u_{2}), M(u_{2}u_{3}), M(u_{1}u_{3}) all contain at least one member of Y (P_{2}). Let e_{1}, e_{2}, e_{3} be the edges u_{2}u_{3}, u_{3}u_{1}, u_{1}u_{2} of H respectively. Choose R_{e_{1}} of length zero such that its vertex (r_{1} say) is in Y (P_{2}), and choose R_{e_{2}}, R_{e_{3}} similarly. Thus r_{1} is the edge of K joining u_{2}, u_{3}. For i = 1, 2, 3, let Q_{i} be a path of K between u_{i} and some w_{i} ∈ W, such that Q_{1}, Q_{2}, Q_{3} are pairwise vertex-disjoint.

(5) Y (P_{1}) ∩ E(K) ⊆ {r_{1}, r_{2}, r_{3}}.

For let e ∈ Y (P_{1}) ∩ E(K), and suppose first that at most one of Q_{1}, Q_{2}, Q_{3} contains an end of e. Since K is connected, we may choose a path S of K with first edge in Y (p_{1}) such that S meets one of Q_{1}, Q_{2}, Q_{3}; and by choosing S minimal, we may assume that S meets Q_{3} and not Q_{1}, Q_{2}, and only its first edge is in Y (p_{1}). In particular, u_{1}, u_{2} ∉ V (S), and so no edge of S is in N(D); and therefore no edge of S except the first is adjacent in G to any of p_{1}, …, p_{k}. Let S′ be a path of S ∪ Q_{3} between the first vertex of S and w_{3}. Then

G|(E(Q_{1}) ∪ E(Q_{2}) ∪ E(S′) ∪ {p_{1}, …, p_{k}})

is an induced tree in G containing three members of Z, a contradiction. This proves that two of Q_{1}, Q_{2}, Q_{3} contain ends of e. Let e = v_{1}v_{2} where v_{1} ∈ V (Q_{1}) and v_{2} ∈ V (Q_{2}) say. Suppose that v_{2} ≠ u_{2}. For i = 1, 2, let S_{i} be a subpath of Q_{i} between v_{i} and w_{i}. Then

G|(E(S_{1}) ∪ E(S_{2}) ∪ E(Q_{3}) ∪ {e, r_{1}} ∪ {p_{1}, …, p_{k}})

is an induced tree in G containing three members of Z, a contradiction. Thus v_{2} = u_{2}, and similarly v_{1} = u_{1} and so e = r_{3}. This proves (5).

From (5), we deduce that Y (P_{1}) ⊆ η(e_{1}) ∪ η(e_{2}) ∪ η(e_{3}) (for otherwise we could make a choice of the R_{f} for f ≠ u_{1}u_{2}, u_{1}u_{3}, u_{2}u_{3} that would violate (5)). Since Y (P_{1}) ⊈ N(D), we may assume that there is some e_{3}-rung R′_{e_{3}} such that some vertex of R′_{e_{3}} belongs to Y (P_{1}) and not to η(e_{3}, u_{2}) (and so R′_{e_{3}} has length at least one). Let S be a minimal subpath of R′_{e_{3}} that meets both Y (P_{1}) and η(e_{3}, u_{1}). Then

G|(E(Q_{1}) ∪ E(Q_{2}) ∪ E(Q_{3}) ∪ V (S) ∪ {r_{1}} ∪ {p_{1}, …, p_{k}})

is an induced tree in G containing three members of Z, a contradiction. This proves 5.4.

Proof of 3.2. We have already seen the proof of the “if” half. To prove the “only if” half, we may assume that |Z| ≥ 3. We choose H, W as in 5.2. Choose η as before; that is, η is a connected H-strip structure in (G, Z), chosen with ∪η maximal. Let C be the set of all vertex sets of components of G \ ∪η. For C ∈ C we define its home as follows. Let Y be the set of attachments of G|C in G| ∪ η. We say that e ∈ E(H) is the home of C if Y ⊆ η(e); v ∈ V (H) is the home of C if Y ⊆ N(v) and no edge of H is the home of C; and a triangle D of H is the home of C if Y ⊆ N(D) and there is no vertex or edge of H that is the home of C. By 5.4, each C ∈ C has a (unique) home. For each e ∈ E(H), let η′(e) be the union of η(e) and all C ∈ C with home e. Define η′(e, v) = η(e, v) if v ∈ V (H) is incident with e. For each v ∈ V (H), define η′(v) to be the union of all C ∈ C with home v, and for each triangle D of H, let η′(D) be the union of all C ∈ C with home D. It follows that η′ is an extended H-strip decomposition of (G, Z). This proves 3.2.

6 The algorithm

So far, we have proved our main result, the description of the structure of the constricted pairs; now we present a polynomial-time algorithm for the following question:

CONSTRICTED. With input a graph G and Z ⊆ V (G), decide whether Z is constricted.

Our main theorem 3.2 asserts that for a given pair (G, Z), either there is an induced subtree containing three members of Z, or (G, Z) admits an extended H-strip decomposition for some H, and not both. Therefore we could ask for a polynomial algorithm for the following more demanding question:

TREE-OR-DECOMPOSITION. With input a connected graph G and Z ⊆ V (G) with |Z| ≥ 2, output either an induced subtree of G containing at least three members of Z, or a graph H and an extended H-strip decomposition η of (G, Z).

We will first give an algorithm for CONSTRICTED, and then discuss how to modify it to solve TREE-OR-DECOMPOSITION. It would be nice to use 3.2 to show that some simple algorithm works, but so far we have not been able to do this. The best method we can see is just to convert the proof of the theorem to an algorithm.

Thus, we have input a graph G and a subset Z ⊆ V (G), and we wish to decide whether Z is constricted in G. It is easy to reduce this question to the special case when G is connected and |Z| ≥ 3, so from now on we assume that. Let |V (G)| = n. Let η be a connected H-strip structure in (G, Z), let X ⊆ V (G) \ ∪η, and let Y be the set of all members of ∪η that have at least one neighbour in X. We say that X is local (with respect to (H, η)) if either Y ⊆ η(e) for some e ∈ E(H), or Y ⊆ N(v) for some v ∈ V (H), or Y ⊆ N(D) for some triangle D of H (using the notation of 5.3 and 5.4).

It is easy to modify the first part of the proof of 5.4, and the proof of the “only if” half of 3.2, to yield the following subroutine.

6.1 Algorithm.

• Input: A pair (G, Z) as above, a graph H, and a connected H-strip structure η in (G, Z).

• Output: One of the following:

– An extended H-strip decomposition of (G, Z), or

– a subset X ⊆ V (G) \ ∪η, such that G|X is connected, X is not local, and X is minimal with these properties.

• Running time: O(n^{2}).

Let η be some connected H-strip structure in (G, Z). We define its worth to be |∪η|+(n+1)|E(H)|. Thus every H-strip structure has worth at most (n + 1)^{2}, since | ∪ η| ≤ n and |E(H)| ≤ n. We need another subroutine, as follows.

6.2 Algorithm.

• Input: A pair (G, Z) as above, a graph H, a connected H-strip structure η in (G, Z), and a subset X ⊆ V (G) \ ∪η, such that G|X is connected, X is not local, and X is minimal with these properties.

• Output: One of the following:

– A graph H′ and a connected H′-strip structure η′ in (G, Z) with worth greater than that of η, or

– a (true) statement that Z is not constricted in G|((∪η) ∪ X), and therefore not in G.

• Running time: O(n^{2}).

This can be obtained by modifying the proof of 5.3 and the latter part of the proof of 5.4 appropriately. More exactly, if |X| = 1 we modify the proof of 5.3, and otherwise we modify the proof of 5.4. Suppose first that |X| = 1. We test whether one of the five statements of step (1) of the proof of 5.3 holds. The first three are impossible since X is not local. If either the fourth or fifth holds, we can add the vertex in X to one of the strips η(e) and produce a connected H-strip structure in (G, Z) with worth greater than that of η as required. If none of the outcomes of step (1) of the proof of 5.3 holds, it follows that either Z is not constricted in G|((∪η) ∪ X) is not constricted and we are done, or H, η does not satisfy the hypotheses of 5.3; and in this case it is easy to modify the proof of 5.3 to yield a connected H′-strip structure η′ in (G, Z) with worth greater than that of η. When |X| > 1 we modify the proof of 5.4 in an analogous way.

Combining these two subroutines yields:

6.3 Algorithm.

• Input: A pair (G, Z) as above, a graph H, and a connected H-strip structure η in (G, Z).

• Output: One of the following:

– An extended H-strip decomposition of (G, Z), or

– a graph H′ and a connected H′-strip structure η′ in (G, Z) with worth greater than that of η, or

– a statement that Z is not constricted in G.

• Running time: O(n^{2}).

To make use of 6.3 to solve CONSTRICTED, we first choose some frame (K, W) for (G, Z), by using the method of 5.1. (Or we find some induced tree containing at least three members of Z, and then we output this and stop.) This takes time O(n^{2}), where n = |V (G)|. We convert this to a connected H_{1}-strip structure η_{1} say. Inductively, having produced a graph H_{i} and a connected H_{i}-strip structure η_{i} of worth at least i, we apply 6.3 to H_{i}, η_{i}. If we obtain either the first or third output of 6.3 we are done, and if we obtain the second output this defines H_{i+1}, η_{i+1}, of worth at least i + 1. Since no η_{i} has worth more than (n + 1)^{2}, this process iterates at most (n + 1)^{2} times before terminating, and since each iteration takes time O(n^{2}), the total running time is O(n^{4}).

To solve TREE-OR-DECOMPOSITION instead of just CONSTRICTED, note first that the algorithm just described outputs an extended H-decomposition for some H when Z is constricted, so we have half of what we need for free. We just need to modify the last output of 6.2. At that stage, instead of just the statement that Z is not constricted in G, we need to find an induced subtree of G containing three members of Z; and to do so we need to look more carefully at the proofs of 4.1, 5.3 and 5.4 at the appropriate points. Since we will exit the main recursion at this stage, we can afford to spend time O(n^{4}) instead of just O(n^{2}) to exhibit the desired tree, and this is easily done (we omit the details). Thus the running time of the algorithm to solve TREE-OR-DECOMPOSITION is also O(n^{4}).

There is also a simpler method to solve TREE-OR-DECOMPOSITION (but with running time O(n^{5})). We repeatedly use the algorithm of CONSTRICTED as a subroutine. We may assume that initially Z is not constricted in G (for otherwise the algorithm above for CONSTRICTED outputs an extended H-strip decomposition and we are done). For each vertex v in turn, test whether Z \{v} is constricted in G \ {v}, and if not then remove v from G, Z. What remains at the end is the desired tree.

References

[1] D. Bienstock, “On the complexity of testing for even holes and induced odd paths”, Discrete. Math. 90 (1991), 85-92. Corrigendum in Discrete Math. 102 (1992), 109.

[2] M. Chudnovsky and R. Kapadia, “Detecting a theta or a prism”, SIAM J. Discrete Math. 22 (2008), 1–18.

[3] M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour and K. Vušković, “Recognizing Berge graphs”, Combinatorica 25 (2005), 143–186.

[4] R. Kapadia, Detecting a Theta or a Prism, Senior Thesis, Princeton, May 2006.

[5] F. Maffray and N. Trotignon, “Algorithms for perfectly contractile graphs”, SIAM J. Discrete Math. 19 (2005), 553–574.