Introduction
Structural graph theory provides a mathematical foundation for the development of powerful algorithmic techniques and the systematic design of efficient algorithms for computationally hard problems on structurally restricted graph classes. Central concepts such as graph minors and tree decompositions have played a particularly important role in this interplay between structure and algorithms. A prime example is the theory of treewidth and the celebrated Courcelle’s Theorem [6 ] .
(Dumas, Stamoulis) Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
(Hodor) Theoretical Computer Science Department, Faculty of Mathematics and Computer Science and Doctoral School of Exact and Natural Sciences, Jagiellonian University, Kraków, Poland
(Mazur, Micek) Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
(Rambaud) Mathematics department, TU Darmstadt, Germany
E-mail addresses: mael.dumas@irif.fr, jedrzej.hodor@gmail.com, tom.mazur34@gmail.com, piotr.micek@uj.edu.pl, clement.rambaud@normalesup.org, stamoulis@irif.fr.
M. Dumas received funding from ERC grant BUKA (No. 101126229). J. Hodor is supported by a Polish Ministry of Education and Science grant (Perły Nauki; PN/01/0265/2022). T. Mazur and P. Micek were partially supported by the National Science Centre of Poland under grant UMO-2023/05/Y/ST6/00079 within the Weave-UNISONO program. C. Rambaud has been funded by the European Union through European Research Council project WYDRA, grant agreement no. 101230549. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. G. Stamoulis was supported by the project RBBR that is funded from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme with grant agreement No. 948057. In particular, part of work on this manuscript was done while G. Stamoulis was affiliated with University of Warsaw.
In this paper, we study classical statements from structural graph theory in a setting where a graph is equipped with a distinguished set of vertices. An annotated graph is a pair ( G , S ) (G,S) ( G , S ) , where G G G is a graph and S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) . Our motivation for pursuing this line of research is twofold: algorithmic and structural.
Many problems in theoretical computer science take as input not only a graph, but also a distinguished subset of its vertices. For example, in the Sᴛᴇɪɴᴇʀ Tʀᴇᴇ problem, the input consists of a connected graph G G G with nonnegative edge weights together with a subset of vertices of G G G , whose elements are usually referred to as terminals . The goal is to find a connected subgraph of G G G containing all terminals, possibly together with additional vertices, and having minimum total edge weight.
Although Sᴛᴇɪɴᴇʀ Tʀᴇᴇ is computationally hard in general, standard dynamic programming techniques solve it on n n n -vertex graphs of treewidth at most t t t in time f ( t ) ⋅ n O ( 1 ) f(t) \cdot n^{O(1)} f ( t ) ⋅ n O ( 1 ) . However, a tree decomposition of the input graph is oblivious to the distinguished set of terminals. In particular, the portion of the graph that is relevant for connecting the terminals may be structurally simple and well separated from the remainder of the graph, while the remainder itself may be arbitrarily complicated . Thus, the treewidth of the entire graph may substantially overestimate the structural complexity that is relevant to the problem.
A generic way to incorporate a distinguished set of vertices into a graph parameter is via torsos. Given a graph G G G and a subset S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) , we define torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) to be the graph with vertex set S ′ S' S ′ in which distinct vertices u , v ∈ S ′ u,v \in S' u , v ∈ S ′ are adjacent if and only if there exists a u u u –v v v path in G G G whose internal vertices lie outside S ′ S' S ′ . In particular, for every S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) , we have G [ S ′ ] ⊆ torso G ( S ′ ) G[S'] \subseteq\operatorname{torso}_G(S') G [ S ′ ] ⊆ torso G ( S ′ ) .
Now let p be any graph parameter; formally, p is a real-valued function on the isomorphism classes of finite simple graphs. For an annotated graph ( G , S ) (G,S) ( G , S ) , we define the torso p of ( G , S ) (G,S) ( G , S ) by
p ( G , S ) = min { p ( torso G ( S ′ ) ) ∣ S ⊆ S ′ ⊆ V ( G ) } . \operatorname{p}(G,S)=\min\{\operatorname{p}(\operatorname{torso}_G(S')) \mid S \subseteq S' \subseteq V(G)\}. p ( G , S ) = min { p ( torso G ( S ′ )) ∣ S ⊆ S ′ ⊆ V ( G )} .
Thus, rather than measuring the complexity of the whole graph G G G , we are allowed to enlarge the distinguished set S S S to a set S ′ S' S ′ and measure the complexity of the corresponding torso. The simplest explanation why we should consider a superset of S S S comes from the following example. Consider G G G to be a star with S S S being the set of leaves. Then, torso G ( S ) \operatorname{torso}_G(S) torso G ( S ) is a complete graph while G G G itself is very simple.
Jansen and Swennenhuis [15 ] proved that the Sᴛᴇɪɴᴇʀ Tʀᴇᴇ problem can be solved efficiently on n n n -vertex annotated graphs of torso treewidth at most t t t in time f ( t ) ⋅ n O ( 1 ) f(t) \cdot n^{O(1)} f ( t ) ⋅ n O ( 1 ) . This provides an algorithmic indication that torso versions of classical width parameters may capture the complexity of annotated instances more accurately than the corresponding parameters of the underlying graph. The first implicit occurrence of a torso parameter that we could track is in a paper of Marx, O’Sullivan, and Razgon [19 Lemma 2.11] .
We now turn to the structural motivation for studying annotated graphs. In their seminal Graph Minors series, spanning from 1983 to 2010, Robertson and Seymour developed a far-reaching theory describing the structure of graphs excluding a fixed graph as a minor. One of the central themes of this theory is the close relationship between excluded minors and width parameters such as treewidth and pathwidth. For instance, excluding a fixed planar graph as a minor is equivalent to having bounded treewidth, as follows from the Grid Minor Theorem [25 ] . Similarly, excluding a fixed forest as a minor is equivalent to having bounded pathwidth, as established already in the first paper of the series [24 ] .
Recently, Hodor, La, Micek, and Rambaud [13 ] studied analogous statements for excluded minors of apex type. Recall, for example, that a graph is an apex-forest if it can be made acyclic by deleting at most one vertex. They proved that for every apex-forest X X X , X X X -minor-free graphs have bounded local pathwidth, i.e. every radius r r r balls induces a subgraph of pathwidth at most O ( ∣ V ( X ) ∣ ⋅ r ) O(|V(X)| \cdot r) O ( ∣ V ( X ) ∣ ⋅ r ) . Note that a similar statement with worse bounds was proved before by Dujmović, Eppstein, Joret, Morin, and Wood [8 ] . A key novelty in the proof in [13 ] is the use of torso pathwidth.
These two independent developments, one arising from parameterized algorithms and the other from structural graph theory, suggest that width parameters for annotated graphs deserve a systematic study in their own right.
There is a very natural way of mimicking the minor relation in the realm of annotated graphs. We say that a family ( B x ∣ x ∈ V ( H ) ) (B_x \mid x \in V(H)) ( B x ∣ x ∈ V ( H )) of pairwise disjoint subsets of vertices of G G G is a model of an annotated graph ( H , T ) (H,T) ( H , T ) in an annotated graph ( G , S ) (G,S) ( G , S ) if
(i) for each x ∈ V ( H ) x \in V(H) x ∈ V ( H ) , G [ B x ] G[B_x] G [ B x ] is a connected subgraph of G G G ;
(ii) for all x y ∈ E ( H ) xy \in E(H) x y ∈ E ( H ) , there exists u ∈ B x u \in B_x u ∈ B x and v ∈ B y v \in B_y v ∈ B y with u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) ; and
(iii) for each x ∈ T x \in T x ∈ T , there exists u ∈ S u \in S u ∈ S with u ∈ B x u \in B_x u ∈ B x .
When there exists a model of an annotated graph ( H , T ) (H,T) ( H , T ) in an annotated graph ( G , S ) (G,S) ( G , S ) , we say that ( H , T ) (H,T) ( H , T ) is a minor of ( G , S ) (G,S) ( G , S ) . In the case where ( H , V ( H ) ) (H,V(H)) ( H , V ( H )) is a minor of ( G , S ) (G,S) ( G , S ) , we also say that H H H is an S S S -rooted minor of G G G and a model of ( H , V ( H ) ) (H,V(H)) ( H , V ( H )) in ( G , S ) (G,S) ( G , S ) is called an S S S -rooted model of H H H in G G G . Note that H H H is a minor of G G G if and only if ( H , V ( H ) ) (H,V(H)) ( H , V ( H )) is a minor of ( G , V ( G ) ) (G,V(G)) ( G , V ( G )) . Similar notions were already studied in literature [27 , 17 , 34 ] .
In this paper, we study the interplay between torso parameters and excluding annotated graphs as minors. We (try to) list all the known results in this direction along with some new ones. The graph parameters that we study are: vertex cover number, treedepth, pathwidth, treewidth, 2-treedepth, feedback vertex number, and Hadwiger number; they are denoted respectively by: vc ( ⋅ ) \operatorname{vc}(\cdot) vc ( ⋅ ) , td ( ⋅ ) \operatorname{td}(\cdot) td ( ⋅ ) , pw ( ⋅ ) \operatorname{pw}(\cdot) pw ( ⋅ ) , tw ( ⋅ ) \operatorname{tw}(\cdot) tw ( ⋅ ) , td 2 ( ⋅ ) \operatorname{td}_2(\cdot) td 2 ( ⋅ ) , fv ( ⋅ ) \operatorname{fv}(\cdot) fv ( ⋅ ) , and had ( ⋅ ) \operatorname{had}(\cdot) had ( ⋅ ) . For each of the parameters, we prove or cite an approximate excluded annotated minor characterization. We define
F v c = { ( H , V ( H ) ) ∣ H is a matching } , \mathcal{F}_{\mathrm{vc}} = \{(H,V(H)) \mid H \text{ is a matching}\}, F vc = {( H , V ( H )) ∣ H is a matching } ,
F t d = { ( H , V ( H ) ) ∣ H is a path } , \mathcal{F}_{\mathrm{td}} = \{(H,V(H)) \mid H \text{ is a path}\}, F td = {( H , V ( H )) ∣ H is a path } ,
F p w = { ( H , V ( H ) ) ∣ H is a forest } , \mathcal{F}_{\mathrm{pw}} = \{(H,V(H)) \mid H \text{ is a forest}\}, F pw = {( H , V ( H )) ∣ H is a forest } ,
F t w = { ( H , T ) ∣ H is a plane graph and T is contained in the outer face of H } , \mathcal{F}_{\mathrm{tw}} = \{(H,T) \mid H \text{ is a plane graph and } T \text{ is contained in the outer face of } H\}, F tw = {( H , T ) ∣ H is a plane graph and T is contained in the outer face of H } ,
F t d 2 = { ( H , T ) ∣ H is a ladder and T is a side of H } , \mathcal{F}_{\mathrm{td}_2} = \{(H,T) \mid H \text{ is a ladder and } T \text{ is a side of } H\}, F td 2 = {( H , T ) ∣ H is a ladder and T is a side of H } ,
F f v = { ( H , V ( H ) ) ∣ H is a disjoint union of triangles } , \mathcal{F}_{\mathrm{fv}} = \{(H,V(H)) \mid H \text{ is a disjoint union of triangles}\}, F fv = {( H , V ( H )) ∣ H is a disjoint union of triangles } ,
F h a d = { ( H , V ( H ) ) ∣ H is a complete graph } . \mathcal{F}_{\mathrm{had}} = \{(H,V(H)) \mid H \text{ is a complete graph}\}. F had = {( H , V ( H )) ∣ H is a complete graph } .
A graph class is minor-closed if for every graph in the class, all its minors also belong to the class.
Theorem 1. For each p ∈ { v c , t d , p w , t w , t d 2 , f v , h a d } \mathrm{p} \in\{\mathrm{vc},\mathrm{td},\mathrm{pw},\mathrm{tw},\mathrm{td}_2,\mathrm{fv},\mathrm{had}\} p ∈ { vc , td , pw , tw , td 2 , fv , had } and for every minor-closed class of annotated graphs C \mathcal{C} C , there exists a graph ( H , T ) ∈ F p (H,T) \in\mathcal{F}_{\mathrm{p}} ( H , T ) ∈ F p with ( H , T ) ∉ C (H,T) \notin\mathcal{C} ( H , T ) ∈ / C if and only if there exists a constant c c c such that for every ( G , S ) ∈ C (G,S) \in\mathcal{C} ( G , S ) ∈ C , we have p ( G , S ) ≤ c \mathrm{p}(G,S) \leq c p ( G , S ) ≤ c .
See a visual summary in Table 1 . Theorem 1 is proved in § 3 . The statements for p ∈ { v c , t d , p w , t w } \mathrm{p} \in\{\mathrm{vc},\mathrm{td},\mathrm{pw},\mathrm{tw}\} p ∈ { vc , td , pw , tw } are already known in the literature [11 , 13 , 4 , 20 ] , and we include them for completeness and illustration without proofs. The statement for p = h a d \mathrm{p}=\mathrm{had} p = had can also be derived from known results, see [9 Corollary 13] or [21 Theorem 1.2] . Since, to our knowledge, there is no explicit proof in the literature, we include the proof. Finally, the proofs for p ∈ { t d 2 , f v } \mathrm{p} \in\{\mathrm{td}_2,\mathrm{fv}\} p ∈ { td 2 , fv } are new. It is well-known that paths are obstructiong bounded treedepth, however, the treedepth of a path is logarithmic in its size. Kawarabayashi and Rossman [17 ] found obstructions for
Table 1. Summary of Theorem 1 , which assert that, for each parameter p ∈ {vc, td, pw, tw, td2 _2 2 , fv, had}, a minor-closed class of annotated graphs has bounded p if and only if it excludes a member of F p \mathcal{F}_p F p . Here, the annotated vertices are depicted as red squares.
bounded treedepth that have polynomial treedepth. We provide an annotated variant of this statement, see Theorem 21 .
Erdős–Pósa property for annotated models
In 1965, Erdős and Pósa [10 ] proved that there is a function f ( k ) = O ( k log k ) f(k) = O(k \log k) f ( k ) = O ( k log k ) such that for every graph G G G and every positive integer k k k , either G G G contains k k k vertex-disjoint cycles, or there is a set X X X of at most f ( k ) f(k) f ( k ) vertices of G G G such that G − X G - X G − X is a forest. Informally, we say that cycles have the Erdős–Pósa property .
Here, we are interested in Erdős–Pósa property of models of a fixed graph H H H . It is well-known that models of H H H have the Erdős–Pósa property if and only if H H H is planar [25 ] . The positive direction of the statement above follows from the grid minor theorem. Van Batenburg, Huynh, Joret, and Raymond [33 ] proved that when H H H is planar, the function witnessing the Erdős–Pósa property of models of H H H is in O ( k log k ) O(k \log k) O ( k log k ) .
We are interested in the Erdős–Pósa property of models of annotated graphs in annotated graphs. The annotated variant of the grid theorem (Theorem 1 for p = tw or [13 Theorem 9] ) implies that if H H H is a connected planar graph with a fixed plane embedding and T T T is a subset of the vertices of the outer face of H H H , then the models of ( H , T ) (H, T) ( H , T ) in annotated graphs have the Erdős–Pósa property.
Theorem 2 ([13 Corollary 24] ). For every connected graph H H H with a fixed plane embedding, for every subset T ⊆ V ( H ) T \subseteq V(H) T ⊆ V ( H ) of the vertices on the outer face of H H H , there exists a function f ( H , T ) : N → N f_{(H,T)}: \mathbb{N} \to\mathbb{N} f ( H , T ) : N → N such that for every annotated graph ( G , S ) (G,S) ( G , S ) , and for every positive integer k k k , either
(i) ( G , S ) (G,S) ( G , S ) has k k k disjoint models of ( H , T ) (H,T) ( H , T ) or
(ii) there exists a set Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) such that ∣ Z ∣ ≤ f ( H , T ) ( k ) |Z| \leq f_{(H,T)}(k) ∣ Z ∣ ≤ f ( H , T ) ( k ) and G − Z G-Z G − Z has no models of ( H , T ) (H,T) ( H , T ) .
Combining with the most recent improvements on the grid theorem due to Chuzhoy and Tan [3 ] and Bonnet [1 ] , we may have f ( H , T ) ( k ) = O ~ ( k 33 ) f_{(H,T)}(k) = \widetilde{O}(k^{33}) f ( H , T ) ( k ) = O ( k 33 ) in Theorem 2 . We conjecture that f ( H , T ) ( k ) = O ( k log k ) f_{(H,T)}(k) = O(k \log k) f ( H , T ) ( k ) = O ( k log k ) is possible, see Theorem 41 . As evidence, we prove the first non-trivial case.
Theorem 3. Let H = K 3 H = K_3 H = K 3 and let T T T be a one-vertex subset of V ( H ) V(H) V ( H ) . There exists a constant c c c such that for every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , either
(i) ( G , S ) (G,S) ( G , S ) has k k k disjoint models of ( H , T ) (H,T) ( H , T ) or
(ii) there exists a set Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) such that ∣ Z ∣ ≤ c ⋅ k log k |Z| \leq c \cdot k \log k ∣ Z ∣ ≤ c ⋅ k log k and ( G − Z , S \ Z ) (G-Z,S\backslash Z) ( G − Z , S \ Z ) has no model of ( H , T ) (H,T) ( H , T ) .
Theorem 3 follows from Theorem 38 proved in § 4 . Note that when H H H is a forest, then the pathwidth part of Theorem 1 , namely Theorem 12 , implies that one may take f ( H , T ) f_{(H,T)} f ( H , T ) quadratic (see [13 Corollary 25] ). Recently Claus, Joret, Rambaud, and Robinson [5 ] showed that in this case, f ( H , T ) f_{(H,T)} f ( H , T ) can be linear.
Minor-closed classes of annotated graphs
One of the fundamental results of structural graph theory due to Robertson and Seymour is that all graphs are well-quasi ordered under the minor relation. In other words, every minor-closed class of graphs has a finite list of minor-minimal obstructions. In fact, the result of Robertson and Seymour [26 ] is general enough so it can be also applied to annotated graphs, see also [21 Section 2.4] . Following the approach that we took for graph parameters, every minor-closed class of graphs yields a minor-closed class of annotated graphs. For every class of graphs C \mathcal{C} C , let
C ∙ = { ( G , S ) ∣ there exists S ′ ⊆ V ( G ) with S ⊆ S ′ such that torso G ( S ′ ) ∈ C } . \mathcal{C}^{\bullet} = \{(G,S) \mid\text{there exists } S' \subseteq V(G) \text{ with } S \subseteq S' \text{ such that } \operatorname{torso}_{G}(S') \in\mathcal{C}\}. C ∙ = {( G , S ) ∣ there exists S ′ ⊆ V ( G ) with S ⊆ S ′ such that torso G ( S ′ ) ∈ C } .
The following meta-question arises. Given a class of graphs C \mathcal{C} C for which we know the minor-minimal obstructions, what are the minor-minimal obstructions of C ∙ \mathcal{C}^{\bullet} C ∙ ? We solve the first nontrivial case where C \mathcal{C} C is the class of forests.
Theorem 4. Let C \mathcal{C} C be the class of all forests. For every annotated graph ( G , S ) (G,S) ( G , S ) , we have ( G , S ) ∈ C ∙ (G,S) \in\mathcal{C}^{\bullet} ( G , S ) ∈ C ∙ if and only if K 3 K_3 K 3 is not an S S S -rooted minor of G G G .
Theorem 4 is proved in Subsection 3.4. It would be interesting to establish a similar theorem for C \mathcal{C} C , being all the planar graphs, i.e. an annotated Kuratowski theorem, see Theorem 42 .
Other related results
Annotated graphs are of neuralgic importance in recent results in the Graph Minors literature. The central notion behind several of these developments is the one of bidimensionality of a vertex set S S S in a graph G G G , i.e. the maximum integer ℓ \ell ℓ such that the ℓ × ℓ \ell\times\ell ℓ × ℓ grid is contained as an S S S -rooted minor in G G G . Bidimensionality was used to rephrase the graph minors structure theorem [31 , 12 ] but also exhibits the optimality of the improved bounds for the unique linkage theorem [2 ] . A variant of bidimensionality provides the framework for showing a dichotomy result for the applicability of the irrelevant vertex technique [32 ] . Bidimensionality has also been studied from the lens of logic, enabling algorithmic meta-theorems for corresponding extensions of first-order logic [29 , 28 ] .
Annotated graphs can be seen as a special instance of the more general notion of colorful graphs , graphs equipped with a fixed number of subsets of vertices, which were introduced by Protopapas, Thilikos, and Wiederrecht [21 ] . Furthermore, they [22 ] characterized which models of colorful graphs admit Erdős–Pósa property. See also related work of Kwon and Marx [18 ] .
Preliminaries
For each positive integer k k k , we write [ k ] = { 1 , … , k } [k] = \{1,\ldots,k\} [ k ] = { 1 , … , k } , and [ 0 ] = ∅ [0] = \emptyset [ 0 ] = ∅ . All graphs considered in this paper are finite, simple, and undirected. The null graph is the graph with no vertices. Connected graphs are nonnull. Trees are defined as connected forests, thus trees and subtrees are also assumed to be nonnull. Given a graph G G G , we denote by V ( G ) V(G) V ( G ) its vertex set and by E ( G ) E(G) E ( G ) its edge set. A graph parameter is a function mapping each graph to a real number. A graph parameter p is minor-monotone if for all graphs H H H and G G G , the fact that H H H is a minor of G G G implies p ( H ) ≤ p ( G ) \mathrm{p}(H) \le\mathrm{p}(G) p ( H ) ≤ p ( G ) . Two subgraphs of a graph are disjoint if they are vertex-disjoint.
Let G G G and H H H be graphs. We denote by G ∪ H G \cup H G ∪ H (resp. G ∩ H G \cap H G ∩ H ) the graph with vertex set V ( G ) ∪ V ( H ) V(G) \cup V(H) V ( G ) ∪ V ( H ) (resp. V ( G ) ∩ V ( H ) V(G) \cap V(H) V ( G ) ∩ V ( H ) ) and edge set E ( G ) ∪ E ( H ) E(G) \cup E(H) E ( G ) ∪ E ( H ) (resp. E ( G ) ∩ E ( H ) E(G) \cap E(H) E ( G ) ∩ E ( H ) ). Given two subgraphs A A A and B B B of G G G , we say that ( A , B ) (A,B) ( A , B ) is a separation of G G G if A ∪ B = G A \cup B = G A ∪ B = G . We call ∣ V ( A ) ∩ V ( B ) ∣ \lvert V(A) \cap V(B) \rvert ∣ V ( A ) ∩ V ( B )∣ the order of the separation ( A , B ) (A,B) ( A , B ) . Given X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) , we use G − X G-X G − X to denote the graph obtained from G G G by removing the vertices of X X X and all their incident edges. For a collection H \mathcal{H} H of subgraphs of a graph G G G , we use V ( H ) V(\mathcal{H}) V ( H ) to denote the set ⋃ { V ( H ) ∣ H ∈ H } \bigcup\{V(H) \mid H \in\mathcal{H}\} ⋃ { V ( H ) ∣ H ∈ H } . We say that H H H is a subdivision of G G G if it can be obtained from G G G by replacing each edge by a path of length1 {}^{1} 1 at least one.
For all S , T ⊆ V ( G ) S,T \subseteq V(G) S , T ⊆ V ( G ) , an S S S –T T T path is a path in G G G that is either a one-vertex path with a vertex in S ∩ T S \cap T S ∩ T , or a path with one endpoint in S ∖ T S\setminus T S ∖ T and the other endpoint in T ∖ S T\setminus S T ∖ S such that no internal vertices are in S ∪ T S \cup T S ∪ T . When S S S or T T T is a singleton, say S = { u } S = \{u\} S = { u } , we simplify the notation to u u u –T T T path and analogous variants.
We state and prove several simple observations.
Observation 5. Let ( G , S ) (G,S) ( G , S ) be an annotated graph, let H H H be a graph, and let S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S \subseteq S' S ⊆ S ′ . If H H H is an S S S -rooted minor of G G G , then H H H is a minor of torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) .
Proof. Suppose that ( B x ∣ x ∈ V ( H ) ) (B_x \mid x \in V(H)) ( B x ∣ x ∈ V ( H )) is an S S S -rooted model of H H H in ( G , S ) (G,S) ( G , S ) . For every x ∈ V ( H ) x \in V(H) x ∈ V ( H ) , let B x ′ = B x ∩ S ′ B'_x = B_x \cap S' B x ′ = B x ∩ S ′ . We claim that ( B x ′ ∣ x ∈ V ( H ) ) (B'_x \mid x \in V(H)) ( B x ′ ∣ x ∈ V ( H )) is a model of H H H in G ′ = torso G ( S ′ ) G' = \operatorname{torso}_G(S') G ′ = torso G ( S ′ ) . Let x , y ∈ V ( H ) x,y \in V(H) x , y ∈ V ( H ) . First, B x ′ ≠ ∅ B'_x \ne\emptyset B x ′ = ∅ as B x ∩ S ≠ ∅ B_x \cap S \ne\emptyset B x ∩ S = ∅ . Next, G ′ [ B x ′ ] G'[B'_x] G ′ [ B x ′ ] is connected since G [ B x ] G[B_x] G [ B x ] is connected and for every u , v ∈ B x ′ u,v \in B'_x u , v ∈ B x ′ the restriction to G ′ [ B x ′ ] G'[B'_x] G ′ [ B x ′ ] of a u u u –v v v path in G [ B x ] G[B_x] G [ B x ] is a u u u –v v v path in G ′ [ B x ′ ] G'[B'_x] G ′ [ B x ′ ] . Finally, if B x B_x B x and B y B_y B y are adjacent in G G G , for e ∈ E ( B x ) e \in E(B_x) e ∈ E ( B x ) and v ∈ B y ′ v \in B'_y v ∈ B y ′ there is a u u u –v v v path in G [ B x ∪ B y ] G[B_x \cup B_y] G [ B x ∪ B y ] , hence B x ′ B'_x B x ′ and B y ′ B'_y B y ′ are adjacent in G ′ G' G ′ .
The key implication of Theorem 5 is the following statement.
Observation 6. Let p be a minor-monotone graph parameter. Let H H H be a graph and n n n be an integer such that p ( H ) ≥ n \mathrm{p}(H) \ge n p ( H ) ≥ n . Then, for every annotated graph ( G , S ) (G,S) ( G , S ) such that G G G contains an S S S -rooted minor of H H H , we have p ( G , S ) ≥ n \mathrm{p}(G,S) \ge n p ( G , S ) ≥ n .
Observation 7. Let p be a minor-monotone graph parameter. Then, for all annotated graphs ( H , T ) (H,T) ( H , T ) and ( G , S ) (G,S) ( G , S ) , if ( H , T ) (H,T) ( H , T ) is a minor of ( G , S ) (G,S) ( G , S ) , then p ( H , T ) ≤ p ( G , S ) \mathrm{p}(H,T) \le\mathrm{p}(G,S) p ( H , T ) ≤ p ( G , S ) .
Proof. Let ( B x ∣ x ∈ V ( H ) ) (B_x \mid x \in V(H)) ( B x ∣ x ∈ V ( H )) be a model of ( H , T ) (H,T) ( H , T ) in ( G , S ) (G,S) ( G , S ) . Choose S ⊆ S ′ ⊆ V ( G ) S \subseteq S' \subseteq V(G) S ⊆ S ′ ⊆ V ( G ) such that p ( torso G ( S ′ ) ) = p ( G , S ) \operatorname{p}(\operatorname{torso}_G(S')) = \operatorname{p}(G,S) p ( torso G ( S ′ )) = p ( G , S ) , and put T ′ = { x ∈ V ( H ) : B x ∩ S ′ ≠ ∅ } T' = \{x \in V(H) : B_x \cap S' \ne\varnothing\} T ′ = { x ∈ V ( H ) : B x ∩ S ′ = ∅ } . Since S ⊆ S ′ S \subseteq S' S ⊆ S ′ , we have T ⊆ T ′ T \subseteq T' T ⊆ T ′ . The sets ( B x ∩ S ′ ∣ x ∈ T ′ ) (B_x \cap S' \mid x \in T') ( B x ∩ S ′ ∣ x ∈ T ′ ) form a model of torso H ( T ′ ) \operatorname{torso}_H(T') torso H ( T ′ ) in torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) . This can be proved with a similar argument as in Theorem 5 . Therefore, by the minor-monotonicity of p \operatorname{p} p ,
p ( H , T ) ≤ p ( torso H ( T ′ ) ) ≤ p ( torso G ( S ′ ) ) = p ( G , S ) . \operatorname{p}(H,T) \le\operatorname{p}(\operatorname{torso}_H(T')) \le\operatorname{p}(\operatorname{torso}_G(S')) = \operatorname{p}(G,S). p ( H , T ) ≤ p ( torso H ( T ′ )) ≤ p ( torso G ( S ′ )) = p ( G , S ) .
Annotated obstructions for torso parameters
In this section, we prove Theorem 1 and some other complementary results. Given a graph parameter p \operatorname{p} p , to obtain a statement as in Theorem 1 , one needs two directions. First, one must prove that p \operatorname{p} p can be arbitrarily large on graphs in F p \mathcal{F}_{\operatorname{p}} F p and second, one must prove that if p ( G , S ) \operatorname{p}(G,S) p ( G , S ) is sufficiently large, then ( G , S ) (G,S) ( G , S ) contains as a minor a “large” member of F p \mathcal{F}_{\operatorname{p}} F p . For some of the parameters, we provide an equivalent definition, which is supposed to be more comprehensive than the abstract torso definition.
Treewidth
Treewidth. A tree decomposition of a graph G G G is a pair T = ( T , ( W x ∣ x ∈ V ( T ) ) ) \mathcal{T} = (T,(W_x \mid x \in V(T))) T = ( T , ( W x ∣ x ∈ V ( T ))) , where T T T is a tree and W x ⊆ V ( G ) W_x \subseteq V(G) W x ⊆ V ( G ) for every x ∈ V ( T ) x \in V(T) x ∈ V ( T ) , satisfying the following conditions: (i) for every u ∈ V ( G ) u \in V(G) u ∈ V ( G ) , the graph T [ { x ∈ V ( T ) ∣ u ∈ W x } ] T[\{x \in V(T) \mid u \in W_x\}] T [{ x ∈ V ( T ) ∣ u ∈ W x }] is a connected subgraph of T T T and (ii) for every edge u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) , there exists x ∈ V ( T ) x \in V(T) x ∈ V ( T ) such that u , v ∈ W x u,v \in W_x u , v ∈ W x . The sets W x W_x W x are called the bags of T \mathcal{T} T . The width of T \mathcal{T} T is max { ∣ W x ∣ − 1 ∣ x ∈ V ( T ) } \max\{|W_x| - 1 \mid x \in V(T)\} max { ∣ W x ∣ − 1 ∣ x ∈ V ( T )} . The treewidth of a graph G G G , denoted by tw ( G ) \operatorname{tw}(G) tw ( G ) , is the minimum width of a tree decomposition of G G G .
Since for any graph G G G and X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) , the neighborhood in X X X of a component of G − X G-X G − X is a clique in torso G ( X ) \operatorname{torso}_G(X) torso G ( X ) , we obtain the following observation.
Observation 8. For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , we have tw ( G , S ) ≤ k \operatorname{tw}(G,S) \le k tw ( G , S ) ≤ k if and only if there exists a set S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S \subseteq S' S ⊆ S ′ such that there exists a tree decomposition ( T , ( W x ∣ x ∈ V ( T ) ) ) (T,(W_x \mid x \in V(T))) ( T , ( W x ∣ x ∈ V ( T ))) of m a t h o p e n G [ S ′ ] mathopen{}G[S']\mathclose{} ma t h o p e n G [ S ′ ] of width at most k k k such that for every component of G − S ′ G-S' G − S ′ there exists x ∈ V ( T ) x \in V(T) x ∈ V ( T ) with W x W_x W x containing the neighborhood of the component in G G G .
We call a tree decomposition ( T , ( W x ∣ x ∈ V ( T ) ) ) (T,(W_x \mid x \in V(T))) ( T , ( W x ∣ x ∈ V ( T ))) as in the observation a tree decomposition of ( G , S ) (G,S) ( G , S ) .
Let f ⊟ f_{\boxminus} f ⊟ be the minimum function such that for every positive integer ℓ \ell ℓ , if a graph G G G has no model of the ℓ × ℓ \ell\times\ell ℓ × ℓ grid, then tw ( G ) ≤ f ⊟ ( ℓ ) \operatorname{tw}(G) \le f_{\boxminus}(\ell) tw ( G ) ≤ f ⊟ ( ℓ ) . This function exists due to the Grid Minor Theorem, and the best known upper bound is f ⊟ ( ℓ ) = O ~ ( ℓ 8 ) f_{\boxminus}(\ell) = \widetilde{O}(\ell^8) f ⊟ ( ℓ ) = O ( ℓ 8 ) due to Bonnet [1 ] and Chuzhoy and Tan [3 ] . The following result was given by Hodor, La, Micek, and Rambaud [13 ] .
Theorem 9 ([13 Theorem 8] 2 ). There is a function f 9 : N → N f_9 \colon\mathbb{N} \to\mathbb{N} f 9 : N → N such that the following holds. Let H H H be a plane graph and let T T T be a subset of the outer face of H H H . For every annotated graph ( G , S ) (G,S) ( G , S ) , if tw ( G , S ) ≥ f 9 ( ∣ V ( H ) ∣ ) \operatorname{tw}(G,S) \ge f_9(|V(H)|) tw ( G , S ) ≥ f 9 ( ∣ V ( H ) ∣ ) , then ( G , S ) (G,S) ( G , S ) contains a model of ( H , T ) (H,T) ( H , T ) . Moreover, we can take f 9 ( x ) = 3 f ⊟ ( 98304 ⋅ x 4 ) + 2 f_9(x) = 3f_{\boxminus}(98304 \cdot x^4) + 2 f 9 ( x ) = 3 f ⊟ ( 98304 ⋅ x 4 ) + 2 .
Theorem 9 is proved via tangles of annotated graphs. The main technical part of the proof was stated implicitly by Marx, Seymour, and Wollan [20 statement 1.3] . A complete proof with all the necessary adjustments to the annotated setting can be found in the appendix of [13 ] .
In the further parts of the paper, we will use the following Helly-like property of annotated graphs of bounded torso treewidth. The statement is an extension of [13 Lemma 23] that follows directly from the proof. Given a tree decomposition T = ( T , ( W x ∣ x ∈ V ( T ) ) ) \mathcal{T} = (T,(W_x \mid x \in V(T))) T = ( T , ( W x ∣ x ∈ V ( T ))) of an annotated graph ( G , S ) (G,S) ( G , S ) and a subgraph H H H of G G G intersecting S S S , we define T [ H ] = { x ∈ V ( T ) ∣ W x ∩ V ( H ) ≠ ∅ } \mathcal{T}[H]=\{x\in V(T)\mid W_x\cap V(H)\ne\emptyset\} T [ H ] = { x ∈ V ( T ) ∣ W x ∩ V ( H ) = ∅ } . By the properties of tree decompositions, if H H H is connected, then T [ H ] \mathcal{T}[H] T [ H ] induces a connected subtree of T T T .
Lemma 10 (Extension of [13 Lemma 23] ). Let ( G , S ) (G,S) ( G , S ) be an annotated graph, let S ′ ⊆ V ( G ) S'\subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S\subseteq S' S ⊆ S ′ , let ( T , ( W x ∣ x ∈ V ( T ) ) ) (T,(W_x\mid x\in V(T))) ( T , ( W x ∣ x ∈ V ( T ))) be a tree decomposition of ( G , S ′ ) (G,S') ( G , S ′ ) , and let H \mathcal{H} H be a family of connected subgraphs of G G G each containing a vertex of S S S . For every positive integer k k k , either
(i) there are k k k subgraphs in H \mathcal{H} H so that each two H H H and H ′ H' H ′ satisfy T [ H ] ∩ T [ H ′ ] = ∅ \mathcal{T}[H]\cap\mathcal{T}[H']=\emptyset T [ H ] ∩ T [ H ′ ] = ∅ or
(ii) there is a set X ⊆ V ( T ) X\subseteq V(T) X ⊆ V ( T ) with ∣ X ∣ ≤ k − 1 |X|\leq k-1 ∣ X ∣ ≤ k − 1 such that if Z = ⋃ x ∈ X W x Z=\bigcup_{x\in X}W_x Z = ⋃ x ∈ X W x , then V ( H ) ∩ Z ≠ ∅ V(H)\cap Z\ne\emptyset V ( H ) ∩ Z = ∅ for every H ∈ H H\in\mathcal{H} H ∈ H .
A consequence of Theorem 10 is the following: let G G G be the n × n n\times n n × n grid, and let S S S be the vertex set of the first row of this grid. If H \mathcal{H} H consists of all the subgraphs of G G G induced by the union of a row and a column of G G G , then Theorem 10 for k = 2 k=2 k = 2 implies that there is a set Z Z Z of tw ( G , S ) + 1 \operatorname{tw}(G,S)+1 tw ( G , S ) + 1 vertices intersecting every member of H \mathcal{H} H , and we deduce tw ( G , S ) ≥ n − 1 \operatorname{tw}(G,S)\geq n-1 tw ( G , S ) ≥ n − 1 .
This and Theorem 9 yields the treewidth statement in Theorem 1 .
Pathwidth
A path decomposition of a graph G G G is a tree decomposition ( T , ( W x ∣ x ∈ V ( T ) ) ) (T,(W_x\mid x\in V(T))) ( T , ( W x ∣ x ∈ V ( T ))) of G G G where T T T is a path. The pathwidth of a graph G G G , denoted by pw ( G ) \operatorname{pw}(G) pw ( G ) , is the minimum width of a path decomposition of G G G .
The following observation is the analog of Theorem 8 for path decompositions.
Observation 11. For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , we have pw ( G , S ) ≤ k \operatorname{pw}(G,S)\leq k pw ( G , S ) ≤ k if and only if there exists a set S ′ ⊆ V ( G ) S'\subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S\subseteq S' S ⊆ S ′ such that there exists a path decomposition ( W i ∣ i ∈ [ ℓ ] ) (W_i\mid i\in[\ell]) ( W i ∣ i ∈ [ ℓ ]) of G [ S ′ ] G[S'] G [ S ′ ] of width at most k k k such that for every component of G − S ′ G-S' G − S ′ there exists i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] with W i W_i W i containing the neighborhood of the component in G G G .
The following theorem and Theorem 6 yield the pathwidth statement in Theorem 1 .
Theorem 12 ([13 Theorem 7] ). For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , if pw ( G , S ) ≥ 2 k − 1 \operatorname{pw}(G,S)\geq2k-1 pw ( G , S ) ≥ 2 k − 1 , then ( G , S ) (G,S) ( G , S ) contains an S S S -rooted model of every forest on k k k vertices.
Vertex cover number
The vertex cover number of a graph G G G , denoted by vc ( G ) \operatorname{vc}(G) vc ( G ) , is the minimum number k ∈ N k\in\mathbb{N} k ∈ N for which there is a set X ⊆ V ( G ) X\subseteq V(G) X ⊆ V ( G ) with ∣ X ∣ = k |X|=k ∣ X ∣ = k such that every edge of G G G has at least one endpoint in X X X . Such a set X X X is called a vertex cover in G G G .
Observation 13. For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , we have vc ( G , S ) ≤ k \operatorname{vc}(G,S)\leq k vc ( G , S ) ≤ k , if and only if there exists a set X ⊆ V ( G ) X\subseteq V(G) X ⊆ V ( G ) with ∣ X ∣ ≤ k |X|\leq k ∣ X ∣ ≤ k such that there is no ( S ∖ X ) (S\setminus X) ( S ∖ X ) -rooted model of K 2 K_2 K 2 in G − X G-X G − X .
Proof. Let ( G , S ) (G,S) ( G , S ) be an annotated graph and let k k k be a positive integer. First, assume that vc ( G , S ) ≤ k \operatorname{vc}(G,S)\leq k vc ( G , S ) ≤ k . Consider a vertex subset S ′ ⊆ V ( G ) S'\subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S\subseteq S' S ⊆ S ′ and vc ( torso G ( S ′ ) ) = vc ( G , S ) \operatorname{vc}(\operatorname{torso}_G(S'))=\operatorname{vc}(G,S) vc ( torso G ( S ′ )) = vc ( G , S ) . Let X ⊆ S ′ X\subseteq S' X ⊆ S ′ with ∣ X ∣ ≤ k |X|\leq k ∣ X ∣ ≤ k be such that torso G ( S ′ ) − X \operatorname{torso}_G(S')-X torso G ( S ′ ) − X is edgeless. Suppose that there is an ( S ∖ X ) (S\setminus X) ( S ∖ X ) -rooted minor of K 2 K_2 K 2 in G − X G-X G − X . It follows that there is an s 1 s_1 s 1 -s 2 s_2 s 2 path between distinct vertices s 1 , s 2 ∈ S s_1,s_2\in S s 1 , s 2 ∈ S in G − X G-X G − X and since s 1 , s 2 ∈ S ′ s_1,s_2\in S' s 1 , s 2 ∈ S ′ , there is an s 1 s_1 s 1 -s 2 s_2 s 2 path in torso G ( S ′ ) − X \operatorname{torso}_G(S')-X torso G ( S ′ ) − X , which is a contradiction.
Next, suppose that there exists a set X ⊆ V ( G ) X\subseteq V(G) X ⊆ V ( G ) with ∣ X ∣ ≤ k |X|\leq k ∣ X ∣ ≤ k such that there is no ( S ∖ X ) (S\setminus X) ( S ∖ X ) -rooted model of K 2 K_2 K 2 in G − X G-X G − X . We claim that torso G ( S ∪ X ) − X \operatorname{torso}_G(S\cup X)-X torso G ( S ∪ X ) − X is edgeless. Otherwise, there are two distinct s 1 , s 2 ∈ S ∖ X s_1,s_2\in S\setminus X s 1 , s 2 ∈ S ∖ X connected by an edge in torso G ( S ∪ X ) − X \operatorname{torso}_G(S\cup X)-X torso G ( S ∪ X ) − X . However, this implies that there is an s 1 s_1 s 1 –s 2 s_2 s 2 path in G − X G-X G − X , hence an ( S ∖ X ) (S\setminus X) ( S ∖ X ) -rooted model of K 2 K_2 K 2 , which is again a contradiction. □
Let ( G , A ) (G,A) ( G , A ) be an annotated graph. An A A A -path in G G G is a path with at least two vertices and both ends in A A A . In 1964, Gallai [11 ] proved that either G G G contains k k k disjoint A A A -paths, or there exists a subset X X X of the vertices of G G G with ∣ X ∣ ≤ 2 k − 2 |X| \le2k-2 ∣ X ∣ ≤ 2 k − 2 such that every A A A -path in G G G contains a vertex of X X X . Note that the latter statement (by Theorem 13) is equivalent to vc ( G , A ) ≤ 2 k − 2 \operatorname{vc}(G,A) \le2k-2 vc ( G , A ) ≤ 2 k − 2 . Therefore, we immediately obtain one of the implications of the vertex cover statement in Theorem 1 . The other implication follows from Theorem 6 .
Theorem 14. For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , if vc ( G , S ) ≥ 2 k − 1 \operatorname{vc}(G,S) \ge2k-1 vc ( G , S ) ≥ 2 k − 1 , then G G G contains an S S S -rooted model of the perfect matching on 2 k 2k 2 k vertices.
Feedback vertex number
The feedback vertex number of a graph G G G , denoted by fv ( G ) \operatorname{fv}(G) fv ( G ) , is the minimum number k ∈ N k \in\mathbb{N} k ∈ N for which there is a set X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) with ∣ X ∣ = k |X|=k ∣ X ∣ = k such that G − X G-X G − X is acyclic.
We begin this subsection by proving Theorem 4, which we restate for convenience
Theorem 4. Let C \mathcal{C} C be the class of all forests. For every annotated graph ( G , S ) (G,S) ( G , S ) , we have ( G , S ) ∈ C ∙ (G,S) \in\mathcal{C}^{\bullet} ( G , S ) ∈ C ∙ if and only if K 3 K_3 K 3 is not an S S S -rooted minor of G G G .
Proof. First, note that if ( K 3 , V ( K 3 ) ) (K_3,V(K_3)) ( K 3 , V ( K 3 )) is a minor of an annotated graph ( G , S ) (G,S) ( G , S ) , then by Theorem 5 , K 3 K_3 K 3 is a minor of torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) for every S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S \subseteq S' S ⊆ S ′ , and so ( G , S ) ∉ C ∙ (G,S) \notin\mathcal{C}^{\bullet} ( G , S ) ∈ / C ∙ . Therefore, to conclude the proof, it suffices to show that for every annotated graph ( G , S ) (G,S) ( G , S ) , if ( K 3 , V ( K 3 ) ) (K_3,V(K_3)) ( K 3 , V ( K 3 )) is not a minor of ( G , S ) (G,S) ( G , S ) , then ( G , S ) ∈ C ∙ (G,S) \in\mathcal{C}^{\bullet} ( G , S ) ∈ C ∙ . Let ( G , S ) (G,S) ( G , S ) be an annotated graph with no ( K 3 , V ( K 3 ) ) (K_3,V(K_3)) ( K 3 , V ( K 3 )) minor. By considering each component separately, we may assume without loss of generality that G G G is connected. When S = ∅ S=\varnothing S = ∅ , then ( G , S ) ∈ C ∙ (G,S) \in\mathcal{C}^{\bullet} ( G , S ) ∈ C ∙ , as witnessed by S ′ = ∅ S'=\varnothing S ′ = ∅ . Thus, we may assume that S ≠ ∅ S\ne\varnothing S = ∅ . Let T T T be a connected subgraph of G G G containing S S S and with a minimum number of edges under these constraints. Observe that T T T is a tree. Let B ⊆ V ( T ) B \subseteq V(T) B ⊆ V ( T ) be the set of vertices of degree at least 3 in T T T . We define
S ′ = S ∪ B . S'=S\cup B. S ′ = S ∪ B .
We shall prove that torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) is a forest witnessing that ( G , S ′ ) ∈ C ∙ (G,S') \in\mathcal{C}^{\bullet} ( G , S ′ ) ∈ C ∙ . To do so, we first prove the following:
Claim 15. For every vertex u ∈ S ′ u \in S' u ∈ S ′ , for every pair of distinct components T 1 , T 2 T_1,T_2 T 1 , T 2 of T − u T-u T − u , the sets V ( T 1 ) V(T_1) V ( T 1 ) and V ( T 2 ) V(T_2) V ( T 2 ) lie in distinct components of G − u G-u G − u .
Proof of the claim. Let u ∈ S ′ u \in S' u ∈ S ′ . Suppose for contradiction that there is a path P P P in G − u G-u G − u between V ( T 1 ) V(T_1) V ( T 1 ) and V ( T 2 ) V(T_2) V ( T 2 ) for two components T 1 T_1 T 1 and T 2 T_2 T 2 of T − u T-u T − u . By possibly replacing T 2 T_2 T 2 by the first component of T − u T-u T − u intersecting P P P after T 1 T_1 T 1 , we assume that T 1 T_1 T 1 and T 2 T_2 T 2 are the only components of T − u T-u T − u intersecting P P P . We denote by U U U the set of all the internal vertices of P P P . If u ∈ B u \in B u ∈ B (i.e. u u u has degree more than 2 in T T T ), then there is a component T 3 T_3 T 3 of T − u T-u T − u distinct from T 1 T_1 T 1 and T 2 T_2 T 2 , and we set A = { u } ∪ V ( T 3 ) A=\{u\}\cup V(T_3) A = { u } ∪ V ( T 3 ) . Note that by the minimality of T T T , T 3 T_3 T 3 contains a vertex in S S S . Otherwise, u u u is in S S S , and we set A = { u } A=\{u\} A = { u } . In both cases, A A A is a set of vertices that induces a connected subgraph of G G G , and that contains both u u u and a vertex of S S S . Consider ( V ( T 1 ) ∪ U , V ( T 2 ) , A ) (V(T_1)\cup U,V(T_2),A) ( V ( T 1 ) ∪ U , V ( T 2 ) , A ) . By construction, it is a model of K 3 K_3 K 3 . Moreover, by minimality of E ( T ) E(T) E ( T ) , V ( T 1 ) V(T_1) V ( T 1 ) and V ( T 2 ) V(T_2) V ( T 2 ) both intersect S S S . Since A A A also intersects S S S , this model is S S S -rooted. This contradiction proves the claim. ◇
Now, let E ′ = { u v ∣ u , v ∈ S ′ , vertices between u and v in T are not in S ′ } E' = \{uv \mid u,v \in S',\text{ vertices between }u\text{ and }v\text{ in }T\text{ are not in }S'\} E ′ = { uv ∣ u , v ∈ S ′ , vertices between u and v in T are not in S ′ } , and observe that T T T is a subdivision of ( S ′ , E ′ ) (S',E') ( S ′ , E ′ ) . In particular, ( S ′ , E ′ ) (S',E') ( S ′ , E ′ ) is a tree. We claim that ( S ′ , E ′ ) (S',E') ( S ′ , E ′ ) is exactly torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) . By definition, E ′ ⊆ E ( torso G ( S ′ ) ) E' \subseteq E(\operatorname{torso}_G(S')) E ′ ⊆ E ( torso G ( S ′ )) . Suppose now that there is u v ∈ E ( torso G ( S ′ ) ) uv \in E(\operatorname{torso}_G(S')) uv ∈ E ( torso G ( S ′ )) such that u v ∉ E ′ uv \notin E' uv ∈ / E ′ . Then there is w ∈ S ′ w \in S' w ∈ S ′ between u u u and v v v in T T T . By Theorem 15, the components T u T_u T u and T v T_v T v of T − w T-w T − w containing u u u and v v v respectively lie in distinct components of G − w G-w G − w . Therefore, there is no edge between u u u and v v v in torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) , a contradiction. This proves that torso G ( S ′ ) = ( S ′ , E ′ ) \operatorname{torso}_G(S') = (S',E') torso G ( S ′ ) = ( S ′ , E ′ ) , and so is a forest.
Theorem 4 implies the following description of annotated graphs ( G , S ) (G,S) ( G , S ) with fv ( G , S ) ≤ k \operatorname{fv}(G,S) \le k fv ( G , S ) ≤ k .
Corollary 16. For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , we have fv ( G , S ) ≤ k \operatorname{fv}(G,S) \le k fv ( G , S ) ≤ k , if and only if there exists a set X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) with ∣ X ∣ ≤ k |X| \le k ∣ X ∣ ≤ k such that there is no ( S ∖ X ) (S\setminus X) ( S ∖ X ) -rooted model of K 3 K_3 K 3 in G − X G-X G − X .
Proof. Let ( G , S ) (G,S) ( G , S ) be an annotated graph and k k k be a positive integer. First, assume that fv ( G , S ) ≤ k \operatorname{fv}(G,S) \le k fv ( G , S ) ≤ k . Let S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S \subseteq S' S ⊆ S ′ be such that fv ( torso G ( S ′ ) ) = fv ( G , S ) \operatorname{fv}(\operatorname{torso}_G(S')) = \operatorname{fv}(G,S) fv ( torso G ( S ′ )) = fv ( G , S ) and let X ⊆ S ′ X \subseteq S' X ⊆ S ′ with ∣ X ∣ ≤ k |X| \le k ∣ X ∣ ≤ k be such that torso G ( S ′ ) − X \operatorname{torso}_G(S')-X torso G ( S ′ ) − X is a forest. Then, by Theorem 4, G − X G-X G − X has no ( S ∖ X ) (S\setminus X) ( S ∖ X ) -rooted model of K 3 K_3 K 3 .
Otherwise, assume there is X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) with ∣ X ∣ ≤ k |X| \le k ∣ X ∣ ≤ k such that there is no ( S ∖ X ) (S\setminus X) ( S ∖ X ) -rooted model of K 3 K_3 K 3 in G − X G-X G − X . By Theorem 4, ( G − X , S ∖ X ) ∈ C ∙ (G-X,S\setminus X) \in\mathcal{C}^{\bullet} ( G − X , S ∖ X ) ∈ C ∙ . Hence, there is S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) with ( S ∖ X ) ⊆ S ′ (S\setminus X) \subseteq S' ( S ∖ X ) ⊆ S ′ such that torso G − X ( S ′ ) \operatorname{torso}_{G-X}(S') torso G − X ( S ′ ) is a forest, and so fv ( torso G ( S ′ ∪ X ) ) ≤ ∣ X ∣ ≤ k \operatorname{fv}(\operatorname{torso}_G(S' \cup X)) \le|X| \le k fv ( torso G ( S ′ ∪ X )) ≤ ∣ X ∣ ≤ k .
We next show that if fv ( G , S ) \operatorname{fv}(G,S) fv ( G , S ) is large, then G G G contains a large collection of disjoint K 3 K_3 K 3 's as S S S -rooted minors. The reverse implication is an immediate corollary of Theorem 16 (combined with Theorem 6 ). This way, we obtain the feedback vertex number statement in Theorem 1 .
Theorem 17. There exists a function f 17 f_{17} f 17 such that for every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , if fv ( G , S ) ≥ f 17 ( k ) \operatorname{fv}(G,S) \ge f_{17}(k) fv ( G , S ) ≥ f 17 ( k ) , then ( G , S ) (G,S) ( G , S ) contains an S S S -rooted model of H k H_k H k , where H k H_k H k is k k k disjoint copies of K 3 K_3 K 3 .
Proof. Let k k k be a positive integer and let g ( k ) = f 9 ( ∣ V ( H k ) ∣ ) g(k) = f_9(|V(H_k)|) g ( k ) = f 9 ( ∣ V ( H k ) ∣ ) be the value given by Theorem 9 such that for every annotated graph ( G , S ) (G,S) ( G , S ) if tw ( G , S ) ≥ g ( k ) \operatorname{tw}(G,S) \ge g(k) tw ( G , S ) ≥ g ( k ) , then ( G , S ) (G,S) ( G , S ) contains an S S S -rooted model of H k H_k H k . Note that H k H_k H k is a planar graph admitting a plane embedding where all the vertices are in the outer face. We define f 17 ( k ) = ( k − 1 ) g ( k ) + 1 f_{17}(k) = (k-1)g(k)+1 f 17 ( k ) = ( k − 1 ) g ( k ) + 1 .
Let ( G , S ) (G,S) ( G , S ) be an annotated graph with fv ( G , S ) ≥ f 17 ( k ) \operatorname{fv}(G,S) \ge f_{17}(k) fv ( G , S ) ≥ f 17 ( k ) . If tw ( G , S ) ≥ g ( k ) \operatorname{tw}(G,S) \ge g(k) tw ( G , S ) ≥ g ( k ) , then by Theorem 9 , ( G , S ) (G,S) ( G , S ) contains an S S S -rooted model of H k H_k H k , as desired. Thus, we assume that tw ( G , S ) < g ( k ) \operatorname{tw}(G,S) < g(k) tw ( G , S ) < g ( k ) . Let H \mathcal{H} H be the family of the unions of branch sets of S S S -rooted models of K 3 K_3 K 3 in ( G , S ) (G,S) ( G , S ) . By Theorem 10 applied to a tree decomposition of width tw ( G , S ) \operatorname{tw}(G,S) tw ( G , S ) , either there are k k k disjoint members of H \mathcal{H} H and so H k H_k H k is an S S S -rooted minor of G G G , or there exists a set X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) with ∣ X ∣ ≤ ( k − 1 ) g ( k ) |X| \le(k-1)g(k) ∣ X ∣ ≤ ( k − 1 ) g ( k ) such that every subgraph in H \mathcal{H} H contains a vertex of X X X . Suppose we are in the latter case. In particular, ( G − X , S ∖ X ) (G-X,S\setminus X) ( G − X , S ∖ X ) has no S ∖ X S\setminus X S ∖ X -rooted model of K 3 K_3 K 3 . Therefore, Theorem 16 implies that fv ( G , S ) ≤ ∣ X ∣ < f 17 ( k ) \operatorname{fv}(G,S) \le|X| < f_{17}(k) fv ( G , S ) ≤ ∣ X ∣ < f 17 ( k ) .
Treedepth
A rooted forest is a disjoint union of rooted trees. The vertex-height of a rooted forest F F F is the maximum number of vertices on a path from a root to a leaf in F F F , and the depth of a vertex u ∈ V ( F ) u \in V(F) u ∈ V ( F ) is the number of vertices in the path between u u u and the root of its component. For two vertices u , v u,v u , v in a rooted forest F F F , we say that u u u is a descendant of v v v in F F F if v v v lies on the path from a root to u u u in $F. The closure of F F F is the graph with vertex set V ( F ) V(F) V ( F ) and edge set { v w ∣ v ≠ w and v is a descendant of w in F } \{vw \mid v \ne w\text{ and }v\text{ is a descendant of }w\text{ in }F\} { v w ∣ v = w and v is a descendant of w in F } . We say that F F F is an elimination forest of G G G if V ( F ) = V ( G ) V(F)=V(G) V ( F ) = V ( G ) and G G G is a subgraph of the closure of F F F . The treedepth of a graph G G G , denoted by td ( G ) \operatorname{td}(G) td ( G ) , is 0 if V ( G ) V(G) V ( G ) is empty, and otherwise is the minimum vertex-height of an elimination forest of G G G .
The following observation is straightforward.
Observation 18. For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , we have td ( G , S ) ≤ k \operatorname{td}(G,S) \le k td ( G , S ) ≤ k if and only if there exists a set S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S \subseteq S' S ⊆ S ′ , and a rooted forest F F F of height at most k k k with G [ S ′ ] G[S'] G [ S ′ ] being a subgraph of the closure of F F F , such that, for every component C C C of G − S ′ G-S' G − S ′ , there exists a root-to-leaf path in F F F containing the neighborhood of V ( C ) V(C) V ( C ) in G G G .
Hodor, La, Micek, and Rambaud [13 Theorem 6] proved that if for an annotated graph ( G , S ) (G,S) ( G , S ) , we have td ( G , S ) > ( k 2 ) \operatorname{td}(G,S) > \binom{k}{2} td ( G , S ) > ( 2 k ) , then ( G , S ) (G,S) ( G , S ) contains ( P k , V ( P k ) ) (P_k,V(P_k)) ( P k , V ( P k )) as a minor. Later, this quadratic bound was improved to linear by Claus, Hodor, Joret, and Morin [4 Theorem 3] .
Theorem 19 ([4 Theorem 3] ). For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , if td ( G , S ) ≥ 2 k − 1 \operatorname{td}(G,S) \ge2k-1 td ( G , S ) ≥ 2 k − 1 , then $G contains an S S S -rooted model of a path on $k vertices.
As already mentioned, a drawback of characterizing classes of bounded treedepth by forbidding paths as minors (or equivalently subgraphs) is that they have logarithmic treedepth themselves. Kawarabayashi and Rossman [17 ] found obstructions for bounded treedepth that have polynomial treedepth. The precise bounds were later improved by Czerwiński, Nadara, and Pilipczuk, see Theorem 20 below. Recall that a full binary tree is a rooted tree where each vertex has either two or no children and all leaves have the same depth.
Theorem 20 ([7 Corollary 1.5] ). There exists an absolute constant C C C such that for all positive integers a a a , b b b , and c c c , if a graph G G G has treedepth at least C ⋅ a b c C \cdot abc C ⋅ ab c , then one of the following conditions hold:
(i) G G G has treewidth at least a a a ,
(ii) G G G contains a subdivision of a full binary tree of vertex-height b b b as a subgraph, or
(iii) G G G contains a path on 2 c 2^c 2 c vertices as a subgraph.
We derive an annotated variant of Theorem 20 .
Theorem 21. There exists an absolute constant C C C such that for all positive integers a a a , b b b , and c c c , if an annotated graph ( G , S ) (G,S) ( G , S ) satisfies td ( G , S ) ≥ C ⋅ a b c \operatorname{td}(G,S) \ge C \cdot abc td ( G , S ) ≥ C ⋅ ab c , then one of the following conditions hold:
(i) tw ( G , S ) ≥ a \operatorname{tw}(G,S) \ge a tw ( G , S ) ≥ a ,
(ii) G G G contains a full binary tree of vertex-height b b b as an S S S -rooted minor, or
(iii) G G G contains a path on 2 c 2^c 2 c vertices as an S S S -rooted minor.
Lemma 22 (based on [7 Theorem 4.1] ). Let ( G , S ) (G,S) ( G , S ) be an annotated graph, and let a a a and d d d be positive integers. If td ( G , S ) > a d \operatorname{td}(G,S) > ad td ( G , S ) > a d , then either tw ( G , S ) ≥ a \operatorname{tw}(G,S) \ge a tw ( G , S ) ≥ a or $G contains an S S S -rooted model of a tree of treedepth greater than d d d .
Proof. By contraposition, we prove that if tw ( G , S ) < a \operatorname{tw}(G,S) < a tw ( G , S ) < a and there is no S S S -rooted model of a tree T T T in G G G with td ( T ) > d \operatorname{td}(T) > d td ( T ) > d , then td ( G , S ) ≤ a d \operatorname{td}(G,S) \le ad td ( G , S ) ≤ a d . The proof is by induction on d d d . If d = 1 d=1 d = 1 , then the fact that there is no S S S -rooted model of a tree T T T in G G G with td ( T ) > 1 \operatorname{td}(T)>1 td ( T ) > 1 implies that every component of G G G has at most one vertex in S S S . This implies that td ( G , S ) ≤ 1 \operatorname{td}(G,S) \le1 td ( G , S ) ≤ 1 , as desired.
Thus, we assume that d > 1 d>1 d > 1 and without loss of generality, we also assume that G G G is connected. Let B \mathcal{B} B be the collection of all connected subgraphs of G G G that contain an S S S -rooted model of a tree of treedepth exactly d d d . We claim that each two distinct B 1 B_1 B 1 and B 2 B_2 B 2 in B \mathcal{B} B intersect. Suppose to the contrary that some distinct B 1 B_1 B 1 and B 2 B_2 B 2 in B \mathcal{B} B are disjoint. For each i ∈ [ 2 ] i \in[2] i ∈ [ 2 ] , let M i \mathcal{M}_i M i be an ( S ∩ V ( B i ) ) (S \cap V(B_i)) ( S ∩ V ( B i )) -rooted model of a tree T i T_i T i with td ( T i ) = d \operatorname{td}(T_i) = d td ( T i ) = d . Since G G G is connected, and B 1 B_1 B 1 and B 2 B_2 B 2 are disjoint, by extending one of the branch sets of M 1 \mathcal{M}_1 M 1 and combining with M 2 \mathcal{M}_2 M 2 , we obtain an S S S -rooted model M \mathcal{M} M of a tree T T T , which is obtained from the disjoint union of T 1 T_1 T 1 and T 2 T_2 T 2 by adding an edge between an appropriate vertex of T 1 T_1 T 1 and an appropriate vertex of T 2 T_2 T 2 . Observe that T T T has treedepth at least d + 1 d+1 d + 1 . This contradicts the assumption, and proves that each two distinct B 1 B_1 B 1 and B 2 B_2 B 2 in B \mathcal{B} B intersect.
Let ( T , ( W x ∣ x ∈ V ( T ) ) ) (T,(W_x \mid x \in V(T))) ( T , ( W x ∣ x ∈ V ( T ))) be a tree decomposition of ( G , S ) (G,S) ( G , S ) of width less than a a a . By Theorem 10 for k = 2 k=2 k = 2 , there exists t ∈ V ( T ) t \in V(T) t ∈ V ( T ) such that W t ∩ V ( B ) ≠ ∅ W_t \cap V(\mathcal{B}) \ne\varnothing W t ∩ V ( B ) = ∅ for every B ∈ B B \in\mathcal{B} B ∈ B . Therefore, by the definition of B \mathcal{B} B , every tree T ′ T' T ′ such that G − W t G-W_t G − W t contains an S S S -rooted model of T ′ T' T ′ satisfies td ( T ′ ) < d \operatorname{td}(T') < d td ( T ′ ) < d . By the inductive hypothesis, the treedepth of ( G − W t , S ∖ W t ) (G-W_t,S\setminus W_t) ( G − W t , S ∖ W t ) is at most a ⋅ ( d − 1 ) a\cdot(d-1) a ⋅ ( d − 1 ) . Finally,
td ( G , S ) ≤ td ( G − W t , S ∖ W t ) + ∣ W t ∣ ≤ a ⋅ ( d − 1 ) + a ≤ a d . \operatorname{td}(G,S) \le\operatorname{td}(G-W_t,S\setminus W_t)+|W_t| \le a\cdot(d-1)+a \le ad. td ( G , S ) ≤ td ( G − W t , S ∖ W t ) + ∣ W t ∣ ≤ a ⋅ ( d − 1 ) + a ≤ a d .
The proof of Theorem 21 makes also use of the following two results.
Lemma 23 ([7 Lemma 1.6] ). There exists an absolute constant D > 0.43 D>0.43 D > 0.43 such that for every positive integer d d d , every tree of treedepth more than d d d contains a subcubic subtree of treedepth more than D d Dd D d .
Lemma 24 ([17 Lemma 5.10] ). For all positive integers b b b and c c c , every tree with td ( T ) > b ( c + 2 ) \operatorname{td}(T)>b(c+2) td ( T ) > b ( c + 2 ) either contains a subdivision of a full binary tree of vertex-height b b b as a subgraph or contains a path on 2 c 2^c 2 c vertices as a subgraph.
Proof of Theorem 21. Let D D D be the constant from Theorem 23. We show that if an annotated graph ( G , S ) (G,S) ( G , S ) has treedepth more than ⌈ 1 D b ( c + 2 ) ⌉ a \lceil\frac{1}{D}b(c+2)\rceil a ⌈ D 1 b ( c + 2 )⌉ a , then one of (i), (ii), and (iii) holds. This implies the statement with C = 3 ⋅ 1 D + 1 C=3\cdot\frac{1}{D}+1 C = 3 ⋅ D 1 + 1 . With d = ⌈ 1 D b ( c + 2 ) ⌉ d=\lceil\frac{1}{D}b(c+2)\rceil d = ⌈ D 1 b ( c + 2 )⌉ , by Theorem 22, td ( G , S ) > d a \operatorname{td}(G,S)>da td ( G , S ) > d a implies that either tw ( G , S ) ≥ a \operatorname{tw}(G,S)\ge a tw ( G , S ) ≥ a or G G G contains an S S S -rooted model of a tree T T T in G G G with td ( T ) > d \operatorname{td}(T)>d td ( T ) > d . If the former holds, then we obtain (i), hence assume the latter. By Theorem 23, T T T contains a subcubic subtree T ′ T' T ′ with td ( T ′ ) > D d ≥ b ( c + 2 ) \operatorname{td}(T')>Dd\ge b(c+2) td ( T ′ ) > D d ≥ b ( c + 2 ) . By Theorem 24, T ′ T' T ′ contains either a subdivision of a full binary tree of vertex-height b b b as a subgraph or a path on 2 c 2^c 2 c vertices as a subgraph. Since G G G contains an S S S -rooted model of T T T , G G G contains either an S S S -rooted model of a full binary tree of vertex-height b b b , or an S S S -rooted model of a path on 2 c 2^c 2 c vertices. In the former case, (ii) holds, and in the latter case, (iii) holds, which ends the proof.
2-treedepth
We next give the definition of 2-treedepth, which was introduced by Huyhn, Joret, Micek, Seweryn, and Wollan [14 ] . The 2-treedepth of a graph G G G , denoted by td 2 ( G ) \operatorname{td}_2(G) td 2 ( G ) , is defined recursively as
(t1) td 2 ( G ) = 0 \operatorname{td}_2(G)=0 td 2 ( G ) = 0 if G G G is the null graph;
(t2) td 2 ( G ) = max B td 2 ( B ) \operatorname{td}_2(G)=\max_{B}\operatorname{td}_2(B) td 2 ( G ) = max B td 2 ( B ) over all the blocks3 B B B of G G G , if G G G has more than one block; and
(t3) td 2 ( G ) = 1 + min u ∈ V ( G ) td 2 ( G − u ) \operatorname{td}_2(G)=1+\min_{u\in V(G)}\operatorname{td}_2(G-u) td 2 ( G ) = 1 + min u ∈ V ( G ) td 2 ( G − u ) if G G G has exactly one block.
The following simple observation follows from studying the definitions.
Observation 25. For every annotated graph ( G , S ) (G,S) ( G , S ) with S ≠ ∅ S\ne\varnothing S = ∅ and 2-connected G G G , we have
td 2 ( G , S ) = 1 + min u ∈ V ( G ) td 2 ( G − { u } , S ∖ { u } ) . \operatorname{td}_2(G,S)=1+\min_{u\in V(G)}\operatorname{td}_2(G-\{u\},S\setminus\{u\}). td 2 ( G , S ) = 1 + u ∈ V ( G ) min td 2 ( G − { u } , S ∖ { u }) .
For every positive integer k k k , let L k L_k L k be the 2 × k 2 \times k 2 × k grid, and let T k T_k T k be the vertex set of its first row. See Figure 1 . It is easy to see that td 2 ( L 2 ℓ , T 2 ℓ ) ≥ ℓ \operatorname{td}_2(L_{2^\ell},T_{2^\ell}) \ge\ell td 2 ( L 2 ℓ , T 2 ℓ ) ≥ ℓ : by induction, this is clear for ℓ = 1 \ell=1 ℓ = 1 , and for ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 , by Theorem 25, there is a vertex u u u such that td 2 ( L 2 ℓ − u , T 2 ℓ ∖ { u } ) + 1 = td 2 ( L 2 ℓ , T 2 ℓ ) \operatorname{td}_2(L_{2^\ell}-u,T_{2^\ell}\setminus\{u\})+1=\operatorname{td}_2(L_{2^\ell},T_{2^\ell}) td 2 ( L 2 ℓ − u , T 2 ℓ ∖ { u }) + 1 = td 2 ( L 2 ℓ , T 2 ℓ ) . Since ( L 2 ℓ − 1 , T 2 ℓ − 1 ) (L_{2^{\ell-1}},T_{2^{\ell-1}}) ( L 2 ℓ − 1 , T 2 ℓ − 1 ) is a minor of ( L 2 ℓ − u , T 2 ℓ ∖ { u } ) (L_{2^\ell}-u,T_{2^\ell}\setminus\{u\}) ( L 2 ℓ − u , T 2 ℓ ∖ { u }) , we deduce td 2 ( L 2 ℓ , T 2 ℓ ) ≥ td 2 ( L 2 ℓ − 1 , T 2 ℓ − 1 ) + 1 \operatorname{td}_2(L_{2^\ell},T_{2^\ell}) \ge\operatorname{td}_2(L_{2^{\ell-1}},T_{2^{\ell-1}})+1 td 2 ( L 2 ℓ , T 2 ℓ ) ≥ td 2 ( L 2 ℓ − 1 , T 2 ℓ − 1 ) + 1 . This proves that the family ( L k , T k ) (L_k,T_k) ( L k , T k ) for k ∈ N k \in\mathbb{N} k ∈ N has unbounded 2 2 2 -treedepth.
Figure 1. The annotated graph ( L 6 , T 6 ) (L_6,T_6) ( L 6 , T 6 ) . Vertices in T 6 T_6 T 6 are depicted in red.
Theorem 26. There exists a function f f f such that for every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , if td 2 ( G , S ) ≥ f ( k ) \operatorname{td}_2(G,S) \ge f(k) td 2 ( G , S ) ≥ f ( k ) , then ( G , S ) (G,S) ( G , S ) contains a model of ( L k , T k ) (L_k,T_k) ( L k , T k ) .
To prove Theorem 26 , we introduce a few supplementary definitions (see Figure 2 for their illustration). Let G G G be a graph, let P P P be a path in G G G , and let H \mathcal{H} H be a family of pairwise disjoint subgraphs of G G G , each intersecting P P P . For every H ∈ H H \in\mathcal{H} H ∈ H we define J P H ( H ) J_P^{\mathcal{H}}(H) J P H ( H ) to be the shortest subpath of P P P containing V ( P ) ∩ V ( H ) V(P)\cap V(H) V ( P ) ∩ V ( H ) , and we define I P H ( H ) I_P^{\mathcal{H}}(H) I P H ( H ) to be the set of maximal subpaths of P P P such that each subpath has both endpoints in V ( H ) V(H) V ( H ) and contains no vertices of any H ′ ∈ H ∖ { H } H' \in\mathcal{H}\setminus\{H\} H ′ ∈ H ∖ { H } . Note that ⋃ { V ( Q ) ∣ Q ∈ I P H ( H ) } ⊆ V ( J P H ( H ) ) \bigcup\{V(Q)\mid Q\in I_P^{\mathcal{H}}(H)\}\subseteq V(J_P^{\mathcal{H}}(H)) ⋃ { V ( Q ) ∣ Q ∈ I P H ( H )} ⊆ V ( J P H ( H )) . When H \mathcal{H} H is clear from the context, we will simply write J P ( H ) J_P(H) J P ( H ) for J P H ( H ) J_P^{\mathcal{H}}(H) J P H ( H ) and I P ( H ) I_P(H) I P ( H ) for I P H ( H ) I_P^{\mathcal{H}}(H) I P H ( H ) .
Figure 2. Illustration for the definitions of J P H ( H ) \mathcal{J}^{H}_{P}(H) J P H ( H ) and I P H ( H ) \mathcal{I}^{H}_{P}(H) I P H ( H ) .
The goal of the following lemmas is to prove Theorem 31, which will be used several times in the proof of Theorem 26 . This is inspired by [23 Lemma 16] .
Lemma 27. Let ( G , S ) (G,S) ( G , S ) be an annotated graph. For every block B B B of G G G , let
S B : = { v ∈ V ( B ) ∣ there exists a v – S path P in G with V ( P ) ∩ V ( B ) = { v } } . S_B:=\{v\in V(B)\mid\text{there exists a }v\text{--}S\text{ path }P\text{ in }G\text{ with }V(P)\cap V(B)=\{v\}\}. S B := { v ∈ V ( B ) ∣ there exists a v – S path P in G with V ( P ) ∩ V ( B ) = { v }} . Then
td 2 ( G , S ) = max { td 2 ( B , S B ) ∣ B is a block of G } . \operatorname{td}_2(G,S)=\max\{\operatorname{td}_2(B,S_B)\mid B\text{ is a block of }G\}. td 2 ( G , S ) = max { td 2 ( B , S B ) ∣ B is a block of G } . Moreover, if an annotated graph ( H , T ) (H,T) ( H , T ) is a minor of ( B , S B ) (B,S_B) ( B , S B ) for some block B B B of G G G , then ( H , T ) (H,T) ( H , T ) is a minor of ( G , S ) (G,S) ( G , S ) .
Proof. We first prove an auxiliary observation. Suppose that G 1 G_1 G 1 and G 2 G_2 G 2 are connected subgraphs of G G G such that G = G 1 ∪ G 2 G=G_1\cup G_2 G = G 1 ∪ G 2 and ∣ V ( G 1 ) ∩ V ( G 2 ) ∣ = 1 \lvert V(G_1)\cap V(G_2)\rvert=1 ∣ V ( G 1 ) ∩ V ( G 2 )∣ = 1 . Let v v v be the common vertex of G 1 G_1 G 1 and G 2 G_2 G 2 . For { i , j } = [ 2 ] \{i,j\}=[2] { i , j } = [ 2 ] , define
S i = ( S ∩ V ( G i ) ) ∪ { { v } , if S ∩ ( V ( G j ) ∖ { v } ) ≠ ∅ , ∅ , otherwise . S_i=(S\cap V(G_i))\cup
\begin{cases}
\{v\}, & \text{if }S\cap(V(G_j)\setminus\{v\})\ne\varnothing,\\
\varnothing, & \text{otherwise}.
\end{cases} S i = ( S ∩ V ( G i )) ∪ { { v } , ∅ , if S ∩ ( V ( G j ) ∖ { v }) = ∅ , otherwise .
We claim that
td 2 ( G , S ) = max { td 2 ( G 1 , S 1 ) , td 2 ( G 2 , S 2 ) } . (1) \operatorname{td}_2(G,S)=\max\{\operatorname{td}_2(G_1,S_1),\operatorname{td}_2(G_2,S_2)\}. \tag*{(1)} td 2 ( G , S ) = max { td 2 ( G 1 , S 1 ) , td 2 ( G 2 , S 2 )} . (1)
If S = ∅ S=\varnothing S = ∅ , then both sides of (1) are equal to 0 0 0 , so suppose that S ≠ ∅ S\ne\varnothing S = ∅ . We first prove the upper bound. Suppose first that S ∩ V ( G 1 ) = ∅ S\cap V(G_1)=\varnothing S ∩ V ( G 1 ) = ∅ . Then v ∉ S v\notin S v ∈ / S , S 1 = { v } S_1=\{v\} S 1 = { v } , and S 2 = S S_2=S S 2 = S . Let S 2 ′ ⊆ S 2 S'_2\subseteq S_2 S 2 ′ ⊆ S 2 be such that td 2 ( torso G 2 ( S 2 ′ ) ) = td 2 ( G 2 , S 2 ) \operatorname{td}_2(\operatorname{torso}_{G_2}(S'_2))=\operatorname{td}_2(G_2,S_2) td 2 ( torso G 2 ( S 2 ′ )) = td 2 ( G 2 , S 2 ) . Since S 2 ′ ⊆ V ( G 2 ) S'_2\subseteq V(G_2) S 2 ′ ⊆ V ( G 2 ) , we have torso G ( S 2 ′ ) = torso G 2 ( S 2 ′ ) \operatorname{torso}_{G}(S'_2)=\operatorname{torso}_{G_2}(S'_2) torso G ( S 2 ′ ) = torso G 2 ( S 2 ′ ) . Indeed, a path between two vertices of G 2 G_2 G 2 cannot use G 1 − { v } G_1-\{v\} G 1 − { v } without visiting v v v twice. Hence td 2 ( G , S ) ≤ td 2 ( G 2 , S 2 ) \operatorname{td}_2(G,S)\le\operatorname{td}_2(G_2,S_2) td 2 ( G , S ) ≤ td 2 ( G 2 , S 2 ) . Moreover, td 2 ( G 1 , S 1 ) = 1 \operatorname{td}_2(G_1,S_1)=1 td 2 ( G 1 , S 1 ) = 1 , while td 2 ( G 2 , S 2 ) ≥ 1 \operatorname{td}_2(G_2,S_2)\ge1 td 2 ( G 2 , S 2 ) ≥ 1 , and consequently td 2 ( G , S ) ≤ max { td 2 ( G 1 , S 1 ) , td 2 ( G 2 , S 2 ) } \operatorname{td}_2(G,S)\le\max\{\operatorname{td}_2(G_1,S_1),\operatorname{td}_2(G_2,S_2)\} td 2 ( G , S ) ≤ max { td 2 ( G 1 , S 1 ) , td 2 ( G 2 , S 2 )} . The case S ∩ V ( G 2 ) = ∅ S\cap V(G_2)=\varnothing S ∩ V ( G 2 ) = ∅ is symmetric.
We may therefore assume that S S S intersects both V ( G 1 ) V(G_1) V ( G 1 ) and V ( G 2 ) V(G_2) V ( G 2 ) . For each i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] , let S i ⊆ S i ′ S_i\subseteq S'_i S i ⊆ S i ′ be such that td 2 ( torso G i ( S i ′ ) ) = td 2 ( G i , S i ) \operatorname{td}_2(\operatorname{torso}_{G_i}(S'_i))=\operatorname{td}_2(G_i,S_i) td 2 ( torso G i ( S i ′ )) = td 2 ( G i , S i ) . Let S ′ = S 1 ′ ∪ S 2 ′ S'=S'_1\cup S'_2 S ′ = S 1 ′ ∪ S 2 ′ and note that v ∈ S 1 ′ ∩ S 2 ′ v\in S'_1\cap S'_2 v ∈ S 1 ′ ∩ S 2 ′ . Additionally,
torso G ( S ′ ) = torso G 1 ( S 1 ′ ) ∪ torso G 2 ( S 2 ′ ) , \operatorname{torso}_{G}(S')=\operatorname{torso}_{G_1}(S'_1)\cup\operatorname{torso}_{G_2}(S'_2), torso G ( S ′ ) = torso G 1 ( S 1 ′ ) ∪ torso G 2 ( S 2 ′ ) ,
and the two graphs on the right-hand side intersect only in v v v . Since every block of the graph on the right-hand side is contained in one of its two parts, the definition of 2-treedepth gives
td 2 ( torso G ( S ′ ) ) = max i ∈ [ 2 ] td 2 ( torso G i ( S i ′ ) ) . \operatorname{td}_2(\operatorname{torso}_{G}(S'))=\max_{i\in[2]}\operatorname{td}_2(\operatorname{torso}_{G_i}(S'_i)). td 2 ( torso G ( S ′ )) = i ∈ [ 2 ] max td 2 ( torso G i ( S i ′ )) .
Consequently,
td 2 ( G , S ) ≤ max { td 2 ( G 1 , S 1 ) , td 2 ( G 2 , S 2 ) } . \operatorname{td}_2(G,S)\leq\max\{\operatorname{td}_2(G_1,S_1),\operatorname{td}_2(G_2,S_2)\}. td 2 ( G , S ) ≤ max { td 2 ( G 1 , S 1 ) , td 2 ( G 2 , S 2 )} .
The reverse inequality follows from Theorem 7 , thus, we obtain (1) .
We now prove the first assertion of the lemma. Without loss of generality, we may assume that G G G is connected.
We proceed by induction on the number of blocks of G G G . If G G G has a single block B B B , then B = G B=G B = G and S B = S S_B=S S B = S , so there is nothing to prove. Suppose now that G G G has at least two blocks. Let B 0 B_0 B 0 be a leaf block of the block-cut tree of G G G , and let v v v be the unique cutvertex of G G G contained in B 0 B_0 B 0 . Let G ′ G' G ′ be the union of all blocks of G G G different from B 0 B_0 B 0 . Then G = B 0 ∪ G ′ G=B_0\cup G' G = B 0 ∪ G ′ and V ( B 0 ) ∩ V ( G ′ ) = { v } V(B_0)\cap V(G')=\{v\} V ( B 0 ) ∩ V ( G ′ ) = { v } . Let S 1 S_1 S 1 and S 2 S_2 S 2 be the sets defined above (1) for G 1 = B 0 G_1=B_0 G 1 = B 0 and G 2 = G ′ G_2=G' G 2 = G ′ . By the definition of S B 0 S_{B_0} S B 0 , we have S 1 = S B 0 S_1=S_{B_0} S 1 = S B 0 . Moreover, for every block B B B of G ′ G' G ′ , the set obtained by projecting S 2 S_2 S 2 onto B B B is precisely S B S_B S B . Indeed, a path witnessing this property either ends at a vertex of S ∩ V ( G ′ ) S\cap V(G') S ∩ V ( G ′ ) , in which case it also witnesses the corresponding property in G G G , or it ends at v v v because S S S has a vertex in V ( B 0 ) ∖ { v } V(B_0)\setminus\{v\} V ( B 0 ) ∖ { v } ; in the latter case it can be extended through B 0 B_0 B 0 to a vertex of S S S . Conversely, a path in G G G witnessing that a vertex of B B B belongs to S B S_B S B can be truncated at v v v if its endpoint in S S S lies in V ( B 0 ) ∖ { v } V(B_0)\setminus\{v\} V ( B 0 ) ∖ { v } .
Therefore, by (1) and the induction hypothesis,
td 2 ( G , S ) = max { td 2 ( B 0 , S B 0 ) , td 2 ( G ′ , S 2 ) } = max { td 2 ( B , S B ) : B is a block of G } . \begin{aligned}
\operatorname{td}_2(G,S)=\max\{\operatorname{td}_2(B_0,S_{B_0}),\operatorname{td}_2(G',S_2)\} \\
&=\max\{\operatorname{td}_2(B,S_B): B\text{ is a block of }G\}.
\end{aligned} td 2 ( G , S ) = max { td 2 ( B 0 , S B 0 ) , td 2 ( G ′ , S 2 )} = max { td 2 ( B , S B ) : B is a block of G } .
This proves the first assertion. The “moreover” part is straightforward. □
Lemma 28. Let k k k be an integer with k ≥ 2 k\geq2 k ≥ 2 , let G G G be a graph, let S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) , and let W = ( T , ( W t ∣ t ∈ V ( T ) ) ) \mathcal{W}=(T,(W_t\mid t\in V(T))) W = ( T , ( W t ∣ t ∈ V ( T ))) be a tree decomposition of ( G , S ) (G,S) ( G , S ) with width less than k k k . Let H \mathcal{H} H be a family of pairwise disjoint connected subgraphs of G G G each intersecting S S S . There exists a family F ⊆ H \mathcal{F}\subseteq\mathcal{H} F ⊆ H such that (i) ∣ F ∣ ≥ ∣ H ∣ / k |\mathcal{F}|\geq\sqrt{|\mathcal{H}|}/k ∣ F ∣ ≥ ∣ H ∣ / k , and (ii) ∣ I P F ( F ) ∣ ≤ k + 1 |\mathcal{I}^{\mathcal{F}}_{P}(F)|\leq k+1 ∣ I P F ( F ) ∣ ≤ k + 1 for every F ∈ F F\in\mathcal{F} F ∈ F and path P P P in G G G .
Proof. Let ℓ = ⌈ ∣ H ∣ / k ⌉ \ell=\lceil\sqrt{|{\cal H}|/k}\rceil ℓ = ⌈ ∣ H ∣/ k ⌉ . If ℓ ≤ 1 \ell\le1 ℓ ≤ 1 , then taking for F \mathcal{F} F any ℓ \ell ℓ -subset of H \mathcal{H} H witnesses the statement. Now suppose that ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 .
Note that W \mathcal{W} W has adhesion at most k k k . Since the members of H \mathcal{H} H are pairwise disjoint, there is no set of less than ∣ H ∣ |\mathcal{H}| ∣ H ∣ vertices intersecting every member of H \mathcal{H} H . Therefore, there is no set X ⊆ V ( T ) X\subseteq V(T) X ⊆ V ( T ) with ∣ X ∣ ≤ ∣ H ∣ − 1 k |X|\le\frac{|{\cal H}|-1}{k} ∣ X ∣ ≤ k ∣ H ∣ − 1 such that ⋃ x ∈ X W x \bigcup_{x\in X}W_x ⋃ x ∈ X W x intersects every member of H \mathcal{H} H . By Theorem 10, there is H ′ ⊆ H \mathcal{H}'\subseteq\mathcal{H} H ′ ⊆ H such that
(i) ∣ H ′ ∣ ≥ ∣ H ∣ k |\mathcal{H}'|\ge\frac{|{\cal H}|}{k} ∣ H ′ ∣ ≥ k ∣ H ∣ , and
(ii) the sets W [ H ] \mathcal{W}[H] W [ H ] for H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ are pairwise disjoint.
Consider a minimal subtree F F F of T T T that intersects every W [ H ] \mathcal{W}[H] W [ H ] for H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ .
We now distinguish several cases. First suppose that F F F has at least ℓ \ell ℓ leaves. Then, let F \mathcal{F} F be the set of all the members H H H of H ′ \mathcal{H}' H ′ such that W [ H ] \mathcal{W}[H] W [ H ] contains a leaf of F F F . Consider some H ∈ F H\in\mathcal{F} H ∈ F . There is an adhesion in W \mathcal{W} W separating V ( H ) V(H) V ( H ) from ⋃ H ′ ∈ F , H ′ ≠ H V ( H ′ ) \bigcup_{H'\in\mathcal{F},H'\ne H}V(H') ⋃ H ′ ∈ F , H ′ = H V ( H ′ ) in G G G . Let Z Z Z be this adhesion. Since for every two consecutive I , I ′ ∈ T P F ( H ) I,I'\in\mathcal{T}^{\mathcal{F}}_P(H) I , I ′ ∈ T P F ( H ) along P P P , the subpath of P P P between I I I and I ′ I' I ′ intersects ⋃ H ′ ∈ F , H ′ ≠ H V ( H ′ ) \bigcup_{H'\in\mathcal{F},H'\ne H}V(H') ⋃ H ′ ∈ F , H ′ = H V ( H ′ ) , this subpath crosses Z Z Z at least twice, we deduce that
∣ T P F ( H ) ∣ ≤ ∣ Z ∣ / 2 + 1 ≤ k + 1. |\mathcal{T}^{\mathcal{F}}_P(H)|\le|Z|/2+1\le k+1. ∣ T P F ( H ) ∣ ≤ ∣ Z ∣/2 + 1 ≤ k + 1.
Now suppose that there is a path in F F F and ℓ \ell ℓ members H 1 , … , H ℓ H_1,\ldots,H_\ell H 1 , … , H ℓ of H ′ \mathcal{H}' H ′ such that this path intersects W [ H i ] \mathcal{W}[H_i] W [ H i ] for every i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] . We take F = { H 1 , … , H ℓ } \mathcal{F}=\{H_1,\ldots,H_\ell\} F = { H 1 , … , H ℓ } . Consider i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] . Then, there are at most two adhesions in W \mathcal{W} W separating V ( H i ) V(H_i) V ( H i ) and ⋃ j ∈ [ ℓ ] , j ≠ i V ( H j ) \bigcup_{j\in[\ell],j\ne i}V(H_j) ⋃ j ∈ [ ℓ ] , j = i V ( H j ) in G G G . Let Z Z Z be the union of these two adhesions. Since for every two consecutive I , I ′ ∈ T P F ( H i ) I,I'\in\mathcal{T}^{\mathcal{F}}_P(H_i) I , I ′ ∈ T P F ( H i ) for some i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] along P P P , the subpath of P P P between I I I and I ′ I' I ′ intersects ⋃ j ∈ [ ℓ ] , j ≠ i V ( H j ) \bigcup_{j\in[\ell],j\ne i}V(H_j) ⋃ j ∈ [ ℓ ] , j = i V ( H j ) , this subpath crosses Z Z Z twice, we deduce that
∣ T P F ( H i ) ∣ ≤ ∣ Z ∣ / 2 + 1 ≤ k + 1. |\mathcal{T}^{\mathcal{F}}_P(H_i)|\le|Z|/2+1\le k+1. ∣ T P F ( H i ) ∣ ≤ ∣ Z ∣/2 + 1 ≤ k + 1.
In the last case, every path in F F F intersects at most ℓ − 1 \ell-1 ℓ − 1 sets W [ H ] \mathcal{W}[H] W [ H ] for H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ , and there are at most ℓ − 1 \ell-1 ℓ − 1 leaves in F F F . Let r r r be any vertex of F F F . Then, for every leaf x x x , every r r r -x x x path in F F F intersects at most ℓ − 1 \ell-1 ℓ − 1 sets W [ H ] \mathcal{W}[H] W [ H ] for H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ . Since F F F is covered by the paths between r r r and the leaves, we deduce that
∣ H ′ ∣ ≤ ( ℓ − 1 ) 2 < ∣ H ∣ k , |\mathcal{H}'|\le(\ell-1)^2<\frac{|{\cal H}|}{k}, ∣ H ′ ∣ ≤ ( ℓ − 1 ) 2 < k ∣ H ∣ ,
a contradiction. □
We will also need the celebrated Erdős-Szekeres Theorem:
Theorem 29 (Erdős-Szekeres Theorem). For every positive integer k k k and every permutation π \pi π of [ k 2 + 1 ] [k^2+1] [ k 2 + 1 ] , there exists I ⊆ [ k 2 + 1 ] I\subseteq[k^2+1] I ⊆ [ k 2 + 1 ] of size k + 1 k+1 k + 1 such that π ∣ I \pi|_I π ∣ I is either decreasing or increasing.
Lemma 30. There is a function f 30 : N 3 → N f_{30}:\mathbb{N}^3\to\mathbb{N} f 30 : N 3 → N such that the following holds. Let k k k , ℓ 1 \ell_1 ℓ 1 , and ℓ 2 \ell_2 ℓ 2 be positive integers, let G G G be a graph, let P 1 P_1 P 1 and P 2 P_2 P 2 be disjoint paths in G G G , and let S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) . Let H \mathcal{H} H be a family of connected, pairwise disjoint subgraphs of G G G such that for every H ∈ H H\in\mathcal{H} H ∈ H ,
(i) V ( H ) ∩ S ≠ ∅ V(H)\cap S\ne\varnothing V ( H ) ∩ S = ∅ ,
(ii) 1 ≤ ∣ T P 1 ( H ) ∣ ≤ ℓ 1 1\le|\mathcal{T}_{P_1}(H)|\le\ell_1 1 ≤ ∣ T P 1 ( H ) ∣ ≤ ℓ 1 , and
(iii) 1 ≤ ∣ T P 2 ( H ) ∣ ≤ ℓ 2 1\le|\mathcal{T}_{P_2}(H)|\le\ell_2 1 ≤ ∣ T P 2 ( H ) ∣ ≤ ℓ 2 .
If ∣ H ∣ ≥ f 30 ( k , ℓ 1 , ℓ 2 ) |\mathcal{H}|\ge f_{30}(k,\ell_1,\ell_2) ∣ H ∣ ≥ f 30 ( k , ℓ 1 , ℓ 2 ) , then ( L k , T k ) (L_k,T_k) ( L k , T k ) is a minor of ( G , S ) (G,S) ( G , S ) .
Proof. We set
f 30 ( k , ℓ 1 , ℓ 2 ) = { 2 ( ( k − 1 ) 2 + 1 ) if ℓ 1 = ℓ 2 = 1 , f 30 ( k , 1 , ℓ 2 ) ( f 30 ( k , ℓ 1 − 1 , ℓ 2 ) + 1 ) − 1 if ℓ 1 ≥ 2 , f 30 ( k , ℓ 1 , 1 ) ( f 30 ( k , ℓ 1 , ℓ 2 − 1 ) + 1 ) − 1 if ℓ 1 = 1 and ℓ 2 ≥ 2. f_{30}(k,\ell_1,\ell_2)=
\begin{cases}
2((k-1)^2+1) & \text{if }\ell_1=\ell_2=1,\\
f_{30}(k,1,\ell_2)(f_{30}(k,\ell_1-1,\ell_2)+1)-1 & \text{if }\ell_1\ge2,\\
f_{30}(k,\ell_1,1)(f_{30}(k,\ell_1,\ell_2-1)+1)-1 & \text{if }\ell_1=1\text{ and }\ell_2\ge2.
\end{cases} f 30 ( k , ℓ 1 , ℓ 2 ) = ⎩ ⎨ ⎧ 2 (( k − 1 ) 2 + 1 ) f 30 ( k , 1 , ℓ 2 ) ( f 30 ( k , ℓ 1 − 1 , ℓ 2 ) + 1 ) − 1 f 30 ( k , ℓ 1 , 1 ) ( f 30 ( k , ℓ 1 , ℓ 2 − 1 ) + 1 ) − 1 if ℓ 1 = ℓ 2 = 1 , if ℓ 1 ≥ 2 , if ℓ 1 = 1 and ℓ 2 ≥ 2.
We call a tuple ( k , ℓ 1 , ℓ 2 , P 1 , P 2 , H ) (k,\ell_1,\ell_2,P_1,P_2,\mathcal{H}) ( k , ℓ 1 , ℓ 2 , P 1 , P 2 , H ) satisfying the assumptions of the lemma an instance . We prove the statement of the lemma by induction on ℓ 1 + ℓ 2 + ∣ V ( G ) ∣ \ell_1+\ell_2+|V(G)| ℓ 1 + ℓ 2 + ∣ V ( G ) ∣ . Let ( k , ℓ 1 , ℓ 2 , P 1 , P 2 , H ) (k,\ell_1,\ell_2,P_1,P_2,\mathcal{H}) ( k , ℓ 1 , ℓ 2 , P 1 , P 2 , H ) be an instance with ∣ H ∣ ≥ f 30 ( k , ℓ 1 , ℓ 2 ) |\mathcal{H}|\ge f_{30}(k,\ell_1,\ell_2) ∣ H ∣ ≥ f 30 ( k , ℓ 1 , ℓ 2 ) .
If there exists H ∈ H H\in\mathcal{H} H ∈ H and I ∈ I P 1 ( H ) ∪ I P 2 ( H ) I\in\mathcal{I}_{P_1}(H)\cup\mathcal{I}_{P_2}(H) I ∈ I P 1 ( H ) ∪ I P 2 ( H ) with ∣ V ( I ) ∣ ≥ 2 |V(I)|\ge2 ∣ V ( I ) ∣ ≥ 2 , then we can call the induction hypothesis on the instance obtained by contracting an edge in the path I I I : if there is a model of ( L k , T k ) (L_k,T_k) ( L k , T k ) in the contracted graph, there is also in the original one. Hence we can assume the following.
For every H ∈ H H\in\mathcal{H} H ∈ H , for every I ∈ I P 1 ( H ) ∪ I P 2 ( H ) I\in\mathcal{I}_{P_1}(H)\cup\mathcal{I}_{P_2}(H) I ∈ I P 1 ( H ) ∪ I P 2 ( H ) , ∣ V ( I ) ∣ = 1 |V(I)|=1 ∣ V ( I ) ∣ = 1 . (2)
Similarly, if there is H ∈ H H\in\mathcal{H} H ∈ H and an edge e = u v e=uv e = uv in H H H with v ∉ V ( P 1 ) ∪ V ( P 2 ) v\notin V(P_1)\cup V(P_2) v ∈ / V ( P 1 ) ∪ V ( P 2 ) , then we can contract e e e and call the induction hypothesis on this smaller instance. Hence, using the fact that every member of H \mathcal{H} H is connected, we can assume the following.
For every H ∈ H H\in\mathcal{H} H ∈ H , V ( H ) ⊆ V ( P 1 ) ∪ V ( P 2 ) V(H)\subseteq V(P_1)\cup V(P_2) V ( H ) ⊆ V ( P 1 ) ∪ V ( P 2 ) . (3)
First suppose ℓ 1 = ℓ 2 = 1 \ell_1=\ell_2=1 ℓ 1 = ℓ 2 = 1 . Then, for every H ∈ H H\in\mathcal{H} H ∈ H and i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] , V ( H ) ∩ V ( P i ) V(H)\cap V(P_i) V ( H ) ∩ V ( P i ) consists of one vertex because of (2). By (3), this implies that every H ∈ H H\in\mathcal{H} H ∈ H consists of a single edge, that we denote by p 1 ( H ) p 2 ( H ) p_1(H)p_2(H) p 1 ( H ) p 2 ( H ) with p 1 ( H ) ∈ V ( P 1 ) p_1(H)\in V(P_1) p 1 ( H ) ∈ V ( P 1 ) and p 2 ( H ) ∈ V ( P 2 ) p_2(H)\in V(P_2) p 2 ( H ) ∈ V ( P 2 ) . Let H i = { H ∈ H ∣ p i ( H ) ∈ S } \mathcal{H}_i=\{H\in\mathcal{H}\mid p_i(H)\in S\} H i = { H ∈ H ∣ p i ( H ) ∈ S } for each i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] . Since H = H 1 ∪ H 2 \mathcal{H}=\mathcal{H}_1\cup\mathcal{H}_2 H = H 1 ∪ H 2 , there exists i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] such that ∣ H i ∣ ≥ ∣ H ∣ / 2 ≥ ( k − 1 ) 2 + 1 |\mathcal{H}_i|\ge|\mathcal{H}|/2\ge(k-1)^2+1 ∣ H i ∣ ≥ ∣ H ∣/2 ≥ ( k − 1 ) 2 + 1 . Without loss of generality assume i = 1 i=1 i = 1 . Then, by the Erdős-Szekeres Theorem (Theorem 29 ), there is a subfamily H ′ ⊆ H 1 \mathcal{H}'\subseteq\mathcal{H}_1 H ′ ⊆ H 1 of size k k k such that the vertices p 1 ( H ) p_1(H) p 1 ( H ) and p 2 ( H ) p_2(H) p 2 ( H ) for H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ appear in the same or reverse order along P 1 , P 2 P_1,P_2 P 1 , P 2 . By possibly reversing the order of P 2 P_2 P 2 , we can assume they appear in the same order. Let H 1 , … , H k H_1,\ldots,H_k H 1 , … , H k be the members of H ′ \mathcal{H}' H ′ such that p i ( H 1 ) , … , p i ( H k ) p_i(H_1),\ldots,p_i(H_k) p i ( H 1 ) , … , p i ( H k ) appear in this order along P i P_i P i , for each i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] . Then, for every i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] , for every j ∈ [ k − 1 ] j\in[k-1] j ∈ [ k − 1 ] , let B i , j B_{i,j} B i , j denote the vertex set of the subpath of P i P_i P i starting at p i ( H j ) p_i(H_j) p i ( H j ) and ending at the predecessor of p i ( H j + 1 ) p_i(H_{j+1}) p i ( H j + 1 ) , and let B i , k = { p i ( H k ) } B_{i,k}=\{p_i(H_k)\} B i , k = { p i ( H k )} . Then, ( B i , j ∣ ( i , j ) ∈ [ 2 ] × [ k ] ) (B_{i,j}\mid(i,j)\in[2]\times[k]) ( B i , j ∣ ( i , j ) ∈ [ 2 ] × [ k ]) is a model of ( L k , T k ) (L_k,T_k) ( L k , T k ) in ( G , S ) (G,S) ( G , S ) .
Now suppose that ℓ 1 ≥ 2 \ell_1\ge2 ℓ 1 ≥ 2 or ℓ 2 ≥ 2 \ell_2\ge2 ℓ 2 ≥ 2 and without loss of generality, assume ℓ 1 ≥ 2 \ell_1\ge2 ℓ 1 ≥ 2 .
Consider the family of the subpaths J P 1 ( H ) J_{P_1}(H) J P 1 ( H ) for H ∈ H H\in\mathcal{H} H ∈ H . If there exists H ′ ⊆ H \mathcal{H}'\subseteq\mathcal{H} H ′ ⊆ H of size at least f 30 ( k , 1 , ℓ 2 ) f_{30}(k,1,\ell_2) f 30 ( k , 1 , ℓ 2 ) for which the paths J P 1 ( H ) J_{P_1}(H) J P 1 ( H ) for H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ are pairwise disjoint, then ∣ I P 1 H ′ ( H ) ∣ = 1 |\mathcal{I}_{P_1}^{\mathcal{H}'}(H)|=1 ∣ I P 1 H ′ ( H ) ∣ = 1 for each H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ , and so we can call the induction hypothesis on the instance ( k , 1 , ℓ 2 , P 1 , P 2 , H ′ ) (k,1,\ell_2,P_1,P_2,\mathcal{H}') ( k , 1 , ℓ 2 , P 1 , P 2 , H ′ ) . Otherwise, by the Helly property of subpaths of P 1 P_1 P 1 , there exists X ⊆ V ( P 1 ) X\subseteq V(P_1) X ⊆ V ( P 1 ) of size at most f 30 ( k , 1 , ℓ 2 ) − 1 f_{30}(k,1,\ell_2)-1 f 30 ( k , 1 , ℓ 2 ) − 1 such that X X X intersects V ( J P 1 ( H ) ) V(J_{P_1}(H)) V ( J P 1 ( H )) for every H ∈ H H\in\mathcal{H} H ∈ H . Let Q 1 , … , Q m Q_1,\ldots,Q_m Q 1 , … , Q m be the components of P 1 − X P_1-X P 1 − X . Recall that every H ∈ H H\in\mathcal{H} H ∈ H intersects P 1 P_1 P 1 , and that at least one of the sets V ( Q 1 ) , … , V ( Q m ) V(Q_1),\ldots,V(Q_m) V ( Q 1 ) , … , V ( Q m ) and { x } \{x\} { x } for x ∈ X x\in X x ∈ X . Since at most ∣ X ∣ |X| ∣ X ∣ members of H \mathcal{H} H intersect X X X , we deduce by the pigeonhole principle that there exists j ∈ [ m ] j\in[m] j ∈ [ m ] and H ′ ⊆ H \mathcal{H}'\subseteq\mathcal{H} H ′ ⊆ H such that
(i) ∣ H ′ ∣ ≥ ∣ H ∣ − ∣ X ∣ m ≥ f 30 ( k , ℓ 1 − 1 , ℓ 2 ) |\mathcal{H}'|\ge\frac{|\mathcal{H}|-|X|}{m}\ge f_{30}(k,\ell_1-1,\ell_2) ∣ H ′ ∣ ≥ m ∣ H ∣ − ∣ X ∣ ≥ f 30 ( k , ℓ 1 − 1 , ℓ 2 ) ,
(ii) for every H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ , H H H is disjoint from X X X , and
(iii) for every H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ , H H H intersects Q j Q_j Q j .
Let H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ . By (2), every I ∈ I P 1 ( H ) I\in\mathcal{I}_{P_1}(H) I ∈ I P 1 ( H ) consists of a single vertex. Hence, there is I ∈ I P 1 ( H ) I\in\mathcal{I}_{P_1}(H) I ∈ I P 1 ( H ) that is disjoint from Q j Q_j Q j . This implies that
∣ I Q j H ′ ( H ) ∣ ≤ ∣ I P 1 H ( H ) ∣ − 1 ≤ ℓ 1 − 1. |\mathcal{I}_{Q_j}^{\mathcal{H}'}(H)|\le|\mathcal{I}_{P_1}^{\mathcal{H}}(H)|-1\le\ell_1-1. ∣ I Q j H ′ ( H ) ∣ ≤ ∣ I P 1 H ( H ) ∣ − 1 ≤ ℓ 1 − 1.
Therefore, we can call the induction hypothesis on the instance ( k , ℓ 1 − 1 , ℓ 2 , Q j , P 2 , H ′ ) (k,\ell_1-1,\ell_2,Q_j,P_2,\mathcal{H}') ( k , ℓ 1 − 1 , ℓ 2 , Q j , P 2 , H ′ ) . This proves the lemma.
Lemma 31. There is a function f 31 : N → N f_{31}\colon\mathbb{N}\to\mathbb{N} f 31 : N → N such that the following holds. Let k k k be a positive integer, let G G G be a graph, let S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) , let P 1 P_1 P 1 and P 2 P_2 P 2 be two disjoint paths in G G G , and let H \mathcal{H} H be a family of pairwise disjoint connected subgraphs of G G G such that, for every H ∈ H H\in\mathcal{H} H ∈ H , (i) H H H intersects S S S , (ii) H H H intersects V ( P 1 ) V(P_1) V ( P 1 ) , and (iii) H H H intersects V ( P 2 ) V(P_2) V ( P 2 ) . If ∣ H ∣ ≥ f 31 ( k ) |\mathcal{H}|\geq f_{31}(k) ∣ H ∣ ≥ f 31 ( k ) , then ( L k , T k ) (L_k,T_k) ( L k , T k ) is a minor of ( G , S ) (G,S) ( G , S ) .
Proof. Let f 31 ( k ) = ( f 9 ( 2 k ) ) 3 ⋅ ( f 30 ( k , f 9 ( 2 k ) + 1 , f 9 ( 2 k ) + 1 ) ) 4 f_{31}(k)=(f_9(2k))^3\cdot(f_{30}(k,f_9(2k)+1,f_9(2k)+1))^4 f 31 ( k ) = ( f 9 ( 2 k ) ) 3 ⋅ ( f 30 ( k , f 9 ( 2 k ) + 1 , f 9 ( 2 k ) + 1 ) ) 4 . Suppose for contradiction that ∣ H ∣ ≥ f 31 ( k ) |\mathcal{H}|\geq f_{31}(k) ∣ H ∣ ≥ f 31 ( k ) and that there is no model of ( L k , T k ) (L_k,T_k) ( L k , T k ) in ( G , S ) (G,S) ( G , S ) . By Theorem 9 , there is a tree decomposition of ( G , S ) (G,S) ( G , S ) of width less than f 9 ( 2 k ) f_9(2k) f 9 ( 2 k ) . By applying Theorem 28 twice, we deduce that there exists H ′ ⊆ H \mathcal{H}'\subseteq\mathcal{H} H ′ ⊆ H of size at least f 30 ( k , f 9 ( 2 k ) + 1 , f 9 ( 2 k ) + 1 ) f_{30}(k,f_9(2k)+1,f_9(2k)+1) f 30 ( k , f 9 ( 2 k ) + 1 , f 9 ( 2 k ) + 1 ) such that ∣ T P i H ′ ( H ) ∣ ≤ f 9 ( 2 k ) + 1 |\mathcal{T}^{\mathcal{H}'}_{P_i}(H)|\leq f_9(2k)+1 ∣ T P i H ′ ( H ) ∣ ≤ f 9 ( 2 k ) + 1 for all H ∈ H ′ H\in\mathcal{H}' H ∈ H ′ and i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] . By Theorem 30, we conclude that ( L k , T k ) (L_k,T_k) ( L k , T k ) is a minor of ( G , S ) (G,S) ( G , S ) .
Lemma 32. There is a function f 32 : N 2 → N f_{32}\colon\mathbb{N}^2\to\mathbb{N} f 32 : N 2 → N such that the following holds. For all positive integers k k k and ℓ \ell ℓ , for every 2 2 2 -connected graph G G G , for every S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) , for every u 1 , u 2 ∈ V ( G ) u_1,u_2\in V(G) u 1 , u 2 ∈ V ( G ) distinct, if td 2 ( G , S ) > f 32 ( ℓ , k ) \operatorname{td}_2(G,S)>f_{32}(\ell,k) td 2 ( G , S ) > f 32 ( ℓ , k ) , then either (a) ( L ℓ , T ℓ ) (L_\ell,T_\ell) ( L ℓ , T ℓ ) is a minor of ( G , S ) (G,S) ( G , S ) , or (b) there is a model ( B x ∣ x ∈ V ( L k ) ) (B_x\mid x\in V(L_k)) ( B x ∣ x ∈ V ( L k )) of L k L_k L k in G G G such that (i) for every column C C C of L k L_k L k , S ∩ ( ⋃ c ∈ C B c ) ≠ ∅ S\cap\left(\bigcup_{c\in C}B_c\right)\neq\varnothing S ∩ ( ⋃ c ∈ C B c ) = ∅ , and (ii) the vertices of the first column of L k L_k L k can be named { c 1 , c 2 } \{c_1,c_2\} { c 1 , c 2 } so that u 1 ∈ B c 1 u_1\in B_{c_1} u 1 ∈ B c 1 and u 2 ∈ B c 2 u_2\in B_{c_2} u 2 ∈ B c 2 .
Proof. Let f 32 ( ⋅ , ⋅ ) f_{32}(\cdot,\cdot) f 32 ( ⋅ , ⋅ ) be defined by induction as follows. For all positive integers k , ℓ k,\ell k , ℓ , let
f 32 ( ℓ , k ) = { 0 if k = 1 , 2 ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) + f 32 ( ℓ , k − 1 ) + 6 if k ≥ 2. f_{32}(\ell,k)=
\begin{cases}
0 & \text{if } k=1,\\
2(f_{31}(\ell)-1)\cdot f_9(2\ell)+f_{32}(\ell,k-1)+6 & \text{if } k\geq2.
\end{cases} f 32 ( ℓ , k ) = { 0 2 ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) + f 32 ( ℓ , k − 1 ) + 6 if k = 1 , if k ≥ 2.
We proceed by induction on k k k . Let k k k and ℓ \ell ℓ be positive integers, let G G G be a 2 2 2 -connected graph, let S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) , and let u 1 , u 2 ∈ V ( G ) u_1,u_2\in V(G) u 1 , u 2 ∈ V ( G ) distinct. Assume that td 2 ( G , S ) > f 32 ( ℓ , k ) \operatorname{td}_2(G,S)>f_{32}(\ell,k) td 2 ( G , S ) > f 32 ( ℓ , k ) and that ( L ℓ , T ℓ ) (L_\ell,T_\ell) ( L ℓ , T ℓ ) is not a minor of ( G , S ) (G,S) ( G , S ) . By Theorem 9 , this implies that tw ( G , S ) < f 9 ( 2 ℓ ) \operatorname{tw}(G,S)<f_9(2\ell) tw ( G , S ) < f 9 ( 2 ℓ ) .
First suppose k = 1 k=1 k = 1 . Since G G G is 2 2 2 -connected, and because S S S is not empty (since td 2 ( G , S ) > 0 \operatorname{td}_2(G,S)>0 td 2 ( G , S ) > 0 ), there exists s ∈ S s\in S s ∈ S and two paths P 1 , P 2 P_1,P_2 P 1 , P 2 from s s s to { u 1 , u 2 } \{u_1,u_2\} { u 1 , u 2 } in G G G such that V ( P 1 ) ∩ V ( P 2 ) = { s } V(P_1)\cap V(P_2)=\{s\} V ( P 1 ) ∩ V ( P 2 ) = { s } and u i ∈ V ( P i ) u_i\in V(P_i) u i ∈ V ( P i ) for i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] . Without loss of generality, s ≠ u 1 s\neq u_1 s = u 1 . Then, ( V ( P 1 ) ∖ { s } , V ( P 2 ) ) (V(P_1)\setminus\{s\},V(P_2)) ( V ( P 1 ) ∖ { s } , V ( P 2 )) is a model of ( L 1 , T 1 ) (L_1,T_1) ( L 1 , T 1 ) in ( G , S ) (G,S) ( G , S ) as wanted. Thus, we assume that k ≥ 2 k\geq2 k ≥ 2 .
Since G G G is 2 2 2 -connected, there exist two internally disjoint u 1 u_1 u 1 –u 2 u_2 u 2 paths P 1 , P 2 P_1,P_2 P 1 , P 2 . Let H \mathcal{H} H be the family of all the connected subgraphs H H H of G G G that intersect S S S and at least one internal vertex of each path P i P_i P i , i.e., V ( H ) ∩ S ≠ ∅ V(H)\cap S\neq\varnothing V ( H ) ∩ S = ∅ , V ( H ) ∩ ( V ( P 1 ) ∖ { u 1 , u 2 } ) ≠ ∅ V(H)\cap(V(P_1)\setminus\{u_1,u_2\})\neq\varnothing V ( H ) ∩ ( V ( P 1 ) ∖ { u 1 , u 2 }) = ∅ , and V ( H ) ∩ ( V ( P 2 ) ∖ { u 1 , u 2 } ) ≠ ∅ V(H)\cap(V(P_2)\setminus\{u_1,u_2\})\neq\varnothing V ( H ) ∩ ( V ( P 2 ) ∖ { u 1 , u 2 }) = ∅ . By Theorem 31, there are no f 31 ( ℓ ) f_{31}(\ell) f 31 ( ℓ ) pairwise disjoint members of H \mathcal{H} H . Hence, by Theorem 10, there exists Z ⊆ V ( G ) Z\subseteq V(G) Z ⊆ V ( G ) such that (i) ∣ Z ∣ ≤ ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) |Z|\leq(f_{31}(\ell)-1)\cdot f_9(2\ell) ∣ Z ∣ ≤ ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) , and (ii) V ( H ) ∩ Z ≠ ∅ V(H)\cap Z\neq\varnothing V ( H ) ∩ Z = ∅ for every H ∈ H H\in\mathcal{H} H ∈ H .
Fix a vertex s ∈ S s\in S s ∈ S . Since G G G is 2 2 2 -connected, there are two internally disjoint s s s –{ u 1 , u 2 } \{u_1,u_2\} { u 1 , u 2 } paths Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 in G G G . Then, let H ′ \mathcal{H}' H ′ be the family of all the connected subgraphs H H H of G G G that intersect S S S and at least one vertex of each path Q Q Q different than s s s , i.e., V ( H ) ∩ S ≠ ∅ V(H)\cap S\neq\varnothing V ( H ) ∩ S = ∅ , V ( H ) ∩ ( V ( Q 1 ) ∖ { s } ) ≠ ∅ V(H) \cap(V(Q_1)\setminus\{s\}) \ne\emptyset V ( H ) ∩ ( V ( Q 1 ) ∖ { s }) = ∅ , and V ( H ) ∩ ( V ( Q 2 ) ∖ { s } ) ≠ ∅ V(H) \cap(V(Q_2)\setminus\{s\}) \ne\emptyset V ( H ) ∩ ( V ( Q 2 ) ∖ { s }) = ∅ . Similarly as for P 1 , P 2 P_1, P_2 P 1 , P 2 , there exists Z ′ ⊆ V ( G ) Z' \subseteq V(G) Z ′ ⊆ V ( G ) such that
∣ Z ′ ∣ ≤ ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) |Z'| \le(f_{31}(\ell)-1)\cdot f_9(2\ell) ∣ Z ′ ∣ ≤ ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) , and
V ( H ) ∩ Z ′ ≠ ∅ V(H) \cap Z' \ne\emptyset V ( H ) ∩ Z ′ = ∅ for every H ∈ H ′ H \in\mathcal{H}' H ∈ H ′ .
We set Z ∘ = Z ∪ Z ′ ∪ { s , u 1 , u 2 } Z^\circ= Z \cup Z' \cup\{s,u_1,u_2\} Z ∘ = Z ∪ Z ′ ∪ { s , u 1 , u 2 } ; keep in mind that ∣ Z ∘ ∣ ≤ 2 ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) + 3 |Z^\circ| \le2(f_{31}(\ell)-1)\cdot f_9(2\ell)+3 ∣ Z ∘ ∣ ≤ 2 ( f 31 ( ℓ ) − 1 ) ⋅ f 9 ( 2 ℓ ) + 3 . We have
td 2 ( G − Z ∘ , S ∖ Z ∘ ) ≥ td 2 ( G , S ) − ∣ Z ∘ ∣ > f 32 ( ℓ , k − 1 ) + 2. \operatorname{td}_2(G-Z^\circ,S\setminus Z^\circ) \ge\operatorname{td}_2(G,S)-|Z^\circ| > f_{32}(\ell,k-1)+2. td 2 ( G − Z ∘ , S ∖ Z ∘ ) ≥ td 2 ( G , S ) − ∣ Z ∘ ∣ > f 32 ( ℓ , k − 1 ) + 2.
Therefore, by Theorem 27 , there exists a block G ′ G' G ′ of G − Z ∘ G-Z^\circ G − Z ∘ such that, for
S ′ = { u ∈ V ( G ′ ) ∣ there is a u – S path P in G − Z ∘ with V ( G ′ ) ∩ V ( P ) = { u } } , S'=\{u\in V(G')\mid\text{there is a }u\text{--}S\text{ path }P\text{ in }G-Z^\circ\text{ with }V(G')\cap V(P)=\{u\}\}, S ′ = { u ∈ V ( G ′ ) ∣ there is a u – S path P in G − Z ∘ with V ( G ′ ) ∩ V ( P ) = { u }} ,
we have td 2 ( G ′ , S ′ ) > f 32 ( ℓ , k − 1 ) + 2 \operatorname{td}_2(G',S')>f_{32}(\ell,k-1)+2 td 2 ( G ′ , S ′ ) > f 32 ( ℓ , k − 1 ) + 2 . Intuitively, S ′ S' S ′ is the set of all vertices in V ( G ′ ) V(G') V ( G ′ ) that are either in S ∖ Z ∘ S\setminus Z^\circ S ∖ Z ∘ or can be connected to a vertex in S ∖ Z ∘ S\setminus Z^\circ S ∖ Z ∘ via a sequence of blocks of G − Z ∘ G-Z^\circ G − Z ∘ .
We next focus on fixing two vertices in G ′ G' G ′ and applying the induction hypothesis in order to find a ladder L k − 1 L_{k-1} L k − 1 that can be extended by one step in order to include u 1 u_1 u 1 and u 2 u_2 u 2 (and s s s ). This is done as follows. Since G G G is 2-connected, there exist two vertex-disjoint { u 1 , u 2 } \{u_1,u_2\} { u 1 , u 2 } --V ( G ′ ) V(G') V ( G ′ ) paths R 1 , R 2 R_1,R_2 R 1 , R 2 in G G G . Among all such pairs, allowing their endpoints in G ′ G' G ′ to vary, choose one minimizing
∣ V ( R 1 ) ∩ Z ∘ ∣ + ∣ V ( R 2 ) ∩ Z ∘ ∣ . |V(R_1)\cap Z^\circ|+|V(R_2)\cap Z^\circ|. ∣ V ( R 1 ) ∩ Z ∘ ∣ + ∣ V ( R 2 ) ∩ Z ∘ ∣.
Label the paths so that u i u_i u i is an endpoint of R i R_i R i for each i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] , and let u i ′ u'_i u i ′ be its endpoint in V ( G ′ ) V(G') V ( G ′ ) . Thus V ( R i ) ∩ V ( G ′ ) = { u i ′ } V(R_i)\cap V(G')=\{u'_i\} V ( R i ) ∩ V ( G ′ ) = { u i ′ } .
Let G 0 G_0 G 0 be the subgraph of G G G induced by the union of V ( G ′ ) V(G') V ( G ′ ) and the vertex sets of all components of G − ( Z ∘ ∪ V ( G ′ ) ) G-(Z^\circ\cup V(G')) G − ( Z ∘ ∪ V ( G ′ )) having a neighbor in V ( G ′ ) ∖ { u 1 ′ , u 2 ′ } V(G')\setminus\{u'_1,u'_2\} V ( G ′ ) ∖ { u 1 ′ , u 2 ′ } . See Figure 3 . We claim that ( V ( R i ) ∖ { u i ′ } ) ∩ V ( G 0 ) = ∅ (V(R_i)\setminus\{u'_i\})\cap V(G_0)=\emptyset ( V ( R i ) ∖ { u i ′ }) ∩ V ( G 0 ) = ∅ for each i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] .
Figure 3. The construction of G 0 G_0 G 0 in the proof of Theorem 32. The red vertices are the elements of S S S , and the purple ones are the elements of S ′ S' S ′ .
Suppose otherwise. Then some component C C C used in the definition of G 0 G_0 G 0 meets V ( R 1 ) ∪ V ( R 2 ) V(R_1)\cup V(R_2) V ( R 1 ) ∪ V ( R 2 ) . Since G ′ G' G ′ is a block of G − Z ∘ G-Z^\circ G − Z ∘ , the component C C C has exactly one neighbor v v v in G ′ G' G ′ , and v ∉ { u 1 ′ , u 2 ′ } v\notin\{u'_1,u'_2\} v ∈ / { u 1 ′ , u 2 ′ } . Choose a path Q Q Q from v v v to a vertex w ∈ V ( C ) ∩ ( V ( R 1 ) ∪ V ( R 2 ) ) w\in V(C)\cap(V(R_1)\cup V(R_2)) w ∈ V ( C ) ∩ ( V ( R 1 ) ∪ V ( R 2 )) such that V ( Q ) ∖ { v } ⊆ V ( C ) V(Q)\setminus\{v\}\subseteq V(C) V ( Q ) ∖ { v } ⊆ V ( C ) and Q Q Q meets R 1 ∪ R 2 R_1\cup R_2 R 1 ∪ R 2 only at w w w . Say w ∈ V ( R i ) w\in V(R_i) w ∈ V ( R i ) . Replace the w w w --u i ′ u'_i u i ′ subpath of R i R_i R i by Q Q Q , traversed from w w w to v v v . This gives another pair of vertex-disjoint { u 1 , u 2 } \{u_1,u_2\} { u 1 , u 2 } --V ( G ′ ) V(G') V ( G ′ ) paths. The discarded subpath must contain a vertex of Z ∘ Z^\circ Z ∘ : otherwise, since C C C has no neighbor in G ′ G' G ′ other than v v v , it could not reach u i ′ ≠ v u'_i\ne v u i ′ = v without meeting G ′ G' G ′ before its endpoint. On the other hand, Q Q Q is disjoint from Z ∘ Z^\circ Z ∘ . Consequently, the new pair has a strictly smaller value of ∣ V ( R 1 ) ∩ Z ∘ ∣ + ∣ V ( R 2 ) ∩ Z ∘ ∣ |V(R_1)\cap Z^\circ|+|V(R_2)\cap Z^\circ| ∣ V ( R 1 ) ∩ Z ∘ ∣ + ∣ V ( R 2 ) ∩ Z ∘ ∣ , a contradiction. This proves the claim. Additionally, { s , u 1 , u 2 } ∩ V ( G 0 ) = ∅ \{s,u_1,u_2\}\cap V(G_0)=\emptyset { s , u 1 , u 2 } ∩ V ( G 0 ) = ∅ , since V ( G 0 ) ∩ Z ∘ = ∅ V(G_0)\cap Z^\circ=\emptyset V ( G 0 ) ∩ Z ∘ = ∅ .
Since td 2 ( G ′ , S ′ ∖ { u 1 ′ , u 2 ′ } ) > f 32 ( ℓ , k − 1 ) \operatorname{td}_2(G',S'\setminus\{u'_1,u'_2\})>f_{32}(\ell,k-1) td 2 ( G ′ , S ′ ∖ { u 1 ′ , u 2 ′ }) > f 32 ( ℓ , k − 1 ) , and by the induction hypothesis, there is a model ( B x 0 ∣ x ∈ V ( L k − 1 ) ) (B_x^0 \mid x \in V(L_{k-1})) ( B x 0 ∣ x ∈ V ( L k − 1 )) of L k − 1 L_{k-1} L k − 1 in G ′ G' G ′ such that (i) for every column C C C of L k − 1 L_{k-1} L k − 1 , ( S ′ ∖ { u 1 ′ , u 2 ′ } ) ∩ ( ⋃ c ∈ C B c 0 ) ≠ ∅ (S'\setminus\{u'_1,u'_2\})\cap(\bigcup_{c\in C}B_c^0)\ne\varnothing ( S ′ ∖ { u 1 ′ , u 2 ′ }) ∩ ( ⋃ c ∈ C B c 0 ) = ∅ , and (ii) if { c 1 0 , c 2 0 } \{c_1^0,c_2^0\} { c 1 0 , c 2 0 } is the first column of L k − 1 L_{k-1} L k − 1 , then u 1 ′ ∈ B c 1 0 0 u'_1\in B_{c_1^0}^0 u 1 ′ ∈ B c 1 0 0 and u 2 ′ ∈ B c 2 0 0 u'_2\in B_{c_2^0}^0 u 2 ′ ∈ B c 2 0 0 , or vice-versa. Up to relabeling c 1 0 , c 2 0 c_1^0,c_2^0 c 1 0 , c 2 0 , we assume u 1 ′ ∈ B c 1 0 0 u'_1\in B_{c_1^0}^0 u 1 ′ ∈ B c 1 0 0 and so u 2 ′ ∈ B c 2 0 0 u'_2\in B_{c_2^0}^0 u 2 ′ ∈ B c 2 0 0 .
By construction, this model can be extended into a model ( B x 1 ∣ x ∈ V ( L k − 1 ) ) (B_x^1 \mid x \in V(L_{k-1})) ( B x 1 ∣ x ∈ V ( L k − 1 )) of L k − 1 L_{k-1} L k − 1 in G 0 G_0 G 0 such that (i) for every column C C C of L k − 1 L_{k-1} L k − 1 , S ∩ ( ⋃ c ∈ C B c 1 ) ≠ ∅ S\cap(\bigcup_{c\in C}B_c^1)\ne\varnothing S ∩ ( ⋃ c ∈ C B c 1 ) = ∅ , and (ii) u 1 ′ ∈ B c 1 0 1 u'_1\in B_{c_1^0}^1 u 1 ′ ∈ B c 1 0 1 and u 2 ′ ∈ B c 2 0 1 u'_2\in B_{c_2^0}^1 u 2 ′ ∈ B c 2 0 1 .
By the properties of Z Z Z and Z ′ Z' Z ′ , and because V ( G 0 ) V(G_0) V ( G 0 ) is disjoint from Z ∪ Z ′ Z\cup Z' Z ∪ Z ′ , G 0 G_0 G 0 is not a member of H ∪ H ′ \mathcal{H}\cup\mathcal{H}' H ∪ H ′ . Since V ( G 0 ) V(G_0) V ( G 0 ) intersects S S S , we deduce that (i) there is i 0 ∈ [ 2 ] i_0\in[2] i 0 ∈ [ 2 ] such that P i 0 P_{i_0} P i 0 is disjoint from V ( G 0 ) V(G_0) V ( G 0 ) and (ii) there is j 0 ∈ [ 2 ] j_0\in[2] j 0 ∈ [ 2 ] such that Q j 0 Q_{j_0} Q j 0 is disjoint from V ( G 0 ) V(G_0) V ( G 0 ) .
We fix such an i 0 ∈ [ 2 ] i_0\in[2] i 0 ∈ [ 2 ] . We follow the path R 1 R_1 R 1 (resp. R 2 R_2 R 2 ) starting from u 1 ′ u'_1 u 1 ′ (resp. u 2 ′ u'_2 u 2 ′ ) until it reaches a vertex in V ( P i 0 ) V(P_{i_0}) V ( P i 0 ) , which we denote by w 1 w_1 w 1 (resp. w 2 w_2 w 2 ). Such vertices w 1 w_1 w 1 and w 2 w_2 w 2 exist because u 1 u_1 u 1 (resp. u 2 u_2 u 2 ) are common vertices of R 1 R_1 R 1 (resp. R 2 R_2 R 2 ) and P i 0 P_{i_0} P i 0 . Note that there is an i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] such that the subpath of P i 0 P_{i_0} P i 0 starting from u i u_i u i and finishing at w 1 w_1 w 1 does not contain w 2 w_2 w 2 . We fix such i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] . We consider the following path from u 1 ′ u'_1 u 1 ′ to u i u_i u i : We start following R 1 R_1 R 1 starting from u 1 ′ u'_1 u 1 ′ , and then, when having reached w 1 w_1 w 1 , we continue along P i 0 P_{i_0} P i 0 until we reach u i u_i u i . We denote this path by Y 1 Y_1 Y 1 . Also, we consider the graph Y 2 Y_2 Y 2 obtained by the union of P i 0 − V ( Y 1 ) P_{i_0}-V(Y_1) P i 0 − V ( Y 1 ) and the subpath of R 2 R_2 R 2 starting from u 2 ′ u'_2 u 2 ′ and finishing at w 2 w_2 w 2 . See Figure 4 . Observe that both Y 2 − { u 2 ′ } Y_2-\{u'_2\} Y 2 − { u 2 ′ } and Y 1 − { u 1 ′ } Y_1-\{u'_1\} Y 1 − { u 1 ′ } are connected subgraphs of G G G that are disjoint from V ( G 0 ) V(G_0) V ( G 0 ) , and have (at least) an edge between them. Our aim now is to extend the model of L k − 1 L_{k-1} L k − 1 in G 0 G_0 G 0 to a model of L k L_k L k in G G G by including the sets V ( Y 2 ) − { u 2 ′ } V(Y_2)-\{u'_2\} V ( Y 2 ) − { u 2 ′ } and V ( Y 1 ) − { u 1 ′ } V(Y_1)-\{u'_1\} V ( Y 1 ) − { u 1 ′ } . Still, we need an extra argument so as to ensure condition (i) from the statement of the lemma, i.e., extend one of the new bags of the model so as to include s s s .
Figure 4. The construction of the desired model of L k L_k L k in the proof of Theorem 32. The vertices in S S S are depicted by red squares. We are here in the case j = 1 j=1 j = 1 , i.e. z ∈ V ( Y 1 ) z \in V(Y_1) z ∈ V ( Y 1 ) .
For this, we consider a certain subpath of Q j 0 Q_{j_0} Q j 0 : following the path Q j 0 Q_{j_0} Q j 0 starting from s s s , let z z z be the first vertex of V ( Y 1 ) ∪ V ( Y 2 ) V(Y_1)\cup V(Y_2) V ( Y 1 ) ∪ V ( Y 2 ) reached by Q j 0 Q_{j_0} Q j 0 ; such vertex exists because u j 0 u_{j_0} u j 0 is a common endpoint of Q j 0 Q_{j_0} Q j 0 and P i 0 P_{i_0} P i 0 , and V ( P i 0 ) ⊆ V ( Y 1 ) ∪ V ( Y 2 ) V(P_{i_0})\subseteq V(Y_1)\cup V(Y_2) V ( P i 0 ) ⊆ V ( Y 1 ) ∪ V ( Y 2 ) . We denote by Q ′ Q' Q ′ the subpath of Q j 0 Q_{j_0} Q j 0 starting from s s s and finishing at z z z . Let j ∈ [ 2 ] j\in[2] j ∈ [ 2 ] such that z ∈ V ( Y j ) z\in V(Y_j) z ∈ V ( Y j ) . We proceed to the construction of a model L k L_k L k in G G G .
We label the vertices L k L_k L k by adding to L k − 1 L_{k-1} L k − 1 a new column ( c 1 , c 2 ) (c_1,c_2) ( c 1 , c 2 ) next to the first column of L k − 1 L_{k-1} L k − 1 , namely ( c 1 0 , c 2 0 ) (c_1^0,c_2^0) ( c 1 0 , c 2 0 ) . Then, for every x ∈ V ( L k ) x \in V(L_k) x ∈ V ( L k ) , let
B x = { B x 1 if x ∈ V ( L k − 1 ) , ( V ( Y j ) ∖ { u j 0 } ) ∪ V ( Q ′ ) if x = c j , V ( Y 3 − j ) ∖ { u 3 − j ′ } if x = c 3 − j . B_x =
\begin{cases}
B_x^1 & \text{if } x \in V(L_{k-1}),\\
\left(V(Y_j)\setminus\{u_j^0\}\right) \cup V(Q') & \text{if } x=c_j,\\
V(Y_{3-j})\setminus\{u_{3-j}'\} & \text{if } x=c_{3-j}.
\end{cases} B x = ⎩ ⎨ ⎧ B x 1 ( V ( Y j ) ∖ { u j 0 } ) ∪ V ( Q ′ ) V ( Y 3 − j ) ∖ { u 3 − j ′ } if x ∈ V ( L k − 1 ) , if x = c j , if x = c 3 − j .
This gives the desired model of L k L_k L k in G G G .
Proof of Theorem 26. We set for every positive integer k k k
f ( k ) = { 2 if k = 1 , f 32 ( k , 2 k − 1 ) + 1 otherwise. f(k)=
\begin{cases}
2 & \text{if } k=1,\\
f_{32}(k,2k-1)+1 & \text{otherwise.}
\end{cases} f ( k ) = { 2 f 32 ( k , 2 k − 1 ) + 1 if k = 1 , otherwise.
Let k k k be a positive integer, and let ( G , S ) (G,S) ( G , S ) be an annotated graph with td 2 ( G , S ) ≥ f ( k ) \operatorname{td}_2(G,S) \ge f(k) td 2 ( G , S ) ≥ f ( k ) . By Theorem 27, we can assume that G G G has only one block, namely G G G itself. If k = 1 k=1 k = 1 , then clearly there is a vertex in S S S which is not isolated, and so ( L 1 , T 1 ) (L_1,T_1) ( L 1 , T 1 ) is a minor of ( G , S ) (G,S) ( G , S ) . Now suppose k ≥ 2 k \ge2 k ≥ 2 . Fix two vertices u 1 , u 2 u_1,u_2 u 1 , u 2 of G G G . (This is possible since 2 ≤ td 2 ( G , S ) ≤ ∣ V ( G ) ∣ 2 \le\operatorname{td}_2(G,S) \le|V(G)| 2 ≤ td 2 ( G , S ) ≤ ∣ V ( G ) ∣ .) By Theorem 32, either
(a) there is a model of ( L k , T k ) (L_k,T_k) ( L k , T k ) in ( G , S ) (G,S) ( G , S ) , or
(b) there is a model ( B x ∣ x ∈ V ( L 2 k − 1 ) ) (B_x \mid x \in V(L_{2k-1})) ( B x ∣ x ∈ V ( L 2 k − 1 )) of L 2 k − 1 L_{2k-1} L 2 k − 1 in G G G such that
(i) for every column C C C of L 2 k − 1 L_{2k-1} L 2 k − 1 , S ∩ ( ⋃ c ∈ C B c ) ≠ ∅ S \cap\left(\bigcup_{c\in C} B_c\right) \ne\varnothing S ∩ ( ⋃ c ∈ C B c ) = ∅ , and
(ii) if { c 1 , c 2 } \{c_1,c_2\} { c 1 , c 2 } is the first column of L 2 k − 1 L_{2k-1} L 2 k − 1 , then u 1 ∈ B c 1 u_1 \in B_{c_1} u 1 ∈ B c 1 and u 2 ∈ B c 2 u_2 \in B_{c_2} u 2 ∈ B c 2 or vice-versa.
In the first case, we are done. Now suppose we are in the second case. Then, by the pigeonhole principle, there is a row R R R of L 2 k − 1 L_{2k-1} L 2 k − 1 such that for at least k k k vertices x x x in R R R we have S ∩ B x ≠ ∅ S \cap B_x \ne\varnothing S ∩ B x = ∅ . Contracting in this model all the other columns with one of their neighboring columns, we find a model of ( L k , T k ) (L_k,T_k) ( L k , T k ) in ( G , S ) (G,S) ( G , S ) .
Hadwiger number
The Hadwiger number of a graph G G G , denoted by had ( G ) \operatorname{had}(G) had ( G ) , is the maximum number k ∈ N k \in\mathbb{N} k ∈ N such that G G G contains K k K_k K k as a minor. The main result of this subsection is the following theorem. Together with Theorem 6, Theorem 33 implies the Hadwiger number statement in Theorem 1.
Theorem 33. For every annotated graph ( G , S ) (G,S) ( G , S ) and for every positive integer k k k , if had ( G , S ) ≥ 2 k \operatorname{had}(G,S) \ge2k had ( G , S ) ≥ 2 k , then K k K_k K k is an S S S -rooted minor of G G G .
Note that such a statement with 2 k 2k 2 k replaced by Ω ( k 2300 ) \Omega(k^{2300}) Ω ( k 2300 ) follows from [21 Theorem 1.2] . The exact statement of Theorem 33 follows from a result of Dujmović et al. [9 Corollary 13] , which was inspired by the work of Kawarabayashi on rooted minors [16 ] , which is itself based on [27 Statement 5.4] by Robertson and Seymour. We include the proof of Theorem 33, which is an adaptation of the generic folio technique and, in particular, of the argument in [9 ] .
Given a graph G G G and F ⊆ ( V ( G ) 2 ) F \subseteq\binom{V(G)}{2} F ⊆ ( 2 V ( G ) ) , we denote by G ∪ F G \cup F G ∪ F the graph ( V ( G ) , E ( G ) ∪ F ) (V(G),E(G)\cup F) ( V ( G ) , E ( G ) ∪ F ) .
Lemma 34. Let k k k be a positive integer. Let ( G , S ) (G,S) ( G , S ) be an annotated graph and let M = ( U x ∣ x ∈ V ( K 2 k ) ) \mathcal{M}=(U_x \mid x \in V(K_{2k})) M = ( U x ∣ x ∈ V ( K 2 k )) be a model of K 2 k K_{2k} K 2 k in G ∪ ( S 2 ) G \cup\binom{S}{2} G ∪ ( 2 S ) such that S S S intersects at most k k k branch sets in M \mathcal{M} M , i.e., ∣ { x ∈ V ( K 2 k ) ∣ U x ∩ S ≠ ∅ } ∣ ≤ k \left|\{x \in V(K_{2k}) \mid U_x \cap S \ne\varnothing\}\right| \le k ∣ { x ∈ V ( K 2 k ) ∣ U x ∩ S = ∅ } ∣ ≤ k . Then one of the following holds:
(i) K k K_k K k is an S S S -rooted minor of G G G , or
(ii) there is a separation ( A , B ) (A,B) ( A , B ) of G G G of order at most k − 1 k-1 k − 1 such that S ⊆ V ( A ) S \subseteq V(A) S ⊆ V ( A ) , and there exists z ∈ V ( K 2 k ) z \in V(K_{2k}) z ∈ V ( K 2 k ) with U z ⊆ V ( B ) ∖ V ( A ) U_z \subseteq V(B)\setminus V(A) U z ⊆ V ( B ) ∖ V ( A ) .
Proof. Suppose that the statement does not hold, and consider a counterexample ( G , S , M ) (G,S,\mathcal{M}) ( G , S , M ) with ∣ V ( G ) ∣ |V(G)| ∣ V ( G ) ∣ minimum.
Claim 35. There is no separation ( A , B ) (A,B) ( A , B ) of G G G of order at most k k k such that S ⊆ V ( A ) S \subseteq V(A) S ⊆ V ( A ) , V ( A ) ∖ S ≠ ∅ V(A)\setminus S \ne\emptyset V ( A ) ∖ S = ∅ , and U z ⊆ V ( B ) ∖ V ( A ) U_z \subseteq V(B)\setminus V(A) U z ⊆ V ( B ) ∖ V ( A ) for some z ∈ V ( K 2 k ) z \in V(K_{2k}) z ∈ V ( K 2 k ) .
Proof of the claim. Suppose that such a separation ( A , B ) (A,B) ( A , B ) exists, and let z z z be as in the statement. Since G G G , S S S , and M \mathcal{M} M are a counterexample to the lemma, there is no separation ( A ′ , B ′ ) (A',B') ( A ′ , B ′ ) of G G G of order at most k − 1 k-1 k − 1 with S ⊆ V ( A ′ ) S \subseteq V(A') S ⊆ V ( A ′ ) and V ( B ) ⊆ V ( B ′ ) V(B) \subseteq V(B') V ( B ) ⊆ V ( B ′ ) . Therefore, by Menger’s theorem, there is a family ( P u ∣ u ∈ V ( A ) ∩ V ( B ) ) (P_u \mid u \in V(A)\cap V(B)) ( P u ∣ u ∈ V ( A ) ∩ V ( B )) of pairwise disjoint S S S –( V ( A ) ∩ V ( B ) ) (V(A)\cap V(B)) ( V ( A ) ∩ V ( B )) paths in G G G with u ∈ V ( P u ) u \in V(P_u) u ∈ V ( P u ) for every u ∈ V ( A ) ∩ V ( B ) u \in V(A)\cap V(B) u ∈ V ( A ) ∩ V ( B ) . Note that, for all u ∈ V ( A ) ∩ V ( B ) u \in V(A)\cap V(B) u ∈ V ( A ) ∩ V ( B ) , P u P_u P u is a path in A A A . Now, for every x ∈ V ( K 2 k ) x \in V(K_{2k}) x ∈ V ( K 2 k ) , let U x ′ = U x ∩ V ( B ) U'_x=U_x\cap V(B) U x ′ = U x ∩ V ( B ) . Since ∣ V ( A ) ∩ V ( B ) ∣ ≤ k |V(A)\cap V(B)|\leq k ∣ V ( A ) ∩ V ( B ) ∣ ≤ k and U z ⊆ V ( B ) ∖ V ( A ) U_z\subseteq V(B)\setminus V(A) U z ⊆ V ( B ) ∖ V ( A ) , U x ′ U'_x U x ′ is non-empty for every x ∈ V ( K 2 k ) x\in V(K_{2k}) x ∈ V ( K 2 k ) . Note that every path in G [ A ] G[A] G [ A ] between vertices in V ( A ) ∩ V ( B ) V(A)\cap V(B) V ( A ) ∩ V ( B ) can be simulated by an edge between these two vertices and therefore M ′ = ( U x ′ ∣ x ∈ V ( K 2 k ) ) \mathcal{M}'=(U'_x\mid x\in V(K_{2k})) M ′ = ( U x ′ ∣ x ∈ V ( K 2 k )) is a model of K 2 k K_{2k} K 2 k in B ∪ ( V ( A ) ∩ V ( B ) 2 ) B\cup\binom{V(A)\cap V(B)}{2} B ∪ ( 2 V ( A ) ∩ V ( B ) ) . Note that
∣ { x ∈ V ( K 2 k ) ∣ U x ′ ∩ V ( A ) ∩ V ( B ) ≠ ∅ } ∣ ≤ ∣ V ( A ) ∩ V ( B ) ∣ ≤ k . |\{x\in V(K_{2k})\mid U'_x\cap V(A)\cap V(B)\ne\emptyset\}|\leq|V(A)\cap V(B)|\leq k. ∣ { x ∈ V ( K 2 k ) ∣ U x ′ ∩ V ( A ) ∩ V ( B ) = ∅ } ∣ ≤ ∣ V ( A ) ∩ V ( B ) ∣ ≤ k .
We next show that ∣ V ( B ) ∣ < ∣ V ( G ) ∣ |V(B)|<|V(G)| ∣ V ( B ) ∣ < ∣ V ( G ) ∣ , which implies that the statement of the lemma holds for B B B , V ( A ) ∩ V ( B ) V(A)\cap V(B) V ( A ) ∩ V ( B ) , and M ′ \mathcal{M}' M ′ because of minimality of the counterexample. To see why ∣ V ( B ) ∣ < ∣ V ( G ) ∣ |V(B)|<|V(G)| ∣ V ( B ) ∣ < ∣ V ( G ) ∣ holds, consider a vertex w ∈ V ( A ) ∖ S w\in V(A)\setminus S w ∈ V ( A ) ∖ S ; this exists because of the assumption in the statement of the claim. If w ∉ V ( B ) w\notin V(B) w ∈ / V ( B ) , then we get directly that ∣ V ( B ) ∣ < ∣ V ( G ) ∣ |V(B)|<|V(G)| ∣ V ( B ) ∣ < ∣ V ( G ) ∣ . If w ∈ V ( A ) ∩ V ( B ) w\in V(A)\cap V(B) w ∈ V ( A ) ∩ V ( B ) , then the endpoint of P w P_w P w in S S S does not belong to V ( B ) V(B) V ( B ) and hence we get ∣ V ( B ) ∣ < ∣ V ( G ) ∣ |V(B)|<|V(G)| ∣ V ( B ) ∣ < ∣ V ( G ) ∣ . Thus, the statement of the lemma holds for B B B , V ( A ) ∩ V ( B ) V(A)\cap V(B) V ( A ) ∩ V ( B ) , and M ′ \mathcal{M}' M ′ .
If (i) holds, then there is a ( V ( A ) ∩ V ( B ) ) (V(A)\cap V(B)) ( V ( A ) ∩ V ( B )) -rooted model ( V x ∣ x ∈ V ( K k ) ) (V_x\mid x\in V(K_k)) ( V x ∣ x ∈ V ( K k )) of K k K_k K k in B B B . For each x ∈ V ( K k ) x\in V(K_k) x ∈ V ( K k ) , let u x ∈ V ( A ) ∩ V ( B ) ∩ V x u_x\in V(A)\cap V(B)\cap V_x u x ∈ V ( A ) ∩ V ( B ) ∩ V x . Then, ( V x ∪ V ( P u x ) ∣ x ∈ V ( K k ) ) (V_x\cup V(P_{u_x})\mid x\in V(K_k)) ( V x ∪ V ( P u x ) ∣ x ∈ V ( K k )) is an S S S -rooted model of K k K_k K k in G G G contradicting G G G , S S S , and M \mathcal{M} M being a counterexample.
If (ii) holds, there is a separation ( A ′ , B ′ ) (A',B') ( A ′ , B ′ ) of B B B with V ( A ) ∩ V ( B ) ⊆ V ( A ′ ) V(A)\cap V(B)\subseteq V(A') V ( A ) ∩ V ( B ) ⊆ V ( A ′ ) and U z ′ ′ ⊆ V ( B ′ ) ∖ V ( A ′ ) U'_{z'}\subseteq V(B')\setminus V(A') U z ′ ′ ⊆ V ( B ′ ) ∖ V ( A ′ ) for some z ′ ∈ V ( K 2 k ) z'\in V(K_{2k}) z ′ ∈ V ( K 2 k ) . But then we have U z ′ ′ = U z ′ U'_{z'}=U_{z'} U z ′ ′ = U z ′ , and ( A ∪ A ′ , B ′ ) (A\cup A',B') ( A ∪ A ′ , B ′ ) is a separation of G G G of order at most k − 1 k-1 k − 1 , with S ⊆ V ( A ∪ A ′ ) S\subseteq V(A\cup A') S ⊆ V ( A ∪ A ′ ) and U z ′ ⊆ V ( B ′ ) ∖ V ( A ∪ A ′ ) U_{z'}\subseteq V(B')\setminus V(A\cup A') U z ′ ⊆ V ( B ′ ) ∖ V ( A ∪ A ′ ) , again contradicting the fact that ( G , S , M ) (G,S,\mathcal{M}) ( G , S , M ) is a counterexample. ◇
Claim 36. For every x ∈ V ( K 2 k ) x\in V(K_{2k}) x ∈ V ( K 2 k ) , either U x ⊆ S U_x\subseteq S U x ⊆ S , or ∣ U x ∣ = 1 |U_x|=1 ∣ U x ∣ = 1 .
Proof of the claim. Assume otherwise, and let y ∈ V ( K 2 k ) y\in V(K_{2k}) y ∈ V ( K 2 k ) be such that U y ⊈ S U_y\not\subseteq S U y ⊆ S and ∣ U y ∣ > 1 |U_y|>1 ∣ U y ∣ > 1 . In particular, G [ U y ] G[U_y] G [ U y ] has an edge u v uv uv with { u , v } ⊈ S \{u,v\}\not\subseteq S { u , v } ⊆ S . Let G ′ G' G ′ be obtained from G G G by contracting u v uv uv into a single vertex w w w , let
S ′ = { ( S ∖ { u , v } ) ∪ { w } if { u , v } ∩ S ≠ ∅ , S otherwise, S'=
\begin{cases}
(S\setminus\{u,v\})\cup\{w\} & \text{if }\{u,v\}\cap S\ne\emptyset,\\
S & \text{otherwise,}
\end{cases} S ′ = { ( S ∖ { u , v }) ∪ { w } S if { u , v } ∩ S = ∅ , otherwise,
and let M ′ = { U x ′ ∣ x ∈ V ( K 2 k ) } \mathcal{M}'=\{U'_x\mid x\in V(K_{2k})\} M ′ = { U x ′ ∣ x ∈ V ( K 2 k )} where, for every x ∈ V ( K 2 k ) x\in V(K_{2k}) x ∈ V ( K 2 k ) ,
U x ′ = { ( U x ∖ { u , v } ) ∪ { w } if { u , v } ∩ U x ≠ ∅ (in other words, if x = y ) , U x otherwise. U'_x=
\begin{cases}
(U_x\setminus\{u,v\})\cup\{w\} & \text{if }\{u,v\}\cap U_x\ne\emptyset\text{ (in other words, if }x=y\text{)},\\
U_x & \text{otherwise.}
\end{cases} U x ′ = { ( U x ∖ { u , v }) ∪ { w } U x if { u , v } ∩ U x = ∅ (in other words, if x = y ) , otherwise.
Note that M ′ \mathcal{M}' M ′ is a model of K 2 k K_{2k} K 2 k in G ′ ∪ ( S ′ 2 ) G'\cup\binom{S'}{2} G ′ ∪ ( 2 S ′ ) with
∣ { x ∈ V ( K 2 k ) ∣ U x ′ ∩ S ′ ≠ ∅ } ∣ = ∣ { x ∈ V ( K 2 k ) ∣ U x ∩ S ≠ ∅ } ∣ ≤ k . |\{x\in V(K_{2k})\mid U'_x\cap S'\ne\emptyset\}|=|\{x\in V(K_{2k})\mid U_x\cap S\ne\emptyset\}|\leq k. ∣ { x ∈ V ( K 2 k ) ∣ U x ′ ∩ S ′ = ∅ } ∣ = ∣ { x ∈ V ( K 2 k ) ∣ U x ∩ S = ∅ } ∣ ≤ k .
Since ∣ V ( G ′ ) ∣ < ∣ V ( G ) ∣ |V(G')|<|V(G)| ∣ V ( G ′ ) ∣ < ∣ V ( G ) ∣ , the statement of the lemma holds for G ′ G' G ′ , S ′ S' S ′ , and M ′ \mathcal{M}' M ′ . The annotated graph ( G ′ , S ′ ) (G',S') ( G ′ , S ′ ) is a minor of ( G , S ) (G,S) ( G , S ) , hence, if G ′ G' G ′ contains K k K_k K k as an S ′ S' S ′ -rooted minor, then G G G also contains K k K_k K k as an S S S -rooted minor. Thus, if (i) holds for ( G ′ , S ′ , M ′ ) (G',S',\mathcal{M}') ( G ′ , S ′ , M ′ ) , then it also holds for ( G , S , M ) (G,S,\mathcal{M}) ( G , S , M ) , which contradicts the fact that it is a counterexample.
If (ii) holds for ( G ′ , S ′ , M ′ ) (G',S',\mathcal{M}') ( G ′ , S ′ , M ′ ) , then there is a separation ( A ′ , B ′ ) (A',B') ( A ′ , B ′ ) of G ′ G' G ′ of order at most k − 1 k-1 k − 1 with U z ′ ⊆ V ( B ′ ) ∖ V ( A ′ ) U'_z \subseteq V(B')\setminus V(A') U z ′ ⊆ V ( B ′ ) ∖ V ( A ′ ) for some z ∈ V ( K 2 k ) z \in V(K_{2k}) z ∈ V ( K 2 k ) . Let ( A , B ) (A,B) ( A , B ) be the separation of G G G obtained from ( A ′ , B ′ ) (A',B') ( A ′ , B ′ ) by uncontracting the edge u v uv uv . Note that ( A , B ) (A,B) ( A , B ) has order at most k k k . If ( A , B ) (A,B) ( A , B ) has order at most k − 1 k-1 k − 1 , this contradicts the fact that ( G , S , M ) (G,S,\mathcal{M}) ( G , S , M ) is a counterexample. Thus, we suppose that ( A , B ) (A,B) ( A , B ) is of order exactly k k k , and so u , v ∈ V ( A ) ∩ V ( B ) u,v \in V(A)\cap V(B) u , v ∈ V ( A ) ∩ V ( B ) . In particular, V ( A ) ∖ S ≠ ∅ V(A)\setminus S \ne\emptyset V ( A ) ∖ S = ∅ . Since we also have S ⊆ V ( A ) S \subseteq V(A) S ⊆ V ( A ) and U z ⊆ V ( B ) ∖ V ( A ) U_z \subseteq V(B)\setminus V(A) U z ⊆ V ( B ) ∖ V ( A ) , this contradicts Theorem 35.
Let T = ⋃ x ∈ V ( K 2 k ) , U x ∩ S = ∅ U x T=\bigcup_{x\in V(K_{2k}),U_x\cap S=\emptyset} U_x T = ⋃ x ∈ V ( K 2 k ) , U x ∩ S = ∅ U x . By Theorem 36, T T T induces a complete graph in G G G , which has size at least k k k since ∣ { x ∈ V ( K 2 k ) ∣ U x ∩ S ≠ ∅ } ∣ ≤ k |\{x\in V(K_{2k})\mid U_x\cap S\ne\emptyset\}|\le k ∣ { x ∈ V ( K 2 k ) ∣ U x ∩ S = ∅ } ∣ ≤ k . By Menger’s theorem, either there is a separation ( A , B ) (A,B) ( A , B ) of G G G of order at most k − 1 k-1 k − 1 with S ⊆ V ( A ) S\subseteq V(A) S ⊆ V ( A ) and T ⊆ V ( B ) T\subseteq V(B) T ⊆ V ( B ) or there are k k k pairwise disjoint S S S –T T T paths Q 1 , … , Q k Q_1,\ldots,Q_k Q 1 , … , Q k in G G G . In the former case, there exists u ∈ T ∖ ( V ( A ) ∩ V ( B ) ) u\in T\setminus(V(A)\cap V(B)) u ∈ T ∖ ( V ( A ) ∩ V ( B )) , and so, there exists z ∈ V ( K 2 k ) z\in V(K_{2k}) z ∈ V ( K 2 k ) with U z ⊆ V ( B ) ∖ V ( A ) U_z\subseteq V(B)\setminus V(A) U z ⊆ V ( B ) ∖ V ( A ) . This implies (ii) for G G G , S S S , and M \mathcal{M} M , which is a contradiction. In the latter case, ( V ( Q i ) ∣ i ∈ [ k ] ) (V(Q_i)\mid i\in[k]) ( V ( Q i ) ∣ i ∈ [ k ]) is an S S S -rooted model of K k K_k K k in G G G , which is also a contradiction with G G G , S S S , and M \mathcal{M} M being a counterexample. This completes the proof of the lemma.
Corollary 37. Let k k k be a positive integer and let ( G , S ) (G,S) ( G , S ) be an annotated graph with ∣ S ∣ ≤ k |S|\le k ∣ S ∣ ≤ k and S ≠ ∅ S\ne\emptyset S = ∅ . If K 2 k K_{2k} K 2 k is a minor of G ∪ ( S ) G\cup(S) G ∪ ( S ) , then, for some ℓ ∈ [ k ] \ell\in[k] ℓ ∈ [ k ] , there is a separation ( A , B ) (A,B) ( A , B ) in G G G of order ℓ \ell ℓ such that V ( B ) ∖ V ( A ) ≠ ∅ V(B)\setminus V(A)\ne\emptyset V ( B ) ∖ V ( A ) = ∅ , S ⊆ V ( A ) S\subseteq V(A) S ⊆ V ( A ) , and K ℓ K_\ell K ℓ is an ( V ( A ) ∩ V ( B ) ) (V(A)\cap V(B)) ( V ( A ) ∩ V ( B )) -rooted minor of B B B .
Proof. We proceed by induction on k k k . For k = 1 k=1 k = 1 , one can take A A A to be a 1-vertex graph containing the vertex of S S S , and B = G B=G B = G . Note that V ( B ) ∖ V ( A ) V(B)\setminus V(A) V ( B ) ∖ V ( A ) is non empty, and the unique vertex of A A A forms a ( V ( A ) ∩ V ( B ) ) (V(A)\cap V(B)) ( V ( A ) ∩ V ( B )) -rooted model of K 1 K_1 K 1 in B B B . Now, assume that k ≥ 2 k\ge2 k ≥ 2 and that the result holds for all positive integers less than k k k . Let M = ( U x ∣ x ∈ V ( K 2 k ) ) \mathcal{M}=(U_x\mid x\in V(K_{2k})) M = ( U x ∣ x ∈ V ( K 2 k )) be a model of K 2 k K_{2k} K 2 k in G ∪ ( S ) G\cup(S) G ∪ ( S ) . Since ∣ S ∣ ≤ k |S|\le k ∣ S ∣ ≤ k , at most k k k sets in M \mathcal{M} M intersect S S S . Apply then Theorem 34 to G G G , S S S , M \mathcal{M} M . If there is an S S S -rooted model of K k K_k K k in G G G , then take A A A to be the graph with vertex set S S S with no edges and B B B to be the whole graph G G G , and the lemma is satisfied with ℓ = k \ell=k ℓ = k (note that V ( B ) ∖ V ( A ) ≠ ∅ V(B)\setminus V(A)\ne\emptyset V ( B ) ∖ V ( A ) = ∅ since ∣ V ( G ) ∣ ≥ 2 k > ∣ S ∣ |V(G)|\ge2k>|S| ∣ V ( G ) ∣ ≥ 2 k > ∣ S ∣ ). Otherwise, there exists a separation ( C , D ) (C,D) ( C , D ) in G G G of order at most k − 1 k-1 k − 1 and z ∈ V ( K 2 k ) z\in V(K_{2k}) z ∈ V ( K 2 k ) such that S ⊆ V ( C ) S\subseteq V(C) S ⊆ V ( C ) and U z ⊆ V ( D ) ∖ V ( C ) U_z\subseteq V(D)\setminus V(C) U z ⊆ V ( D ) ∖ V ( C ) . Let Z Z Z be the connected component of D D D containing U z U_z U z . Since z z z is adjacent to every other vertex in K 2 k K_{2k} K 2 k , U x U_x U x contains a vertex of Z Z Z for every x ∈ V ( K 2 k ) x\in V(K_{2k}) x ∈ V ( K 2 k ) . Let M Z \mathcal{M}_Z M Z be obtained from M \mathcal{M} M by replacing each branch set in M \mathcal{M} M by its intersection with V ( Z ) V(Z) V ( Z ) . Let S ′ = V ( C ) ∩ V ( Z ) S'=V(C)\cap V(Z) S ′ = V ( C ) ∩ V ( Z ) and keep in mind that ∣ S ′ ∣ ≤ k − 1 |S'|\le k-1 ∣ S ′ ∣ ≤ k − 1 . Observe that M Z \mathcal{M}_Z M Z is a model of K 2 k K_{2k} K 2 k in Z ∪ ( S ′ ) Z\cup(S') Z ∪ ( S ′ ) . By the induction hypothesis applied to Z , S ′ Z,S' Z , S ′ , and a restriction of M Z \mathcal{M}_Z M Z to a model of K 2 ( k − 1 ) K_{2(k-1)} K 2 ( k − 1 ) , there is a separation ( A ′ , B ′ ) (A',B') ( A ′ , B ′ ) in Z Z Z of order ℓ = ∣ V ( A ′ ) ∩ V ( B ′ ) ∣ ≤ k − 1 \ell=|V(A')\cap V(B')|\le k-1 ℓ = ∣ V ( A ′ ) ∩ V ( B ′ ) ∣ ≤ k − 1 such that V ( B ′ ) ∖ V ( A ′ ) ≠ ∅ V(B')\setminus V(A')\ne\emptyset V ( B ′ ) ∖ V ( A ′ ) = ∅ , S ′ ⊆ V ( A ′ ) S'\subseteq V(A') S ′ ⊆ V ( A ′ ) , and K ℓ K_\ell K ℓ is a ( V ( A ′ ) ∩ V ( B ′ ) ) (V(A')\cap V(B')) ( V ( A ′ ) ∩ V ( B ′ )) -rooted minor of B ′ B' B ′ . Finally, put A = C ∪ A ′ ∪ ( D − V ( Z ) ) A=C\cup A'\cup(D-V(Z)) A = C ∪ A ′ ∪ ( D − V ( Z )) and B = B ′ B=B' B = B ′ . It follows that the separation ( A , B ) (A,B) ( A , B ) has the desired properties.
Proof of Theorem 33. Suppose that there is no S S S -rooted model of K k K_k K k in G G G . We will show that there is a set S ′ S' S ′ with S ⊆ S ′ ⊆ V ( G ) S\subseteq S'\subseteq V(G) S ⊆ S ′ ⊆ V ( G ) such that torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) does not contain K 2 k K_{2k} K 2 k as a minor. We proceed by induction on ∣ V ( G ) ∣ |V(G)| ∣ V ( G ) ∣ . If G G G is not connected, then we apply the induction hypothesis on each connected component and we are done. Now suppose that G G G is connected. If G G G does not contain K 2 k K_{2k} K 2 k as a minor, then we are done because torso G ( V ( G ) ) = G \operatorname{torso}_G(V(G))=G torso G ( V ( G )) = G . Otherwise, let M = ( U x ∣ x ∈ V ( K 2 k ) ) \mathcal{M}=(U_x\mid x\in V(K_{2k})) M = ( U x ∣ x ∈ V ( K 2 k )) be a model of K 2 k K_{2k} K 2 k in G G G . We assume that S S S intersects at most k k k branch sets of M \mathcal{M} M , since otherwise K k K_k K k is an S S S -rooted minor of G G G . So, by Theorem 34 , there is a separation ( A , B ) (A,B) ( A , B ) of G G G with S ⊆ V ( A ) S\subseteq V(A) S ⊆ V ( A ) and U z ⊆ V ( B ) ∖ V ( A ) U_z\subseteq V(B)\setminus V(A) U z ⊆ V ( B ) ∖ V ( A ) for some z ∈ V ( K 2 k ) z\in V(K_{2k}) z ∈ V ( K 2 k ) . Then, since z z z is adjacent to every other vertex in K 2 k K_{2k} K 2 k , the family ( U x ∩ V ( B ) ∣ x ∈ V ( K 2 k ) ) (U_x \cap V(B) \mid x \in V(K_{2k})) ( U x ∩ V ( B ) ∣ x ∈ V ( K 2 k )) is a model of K 2 k K_{2k} K 2 k in B ∪ ( V ( A ) ∩ V ( B ) ) B \cup(V(A)\cap V(B)) B ∪ ( V ( A ) ∩ V ( B )) . By Theorem 37, there is a separation ( C , D ) (C,D) ( C , D ) of B B B with V ( C ) ∩ V ( D ) ≠ ∅ V(C)\cap V(D) \ne\emptyset V ( C ) ∩ V ( D ) = ∅ , V ( A ) ∩ V ( B ) ⊆ V ( C ) V(A)\cap V(B) \subseteq V(C) V ( A ) ∩ V ( B ) ⊆ V ( C ) , and such that there is a ( V ( C ) ∩ V ( D ) ) (V(C)\cap V(D)) ( V ( C ) ∩ V ( D )) -rooted model of K ∣ V ( C ) ∩ V ( D ) ∣ K_{|V(C)\cap V(D)|} K ∣ V ( C ) ∩ V ( D ) ∣ in D D D . In particular, this implies that G ′ = torso G ( V ( C ) ∪ V ( A ) ) G' = \operatorname{torso}_G(V(C) \cup V(A)) G ′ = torso G ( V ( C ) ∪ V ( A )) has no S S S -rooted model of K k K_k K k . So, by the induction hypothesis, there exists S ′ ⊆ V ( C ) ∪ V ( A ) ⊆ V ( G ) S' \subseteq V(C) \cup V(A) \subseteq V(G) S ′ ⊆ V ( C ) ∪ V ( A ) ⊆ V ( G ) with S ⊆ S ′ S \subseteq S' S ⊆ S ′ such that torso G ′ ( S ′ ) \operatorname{torso}_{G'}(S') torso G ′ ( S ′ ) is K 2 k K_{2k} K 2 k -minor-free. Since torso G ′ ( S ′ ) = torso G ( S ′ ) \operatorname{torso}_{G'}(S') = \operatorname{torso}_G(S') torso G ′ ( S ′ ) = torso G ( S ′ ) , this proves the theorem. □
Erdős–Pósa property of lollipops
Let G G G be a graph and S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) . An S S S -lollipop in G G G is a subgraph of G G G that is the union of a cycle C C C and a path P P P such that V ( P ) V(P) V ( P ) intersects both V ( C ) V(C) V ( C ) and S S S . Note that an annotated graph ( G , S ) (G,S) ( G , S ) contains a lollipop if and only if ( K 3 , T ) (K_3,T) ( K 3 , T ) is a minor of ( G , S ) (G,S) ( G , S ) , where T T T is a singleton in V ( K 3 ) V(K_3) V ( K 3 ) . Therefore, the next theorem implies Theorem 3 .
Theorem 38. There exists an absolute constant c c c such that for every graph G G G , for every S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) , and for every positive integer k k k , either
(i) G G G has k k k disjoint S S S -lollipops or
(ii) there exists a set Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) such that ∣ Z ∣ ≤ c ⋅ k log k |Z| \le c \cdot k \log k ∣ Z ∣ ≤ c ⋅ k log k and G − Z G-Z G − Z has no S S S -lollipops.
We will use the following classical lemma of Simonovits [30 ] . First, for every positive integer k k k , let
s ( k ) = { ⌈ 4 k ( log k + log log k + 4 ) ⌉ if k ≥ 2 , 2 if k = 1. s(k) =
\begin{cases}
\lceil4k(\log k + \log\log k + 4)\rceil& \text{if } k \ge2,\\
2 & \text{if } k = 1.
\end{cases} s ( k ) = { ⌈ 4 k ( log k + log log k + 4 )⌉ 2 if k ≥ 2 , if k = 1.
Note that s ( k ) ∈ O ( k log k ) s(k) \in O(k\log k) s ( k ) ∈ O ( k log k ) .
Lemma 39 ([30 ] ). Let k k k be a positive integer and let H H H be a graph with all vertices of degree 2 or 3. If H H H contains at least s ( k ) s(k) s ( k ) vertices of degree 3, then H H H contains k k k pairwise disjoint cycles.
We will use as a black-box the Erdős–Pósa Theorem.
Theorem 40 (Erdős–Pósa Theorem [10 ] ). There is a function ep : N → N \operatorname{ep}: \mathbb{N} \to\mathbb{N} ep : N → N such that the following holds. For every graph G G G and every positive integer k k k , either
(1) G G G has k k k pairwise disjoint cycles, or
(2) there exists Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) such that ∣ Z ∣ ≤ ep ( k ) |Z| \le\operatorname{ep}(k) ∣ Z ∣ ≤ ep ( k ) and G − Z G-Z G − Z has no cycle.
Additionally, ep ( k ) ∈ O ( k log k ) \operatorname{ep}(k) \in O(k\log k) ep ( k ) ∈ O ( k log k ) .
In what follows, we fix such a function ep ( ⋅ ) \operatorname{ep}(\cdot) ep ( ⋅ ) .
Proof of Theorem 38 . For every positive integer k k k , let
α ( k ) = ⌈ s ( 2 k − 1 ) 2 ⌉ + ( k − 1 ) \alpha(k) = \left\lceil\frac{s(2k-1)}{2}\right\rceil+ (k-1) α ( k ) = ⌈ 2 s ( 2 k − 1 ) ⌉ + ( k − 1 )
and let c c c be a constant such that for every integer k k k with k ≥ 2 k \ge2 k ≥ 2 ,
ep ( k ) + α ( k ) ≤ c ⋅ k log k . \operatorname{ep}(k) + \alpha(k) \le c \cdot k\log k. ep ( k ) + α ( k ) ≤ c ⋅ k log k .
Let G G G be a graph, let S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) , and let k k k be a positive integer. If k = 1 k=1 k = 1 , then either G G G contains an S S S -lollipop or not and the result holds. Now suppose k ≥ 2 k \ge2 k ≥ 2 . First, we apply the Erdős–Pósa theorem (Theorem 40 ) to G G G and k k k . This gives that either there are k k k pairwise disjoint cycles in G G G , or there exists Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) with ∣ Z ∣ ≤ ep ( k ) ≤ c ⋅ k log k |Z| \le\operatorname{ep}(k) \le c \cdot k\log k ∣ Z ∣ ≤ ep ( k ) ≤ c ⋅ k log k such that $G-Z is a forest. In the latter case, G − Z G-Z G − Z has no cycles, and so G − Z G-Z G − Z has no S S S -lollipops. Thus, we assume the former. Let C \mathcal{C} C be the maximum family of pairwise disjoint cycles in G G G . In particular, ∣ C ∣ ≥ k |\mathcal{C}| \ge k ∣ C ∣ ≥ k .
Let P \mathcal{P} P be a maximal family of pairwise vertex-disjoint V ( C ) V(\mathcal{C}) V ( C ) –S S S paths in G G G such that for each two paths in P \mathcal{P} P , the endpoints in V ( C ) V(\mathcal{C}) V ( C ) lie in distinct cycles of C \mathcal{C} C . Let C 1 \mathcal{C}_1 C 1 be the family of all cycles in C \mathcal{C} C containing endpoints of paths in P \mathcal{P} P . If ∣ C 1 ∣ ≥ k |\mathcal{C}_1| \ge k ∣ C 1 ∣ ≥ k , then clearly G [ V ( C 1 ∪ P ) ] G[V(\mathcal{C}_1 \cup\mathcal{P})] G [ V ( C 1 ∪ P )] contains k k k pairwise disjoint S S S -lollipops. Thus, we assume that ∣ C 1 ∣ < k |\mathcal{C}_1| < k ∣ C 1 ∣ < k . In particular, C ∖ C 1 ≠ ∅ \mathcal{C}\setminus\mathcal{C}_1 \ne\varnothing C ∖ C 1 = ∅ .
We apply Menger’s theorem between V ( C ∖ C 1 ) V(\mathcal{C}\setminus\mathcal{C}_1) V ( C ∖ C 1 ) and S S S . We get that either there are α ( k ) \alpha(k) α ( k ) pairwise disjoint V ( C ∖ C 1 ) V(\mathcal{C}\setminus\mathcal{C}_1) V ( C ∖ C 1 ) –S S S paths in G G G , or there exists a set Z ′ ⊆ V ( G ) Z' \subseteq V(G) Z ′ ⊆ V ( G ) with ∣ Z ′ ∣ < α ( k ) |Z'| < \alpha(k) ∣ Z ′ ∣ < α ( k ) such that G − Z ′ G-Z' G − Z ′ has no V ( C ∖ C 1 ) V(\mathcal{C}\setminus\mathcal{C}_1) V ( C ∖ C 1 ) –S S S paths. First, assume that the latter holds and let H H H be the subgraph of G G G defined as the union of all components of G − Z ′ G-Z' G − Z ′ containing a vertex in S S S . It follows that H H H has no vertices of V ( C ∖ C 1 ) V(\mathcal{C}\setminus\mathcal{C}_1) V ( C ∖ C 1 ) . In particular, H H H has no k k k pairwise disjoint cycles, as otherwise these cycles, along with the cycles in C ∖ C 1 \mathcal{C}\setminus\mathcal{C}_1 C ∖ C 1 form a family of pairwise disjoint cycles in G G G larger than C \mathcal{C} C , which contradicts C \mathcal{C} C being maximum. Therefore, by the Erdős–Pósa theorem, there exists Z ′ ′ ⊆ V ( H ) Z'' \subseteq V(H) Z ′′ ⊆ V ( H ) with ∣ Z ′ ′ ∣ ≤ ep ( k ) |Z''| \le\operatorname{ep}(k) ∣ Z ′′ ∣ ≤ ep ( k ) such that H − Z ′ ′ H-Z'' H − Z ′′ is a forest. In particular, for Z = Z ′ ∪ Z ′ ′ Z=Z'\cup Z'' Z = Z ′ ∪ Z ′′ , we have ∣ Z ∣ ≤ ep ( k ) + α ( k ) ≤ c k log k |Z| \le\operatorname{ep}(k)+\alpha(k) \le ck\log k ∣ Z ∣ ≤ ep ( k ) + α ( k ) ≤ c k log k and G − Z G-Z G − Z has no S S S -lollipops.
Therefore, we assume that there is a family Q \mathcal{Q} Q of at least α ( k ) \alpha(k) α ( k ) pairwise disjoint V ( C ∖ C 1 ) V(\mathcal{C}\setminus\mathcal{C}_1) V ( C ∖ C 1 ) –S S S paths in G G G . We will show that this contradicts the choice of C \mathcal{C} C . Let C 2 \mathcal{C}_2 C 2 be the family of all cycles in C ∖ C 1 \mathcal{C}\setminus\mathcal{C}_1 C ∖ C 1 containing endpoints of paths in Q \mathcal{Q} Q . Similarly as in the case of C 1 \mathcal{C}_1 C 1 , we may assume that ∣ C 2 ∣ < k |\mathcal{C}_2| < k ∣ C 2 ∣ < k .
Let Q ∈ Q Q \in\mathcal{Q} Q ∈ Q . If V ( Q ) ∩ V ( P ∪ C 1 ) = ∅ V(Q) \cap V(\mathcal{P}\cup\mathcal{C}_1)=\varnothing V ( Q ) ∩ V ( P ∪ C 1 ) = ∅ , then P ∪ { Q } \mathcal{P}\cup\{Q\} P ∪ { Q } is a larger family of V ( C ) V(\mathcal{C}) V ( C ) –S S S paths that are pairwise disjoint contradicting the definition of P \mathcal{P} P . Thus, V ( Q ) ∩ V ( P ∪ C 1 ) ≠ ∅ V(Q) \cap V(\mathcal{P}\cup\mathcal{C}_1)\ne\varnothing V ( Q ) ∩ V ( P ∪ C 1 ) = ∅ , and the next definition is justified. Let q Q q_Q q Q be the endpoint of Q Q Q in V ( C 2 ) V(\mathcal{C}_2) V ( C 2 ) , and let q Q ′ q'_Q q Q ′ be the first vertex in V ( C 1 ∪ P ) V(\mathcal{C}_1\cup\mathcal{P}) V ( C 1 ∪ P ) along Q Q Q starting from q Q q_Q q Q . Note that q Q q_Q q Q is distinct from q Q ′ q'_Q q Q ′ since V ( C 2 ) ∩ V ( C 1 ∪ P ) = ∅ V(\mathcal{C}_2)\cap V(\mathcal{C}_1\cup\mathcal{P})=\varnothing V ( C 2 ) ∩ V ( C 1 ∪ P ) = ∅ . Let R Q R_Q R Q be the q Q q_Q q Q –q Q ′ q'_Q q Q ′ subpath of Q Q Q . Next, we define a path R Q ′ R'_Q R Q ′ . If q Q ′ ∈ V ( C 1 ) q'_Q\in V(\mathcal{C}_1) q Q ′ ∈ V ( C 1 ) , then we set R Q ′ R'_Q R Q ′ to be the one-vertex path containing q Q ′ q'_Q q Q ′ . Otherwise, for P ∈ P P\in\mathcal{P} P ∈ P such that q Q ′ ∈ V ( P ) q'_Q\in V(P) q Q ′ ∈ V ( P ) , we set R Q ′ R'_Q R Q ′ to be the V ( C 1 ) V(\mathcal{C}_1) V ( C 1 ) –q Q ′ q'_Q q Q ′ subpath of P P P . Let Q ′ \mathcal{Q}' Q ′ be the set of all Q ∈ Q Q\in\mathcal{Q} Q ∈ Q such that q Q ′ ∉ V ( C 1 ) ∩ V ( P ) q'_Q\notin V(\mathcal{C}_1)\cap V(\mathcal{P}) q Q ′ ∈ / V ( C 1 ) ∩ V ( P ) .
Define
H = ⋃ ( C 1 ∪ C 2 ) ∪ ⋃ Q ∈ Q ′ ( R Q ∪ R Q ′ ) . H=\bigcup(\mathcal{C}_1\cup\mathcal{C}_2)\cup\bigcup_{Q\in\mathcal{Q}'}(R_Q\cup R'_Q). H = ⋃ ( C 1 ∪ C 2 ) ∪ Q ∈ Q ′ ⋃ ( R Q ∪ R Q ′ ) .
First, we claim that H H H has only vertices of degree 2 or 3. All vertices of ⋃ ( C 1 ∪ C 2 ) \bigcup(\mathcal{C}_1\cup\mathcal{C}_2) ⋃ ( C 1 ∪ C 2 ) are of degree at least 2 in H H H . By construction, for every Q ∈ Q ′ Q\in\mathcal{Q}' Q ∈ Q ′ , the endpoints of R Q R_Q R Q and R Q ′ R'_Q R Q ′ in G G G are in H H H , hence, all vertices of H H H have degree at least 2. On the other hand, recall that
the cycles in C 1 ∪ C 2 \mathcal{C}_1\cup\mathcal{C}_2 C 1 ∪ C 2 are pairwise disjoint;
the paths in P \mathcal{P} P are pairwise disjoint;
the paths in Q \mathcal{Q} Q are pairwise disjoint;
the paths in P \mathcal{P} P are disjoint from the cycles in C 2 \mathcal{C}_2 C 2 ; and
for Q ∈ Q ′ Q\in\mathcal{Q}' Q ∈ Q ′ , the vertex q Q ′ q'_Q q Q ′ intersects a path of P \mathcal{P} P or a cycle of C 1 \mathcal{C}_1 C 1 , but not both by the definition of Q ′ \mathcal{Q}' Q ′ .
Therefore we obtain that all vertices of H H H have degree at most 3.
Next, we claim that H H H has at least s ( 2 k − 1 ) s(2k-1) s ( 2 k − 1 ) vertices of degree 3. Note that since ∣ P ∣ < k |\mathcal{P}|<k ∣ P ∣ < k and the paths in Q \mathcal{Q} Q are pairwise disjoint, we have ∣ Q ∖ Q ′ ∣ < k |\mathcal{Q}\setminus\mathcal{Q}'|<k ∣ Q ∖ Q ′ ∣ < k . In particular, ∣ Q ′ ∣ ≥ ⌈ s ( 2 k − 1 ) / 2 ⌉ |\mathcal{Q}'|\ge\lceil s(2k-1)/2\rceil ∣ Q ′ ∣ ≥ ⌈ s ( 2 k − 1 ) /2 ⌉ , or in other words, 2 ∣ Q ′ ∣ ≥ s ( 2 k − 1 ) 2|\mathcal{Q}'|\ge s(2k-1) 2∣ Q ′ ∣ ≥ s ( 2 k − 1 ) .
Let Q C ′ = { Q ∈ Q ′ ∣ q Q ′ ∈ V ( C 1 ) } \mathcal{Q}'_{\mathcal{C}}=\{Q\in\mathcal{Q}'\mid q'_Q\in V(\mathcal{C}_1)\} Q C ′ = { Q ∈ Q ′ ∣ q Q ′ ∈ V ( C 1 )} and for each P ∈ P P\in\mathcal{P} P ∈ P , let Q P ′ = { Q ∈ Q ′ ∣ q Q ′ ∈ V ( P ) } \mathcal{Q}'_P=\{Q\in\mathcal{Q}'\mid q'_Q\in V(P)\} Q P ′ = { Q ∈ Q ′ ∣ q Q ′ ∈ V ( P )} . Clearly, { Q C ′ } ∪ { Q P ′ ∣ P ∈ P } \{\mathcal{Q}'_{\mathcal{C}}\}\cup\{\mathcal{Q}'_P\mid P\in\mathcal{P}\} { Q C ′ } ∪ { Q P ′ ∣ P ∈ P } is a partition of Q ′ \mathcal{Q}' Q ′ . Let P ′ = { P ∈ P ∣ Q P ′ ≠ ∅ } \mathcal{P}'=\{P\in\mathcal{P}\mid\mathcal{Q}'_P\ne\varnothing\} P ′ = { P ∈ P ∣ Q P ′ = ∅ } . For each P ∈ P ′ P \in\mathcal{P}' P ∈ P ′ , let p P p_P p P be the endpoint of P P P in V ( C 1 ) V(C_1) V ( C 1 ) and let Q P ∈ Q P ′ Q_P \in\mathcal{Q}'_P Q P ∈ Q P ′ be such that q Q P ′ q'_{Q_P} q Q P ′ is the furthest vertex in P P P starting from p P p_P p P among { q Q ′ ∣ Q ∈ Q P ′ } \{q'_{Q} \mid Q \in\mathcal{Q}'_P\} { q Q ′ ∣ Q ∈ Q P ′ } . It follows that the vertices in the following set have degree 3 in H H H :
{ q Q ∣ Q ∈ Q ′ } ∪ { q Q ′ ∣ Q ∈ Q C ′ } ∪ ⋃ P ∈ P ′ ( { p P } ∪ { q Q ′ ∣ Q ∈ Q P ′ ∖ { Q P } } ) . \{q_Q \mid Q \in\mathcal{Q}'\} \cup\{q'_Q \mid Q \in\mathcal{Q}'_C\} \cup\bigcup_{P \in\mathcal{P}'} \left(\{p_P\} \cup\{q'_Q \mid Q \in\mathcal{Q}'_P \setminus\{Q_P\}\}\right). { q Q ∣ Q ∈ Q ′ } ∪ { q Q ′ ∣ Q ∈ Q C ′ } ∪ P ∈ P ′ ⋃ ( { p P } ∪ { q Q ′ ∣ Q ∈ Q P ′ ∖ { Q P }} ) .
Additionally, the above set has size
∣ Q ′ ∣ + ∣ Q C ′ ∣ + ∑ P ∈ P ′ ( 1 + ( ∣ Q P ′ ∣ − 1 ) ) = 2 ∣ Q ′ ∣ ≥ s ( 2 k − 1 ) , |\mathcal{Q}'| + |\mathcal{Q}'_C| + \sum_{P \in\mathcal{P}'} (1 + (|\mathcal{Q}'_P| - 1)) = 2|\mathcal{Q}'| \ge s(2k-1), ∣ Q ′ ∣ + ∣ Q C ′ ∣ + P ∈ P ′ ∑ ( 1 + ( ∣ Q P ′ ∣ − 1 )) = 2∣ Q ′ ∣ ≥ s ( 2 k − 1 ) ,
since { Q C ′ } ∪ { Q P ′ ∣ P ∈ P } \{\mathcal{Q}'_C\} \cup\{\mathcal{Q}'_P \mid P \in\mathcal{P}\} { Q C ′ } ∪ { Q P ′ ∣ P ∈ P } is a partition of Q ′ \mathcal{Q}' Q ′ . It follows that indeed, H H H has at least s ( 2 k − 1 ) s(2k-1) s ( 2 k − 1 ) vertices of degree 3. By Theorem 39 , H H H contains a family C ′ \mathcal{C}' C ′ of 2 k − 1 2k-1 2 k − 1 pairwise disjoint cycles. Since the paths in P ∪ Q ′ \mathcal{P} \cup\mathcal{Q}' P ∪ Q ′ are disjoint from the cycles in C ∖ ( C 1 ∪ C 2 ) \mathcal{C} \setminus(C_1 \cup C_2) C ∖ ( C 1 ∪ C 2 ) and H ⊆ ( C 1 ∪ C 2 ∪ P ∪ Q ) H \subseteq(C_1 \cup C_2 \cup\mathcal{P} \cup\mathcal{Q}) H ⊆ ( C 1 ∪ C 2 ∪ P ∪ Q ) , the family D = ( C ∖ ( C 1 ∪ C 2 ) ) ∪ C ′ \mathcal{D} = (\mathcal{C} \setminus(C_1 \cup C_2)) \cup\mathcal{C}' D = ( C ∖ ( C 1 ∪ C 2 )) ∪ C ′ is a family of pairwise disjoint cycles in G G G . Moreover,
∣ D ∣ = ∣ C ∣ − ∣ C 1 ∣ − ∣ C 2 ∣ + ∣ C ′ ∣ ≥ ∣ C ∣ − 2 ( k − 1 ) + 2 k − 1 = ∣ C ∣ + 1. |\mathcal{D}| = |\mathcal{C}| - |C_1| - |C_2| + |\mathcal{C}'| \ge|\mathcal{C}| - 2(k-1) + 2k - 1 = |\mathcal{C}| + 1. ∣ D ∣ = ∣ C ∣ − ∣ C 1 ∣ − ∣ C 2 ∣ + ∣ C ′ ∣ ≥ ∣ C ∣ − 2 ( k − 1 ) + 2 k − 1 = ∣ C ∣ + 1.
This is a contradiction with the maximality of C \mathcal{C} C , which ends the proof. □
Open problems
To conclude, we would like to gather some indicative conjectures and open problems that we consider relevant to the study of annotated graphs.
We conjecture that for plane annotated graphs where the annotated set appears in the outer-face, the Erdős–Pósa function is O ( k log k ) O(k \log k) O ( k log k ) .
Conjecture 41 (Erdős–Pósa function of annotated minors). Let ( H , T ) (H,T) ( H , T ) be an annotated graph with H H H a plane graph and T T T contained in its outer-face. There exists a constant c ( H , T ) c(H,T) c ( H , T ) such that, for every annotated graph ( G , S ) (G,S) ( G , S ) , for every positive integer k k k , either
(i) ( G , S ) (G,S) ( G , S ) has k k k disjoint models of ( H , T ) (H,T) ( H , T ) , or
(ii) there exists Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) with ∣ Z ∣ ≤ c ( H , T ) ⋅ k log k |Z| \le c(H,T) \cdot k \log k ∣ Z ∣ ≤ c ( H , T ) ⋅ k log k such that ( G − Z , S ∖ Z ) (G-Z,S\setminus Z) ( G − Z , S ∖ Z ) has no model of ( H , T ) (H,T) ( H , T ) .
Similar to the standard (non-annotated) case, the bound in O ( k log k ) O(k \log k) O ( k log k ) would be tight for every ( H , T ) (H,T) ( H , T ) where H H H is not a forest (see e.g. [10 , 33 ] ). As mentioned earlier, a bound in O ( k ) O(k) O ( k ) in the case where H H H is a tree was recently obtained by Claus, Joret, Rambaud, and Robinson [5 ] . In Theorem 38 , we solve the case where H = K 3 H = K_3 H = K 3 and T T T is a single vertex of K 3 K_3 K 3 . Therefore, the first open case of Theorem 41 is H = K 3 H = K_3 H = K 3 with T T T consisting of two vertices of H H H .
Another intriguing line of research consists in finding the minimal annotated obstructions of some classes of annotated graphs. Probably the most natural example is the case of planar graphs:
Problem 42 (Annotated Kuratowski). Determine the smallest set O \mathcal{O} O of annotated graphs such that, for every annotated graph ( G , S ) (G,S) ( G , S ) , there exists S ′ ⊆ V ( G ) S' \subseteq V(G) S ′ ⊆ V ( G ) with S ⊆ S ′ S \subseteq S' S ⊆ S ′ and torso G ( S ′ ) \operatorname{torso}_G(S') torso G ( S ′ ) planar if and only if, for every ( H , T ) ∈ O (H,T) \in\mathcal{O} ( H , T ) ∈ O , ( H , T ) (H,T) ( H , T ) is not a minor of ( G , S ) (G,S) ( G , S ) .
Note that, by (the labeled variant of) the Robertson-Seymour Theorem, such a set O \mathcal{O} O exists and is finite. In Theorem 4, we solved the analogous problem for forests instead of planar graphs.
Also, it would be interesting to see whether, similar to the Steiner Tree problem [15 ] , more problems on terminal sets can be shown to be FPT parameterized not just by the size of the terminal set S S S but rather by tw ( G , S ) \operatorname{tw}(G,S) tw ( G , S ) or other torso parameters.
Acknowledgments
Some parts of this research were conducted at the Twelfth and Thirteenth Annual Workshop on Geometry and Graphs held at the Bellairs Research Institute in February 2025 and February 2026, respectively. Thanks to the organizers and the other workshop participants for creating a productive working atmosphere.