Abstract

We prove that there exist functions \(f:\mathbb{N}^2\to\mathbb{N}\) and \(g:\mathbb{N}\to\mathbb{N}\) such that for all positive integers \(k\), \(d\), and \(\ell\geqslant 3\), every graph \(G\) either contains \(k\) cycles of length at least \(\ell\) that are pairwise at distance greater than \(d\), or admits a subset of vertices \(X\) with \(|X|\leqslant f(k,\ell)\) such that \(G-B_G(X,g(d))\) contains no cycle of length at least \(\ell\), where \(B_G(X,r)\) denotes the ball of radius \(r\) around \(X\). This generalizes a theorem of Dujmović, Joret, Micek, and Morin (2024), which established the \(\ell=3\) case. Moreover, we prove that the theorem holds with \(f(k,\ell)\in\mathcal{O}(\ell k\log k)\) and \(g(d)\in\mathcal{O}(d)\). The linear bound on \(g\) is best possible, while the bound on \(f\) is optimal as a function of \(k\) for every fixed \(\ell\). In particular, for \(\ell=3\) our result improves the previous bound of \(\mathcal{O}(k^{18}\mathop{\mathrm{polylog}}k)\) by Dujmović et al.

1 Introduction↩︎

In 1965, Erdős and Pósa [1] proved that there exists a function \(f(k)\) such that for every positive integer \(k\) and every graph \(G\), either \(G\) contains \(k\) vertex-disjoint cycles, or there is a subset \(X\) of vertices of \(G\) with \(|X|\leqslant f(k)\) such that \(G-X\) has no cycles. This celebrated result has become one of the cornerstones of graph theory and has inspired a vast literature on the Erdős–Pósa property for a wide range of combinatorial objects.

Many extensions of the Erdős–Pósa theorem impose additional constraints on the cycles under consideration while retaining the same packing-versus-covering paradigm. Well-known constraints and generalizations include: long cycles [2]–[5], where each cycle has length at least \(\ell\); \(S\)-cycles [5]–[9], where the cycles must intersect a prescribed set \(S\); modularity constraints [8]–[17], where the lengths of cycles have remainder \(r\) modulo \(m\). Another key ingredient in Erdős–Pósa type theorems is the mode of packing, for example, minors [13], [18]–[25], edge-disjointness [26]–[30], half-integral packing [31]–[35].

1.1 Far-Apart Erdős–Pósa Property of Cycles↩︎

The following theorem of [36], which we call the “far-apart Erdős–Pósa property of cycles”, may be viewed as an extension of the Erdős–Pósa theorem where the cycles being "pairwise far apart" is the mode of packing. Here and throughout the paper, \(B_G(X,r)\) denotes the set of vertices at distance at most \(r\) from \(X\) in \(G\).

There exist functions \(f:\N \to \N\) and \(g:\N \to \N\), such that for all positive integers \(k\) and \(d\), and for every graph \(G\), either \(G\) contains \(k\) cycles that are pairwise at distance greater than \(d\) in \(G\), or there exists a subset \(X\) of vertices of \(G\) with \(|X|\leqslant f(k)\) such that \(G-B_G(X,g(d))\) has no cycles.

[thm:ErdosPosaCyclesFarApart] was conjectured in 2024 independently by Chudnovsky and Seymour⁸ and by [37]. Furthermore, [37] solved the cases \(k=2\) and arbitrary \(d\) as well as \(d=1\) and arbitrary \(k\). They also pointed out that balls are needed in [thm:ErdosPosaCyclesFarApart], even for the \(d=1\) case, since in complete graphs, no pair of cycles have distance more than \(1\), yet an unbounded number of vertices are needed to hit all cycles.

Long cycles, that is, cycles of length at least \(\ell\geqslant 3\), form one of the most well-studied instances of the Erdős–Pósa property, with a long line of work in the classical setting of vertex-disjoint packings. A 1988 result of [11] implies that for every \(\ell\), long cycles have the Erdős–Pósa property: every graph either contains \(k\) vertex-disjoint cycles of length at least \(\ell\), or a set of at most \(f(k,\ell)\) vertices meeting all of them. Thomassen’s argument gives \(f(k,\ell)\in 2^{\ell^{\mathcal{O}(k)}}\). The bound was improved to \(\mathcal{O}(\ell k^2)\) by [2], then to \(\mathcal{O}(\ell k\log k)\) by [3], and finally to the asymptotically optimal \(\Theta(\ell k+k\log k)\) by [4]. The following theorem, which is our main result, generalizes this line of work to the far-apart setting, and equally generalizes [thm:ErdosPosaCyclesFarApart] to long cycles, with optimal bounds for every fixed \(\ell\).

There exist functions \(f:\mathbb{N}^2\to\mathbb{N}\) and \(g:\mathbb{N}\to\mathbb{N}\), such that for all integers \(k\), \(d\), and \(\ell\) with \(k\geqslant 1\), \(d\geqslant 1\), and \(\ell\geqslant 3\), and for every graph \(G\), either \(G\) contains \(k\) cycles of length at least \(\ell\) that are pairwise at distance greater than \(d\) in \(G\), or there exists a subset \(X\) of vertices of \(G\) with \(|X|\leqslant f(k,\ell)\) such that \(G-B_G(X,g(d))\) has no cycles of length at least \(\ell\). Furthermore, this holds with \(f(k,\ell) \in \mathcal{O}( \ell k \log k)\) and \(g(d) \in \mathcal{O}(d)\).

We note that [38] recently proved this result for \(d=1\).

Let us now comment on the optimality of the bounds in [thm:main-in-intro]. First, \(f\) necessarily depends on both \(k\) and \(\ell\). This is witnessed by the ‘\(d=0\) case’ of the problem (which is not covered by [thm:main-in-intro]): there, balls are not needed, and the optimal size of a hitting set was determined to be \(\Theta(\ell k + k\log k)\) by [4]. Second, the bound \(g(d) \in \mathcal{O}(d)\) in [thm:main-in-intro] is best possible since \(g(d)\geqslant d\) is necessary in any such result.⁹ Third, for every fixed \(\ell\), the bound \(f(k,\ell)\in\mathcal{O}(\ell k\log k)\) is optimal as a function of \(k\) by standard lower bounds for the Erdős–Pósa theorem.

We now explain how [thm:main-in-intro] is obtained, namely how we generalize [thm:ErdosPosaCyclesFarApart] to cycles of length at least \(\ell\) while attaining optimal bounding functions for fixed \(\ell\). At a high level, our proof follows the same general framework as that of [36]. However, some key ingredients break down when moving beyond \(\ell=3\), and others stand in the way of optimal bounds.

The proof of [thm:ErdosPosaCyclesFarApart] in [36] exploits the case \(\ell=3\) in an essential way: hitting all cycles means leaving a forest behind. The argument in [36] is built around cycles whose surrounding balls induce unicyclic subgraphs, culminating in an application of the Helly property for subtrees of a tree (via the Gyárfás–Lehel theorem). For general \(\ell\), this structure is simply not available. Namely, a graph with no cycle of length at least \(\ell\) need not resemble a forest and may be locally dense. Our proof instead relies on two coarser ingredients. First, by a theorem of [39], graphs with no cycle of length at least \(\ell\) have treewidth less than \(\ell-1\). Thus the forests from [36] become graphs of bounded treewidth, and the Helly-type argument must be carried out not on these graphs themselves but on the trees underlying their tree-decompositions. Second, since unicyclic neighborhoods have no analogue for general \(\ell\), we introduce the notion of the span of a cycle \(C\), which measures how far apart along \(C\) the BFS-projections of the endpoints of nearby edges can be. Cycles of small span provide exactly the coarse control that unicyclic balls provided for \(\ell=3\): objects near \(C\) project onto short intervals of \(C\). A final difficulty is quantitative: a direct implementation of this strategy produces balls of radius \(\mathcal{O}(d\ell)\), and keeping the radius at \(\mathcal{O}(d)\), independent of \(\ell\), requires an additional padding argument that spreads a small hitting set on the cycles of the packing into a slightly larger but well-distributed one.

Regarding the bounding function \(f\), the proof in [36] yields \(f(k)\in\mathcal{O}(k^{18}\mathop{\mathrm{polylog}}k)\), largely because it invokes a theorem of [40] on the approximate Helly property of subgraphs of a tree with a bounded number of components. Replacing this ingredient with a theorem of [41] (see [thm:alon] in 2) already lowers the bound to \(\mathcal{O}(k^3\log k)\), but no further: the approach in [36] applies local arguments to every pair of cycles in a packing of up to \(k-1\) cycles, and therefore cannot produce a subquadratic bound. We instead analyze all cycles in the packing at once, and in a global manner. Altogether this yields [thm:main-in-intro] with \(f(k,\ell)\in\mathcal{O}(\ell k\log k)\) and \(g(d)\in\mathcal{O}(d)\) and, as a special case, the optimal bound \(f(k)\in\mathcal{O}(k\log k)\) in [thm:ErdosPosaCyclesFarApart], where optimality follows from standard lower bounds for the Erdős–Pósa theorem.

[thm:ErdosPosaCyclesFarApart] [thm:main-in-intro] are part of a larger body of work. The , as we call it, asks for either a large packing of objects that are pairwise far apart, or a small number of small-radius balls that hit all of the objects. Another example is the following “coarse Gallai theorem” of [42]: for every graph \(G\) and every set \(A\) of its vertices, either \(G\) contains \(k\) paths with endpoints in \(A\) that are pairwise at distance at least \(d\), or there is a set \(X\) of at most \(f(k)\) vertices such that every such path meets \(B_G(X,g(k,d))\). The radius of the balls depends on \(k\), in contrast with [thm:main-in-intro] where it is \(\mathcal{O}(d)\) only.

1.2 Coarse Motivations↩︎

From the point of view of graph minor theory, one can restate the Erdős–Pósa theorem as follows: There exists a function \(f(k)\) such that for every positive integer \(k\), and for every graph \(G\), either \(G\) contains \(k\) vertex-disjoint subgraphs each containing a \(K_3\) minor, or there exists a subset \(X\) of vertices of \(G\) with \(|X|\leqslant f(k)\) such that \(G-X\) has no \(K_3\) minor. Our far-apart Erdős–Pósa property (from 1.1) is inspired by a new line of research around the Erdős–Pósa theorem, where the usual notion of minors is replaced with that of “fat” minors.

This notion comes from a recently developed field of research called coarse graph theory that takes its roots in the pioneering work of [43], who studied graph minors from the point of view of coarse geometry. Quoting Georgakopoulos and Papasoglu, the general goal of coarse graph theory is

This novel viewpoint lead to a wealth of new and exciting questions and conjectures in graph theory that have attracted the attention of researchers in the last few years. This includes a coarse Menger conjecture (disproved recently by [44]), a coarse grid conjecture (disproved recently by [45]), and the following coarse Erdős–Pósa conjecture.¹⁰ (Necessary definitions are given below.)

There exists functions \(f:\N \to \N\) and \(g:\N \to \N\), with \(g(d)\in \mathcal{O}(d)\), such that, for all positive integers \(k\) and \(d\), and for every graph \(G\), either \(G\) contains \(k\) minor-models of \(K_3\) that are \(d\)-fat and pairwise at distance more than \(d\), or there exists a subset \(X\) of vertices of \(G\) with \(|X|\leqslant f(k)\) such that \(G-B_G(X,g(d))\) has no \(d\)-fat \(K_3\) minor-model.

To explain the notion of fat minor-models, it will be helpful to first consider the following way of defining the usual notion of minor-models: A of a graph \(H\) in a graph \(G\) is a collection of vertex-disjoint connected subgraphs \(\set{M_v:v\in V(H)}\) and a collection of internally-disjoint paths \(\set{P_e: e\in E(H)}\) such that for every edge \(e=uv\) of \(H\), the path \(P_e\) has one endpoint in \(M_u\) and the other endpoint in \(M_v\), and none of its internal vertices is in any subgraph \(M_w\) with \(w\in V(H)\). Now, given a positive integer \(d\), a minor-model of \(H\) in \(G\) is if it satisfies the following extra properties:

\(M_u\) and \(M_v\) are at distance at least \(d\) in \(G\) for every two distinct vertices \(u,v\in V(H)\);

\(P_e\) and \(P_f\) are at distance at least \(d\) in \(G\) for every two distinct edges \(e,f\in E(H)\), and

\(M_u\) and \(P_e\) are at distance at least \(d\) in \(G\) for every vertex \(u\in V(H)\) and edge \(e\in E(H)\) not incident to \(u\). Informally, every two objects from the definition of minor-model are required to be far apart in \(G\), except when they are required to intersect as per the original definition of minor. It might be helpful to think of fat minors as minors that would survive even if some disjoint balls of bounded radius were contracted into vertices. Alternatively, at a very intuitive level, the difference between minors and fat minors is that minors are essentially subgraphs that are allowed to be spread out, whereas fat minors are required to be spread out for the purpose of being “seen” even when looking at the graph from far away.

[thm:main-in-intro] and [conj:coarse-EP] are closely related but incomparable statements: neither implies the other. A first difference lies in how the parameters interact. In [conj:coarse-EP], a single parameter \(d\) governs everything: the fatness of the minor-models, the distances between them, and, as a consequence, the lengths of the cycles involved, since every \(d\)-fat minor-model of \(K_3\) contains a cycle of length at least \(6d\). In [thm:main-in-intro], by contrast, the length threshold \(\ell\) and the distance parameter \(d\) are independent of each other. A second difference lies in the nature of the objects being packed. A \(d\)-fat \(K_3\) minor-model is intrinsically spread out: many pairs of its vertices are required to be at distance at least \(d\) in \(G\). A cycle of length at least \(\ell\) carries no such requirement: any two of its vertices may be close, or even adjacent, in \(G\). For this reason, [conj:coarse-EP] does not imply [thm:main-in-intro], even in the regime \(\ell\leqslant 6d\): a hitting set for \(d\)-fat \(K_3\) minor-models need not come close to any long cycle. (For instance, large complete graphs contain no \(2\)-fat \(K_3\) minor-model but many long cycles.) Conversely, [thm:main-in-intro] does not imply [conj:coarse-EP], since a packing of pairwise far-apart long cycles need not yield even a single fat \(K_3\) minor-model.

This paper is organised as follows. In 2, we introduce the main tools we use in our proofs, and in 3, we prove [thm:main-in-intro].

2 Tools↩︎

Our proof makes use of three tools. The first is a key ingredient of Simonovits’s [46] proof of the Erdős–Pósa theorem, which was published in 1967 just two years after the original paper. The second is a beautiful statement generalizing the Helly property of a family of subtrees in a fixed host tree, which is due to [41] (improving on an earlier result of Gyárfás and Lehel [40]). The last is a theorem of [39] which says that graphs with no long cycles have bounded treewidth.

For all positive integers \(k\), define¹¹ \[\mathdefin{s(k)}\mathrel{\vcenter{:}}= \begin{cases} \lceil 4k(\log k + \log\log k +4)\rceil & \textrm{if k\geqslant 2,}\\ 2 & \textrm{if k=1.} \end{cases}\]

Let \(k\) be a positive integer and let \(G\) be a graph with all vertices of degree \(2\) or \(3\). If \(G\) contains at least \(s(k)\) vertices of degree \(3\), then \(G\) contains \(k\) pairwise vertex-disjoint cycles.

If a graph has at least one vertex, then it is .

For all positive integers \(k\) and \(c\), for every tree \(T\) and every collection \(\mathcal{A}\) of non-null subgraphs of \(T\) each having at most \(c\) components, either

\(\mathcal{A}\) has \(k\) pairwise vertex-disjoint members, or

there exists a subset \(X\subseteq V(T)\) with \(|X|\leqslant 2 c^2(k-1)\) such that \(X\cap V(A)\not=\varnothing\) for all \(A\in \mathcal{A}\).

For every integer \(\ell\geqslant 3\), every graph containing no cycle of length at least \(\ell\) has treewidth less than \(\ell-1\).

3 Proof of the Main Result↩︎

We denote by the set of nonnegative integers. For positive integers \(k\), we write as a compact form of \(\set{1,\dots,k}\). For sets \(S\), let be the set of all subsets of \(S\) that have size \(2\).

We consider simple, finite, and undirected graphs. Formally, a graph is pair \((V,E)\) consisting of a finite set of \(V\) with \(V\cap \binom{V}{2}=\varnothing\), and a set of \(E\subseteq \binom{V}{2}\).

Let \(G\) be a graph. We use the notations \(\mathdefin{V(G)}\) and \(\mathdefin{E(G)}\) to denote the vertex set of \(G\) and the edge set of \(G\), respectively. A graph \(H\) is a of \(G\), written as , if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\). A subgraph of \(G\) is if its vertex set equals \(V(G)\). For a set \(S\subseteq V(G)\), \(\mathdefin{G[S]}\) denotes the subgraph of \(G\) with vertex set \(S\) and edge set \(\binom{S}{2}\cap E(G)\), and \(\mathdefin{G-S}\mathrel{\vcenter{:}}= G[V(G)\setminus S]\). For a set \(Z\subseteq \binom{V(G)}{2}\), \(\mathdefin{G\cup Z}\) is the graph with vertex set \(V(G)\) and edge set \(E(G)\cup Z\); and \(\mathdefin{G-Z}\) is the graph with vertex set \(V(G)\) and edge set \(E(G)\setminus Z\). For two subsets \(A\) and \(B\) of \(V(G)\), we say that an edge \(uv\) of \(G\) with \(u\in A\) and \(v\in B\) is \(A\) and \(B\). For subgraphs \(H_1\) and \(H_2\) of \(G\), \(\mathdefin{H_1\cup H_2}\) is the graph with vertex set \(V(H_1)\cup V(H_2)\) and edge set \(E(H_1)\cup E(H_2)\). For a collection \(\mathcal{H}\) of subgraphs of \(G\), is the graph with vertex set \(\bigcup_{H\in \mathcal{H}} V(H)\) and edge set \(\bigcup_{H\in \mathcal{H}} E(H)\).

A is a graph with the vertex set \(\set{v_0,\ldots,v_k}\) and the edges \(\set{v_{i-1}v_{i} : i \in [k]}\), where \(k\geqslant 0\) and \(v_0,\dots,v_k\) are pairwise distinct. We often refer to a path by a natural sequence of its vertices, writing, say, \(v_0\cdots v_k\) or equivalently \(v_k \cdots v_0\). Writing a path as \(v_0\cdots v_k\) fixes an underlying orientation of the path, where \(v_0\) is the first vertex and \(v_k\) is the last vertex. We say that \(v_0\) and \(v_k\) are the of \(v_0 \cdots v_k\). We also say that \(v_0 \cdots v_k\) at \(v_0\) and at \(v_k\). Given a path \(P\) and two vertices \(v, w\) of \(P\), we denote by \(\mathdefin{vPw}\) the subpath of \(P\) from \(v\) to \(w\).

Suppose \(A\) and \(B\) are vertices or sets of vertices in a graph \(G\). A path \(P\) with \(P\subseteq G\) is an in \(G\) if \(P\) starts at (a vertex in) \(A\) and ends at (a vertex in) \(B\), and the inner vertices of \(P\) are disjoint from \(A\cup B\).

A is a graph with at least three vertices such that deleting any one edge results in a path. A in a graph \(G\) is a sequence \(v_0 v_1 \cdots v_k\) of vertices of \(G\), with \(k\geqslant 0\), such that \(v_{i-1}v_{i} \in E(G)\) for every \(i\in [k]\). Note that \(v_0,\dots,v_k\) are not necessarily distinct. Often we speak of a walk \(v_0 v_1 \cdots v_k\) as a graph, in such cases we are referring to the graph with vertex set \(\set{v_0, \dots, v_k}\) and edge set \(\set{v_{i-1}v_i:i\in [k]}\).

For walks, paths or edges \(P=v_0 v_1\cdots v_s\) and \(Q=v_s v_{s+1}\cdots v_t\), with \(0\leqslant s\leqslant t\), let \(\mathdefin{P\cup Q}\) be the walk (or path if it is one) whose underlying sequence of vertices is \(v_0 v_1\cdots v_t\).

A is a graph with no cycles. A is a connected forest.

A of a graph \(G\) is a function \(\beta\) from the vertex set of some tree \(T\) to the power set of \(V(G)\), such that for every vertex \(v\in V(G)\), the set \(\set{t\in V(T) : v\in \beta(t)}\) induces a non-null tree in \(T\); and for every edge \(uv\in E(G)\), there exists \(t\in V(T)\) with \(\set{u,v}\subseteq\beta(t)\). The of \(\beta\) is \(\max_{t\in V(T)}|\beta(t)|-1\). The of \(G\), denoted by , is the minimum width of a tree-decomposition of \(G\).

The length, \(\mathdefin{\mathop{\mathrm{len}}(P)}\), of a path \(P\) is the number of edges in \(P\). Similarly, the length of a cycle \(C\) is the number of edges in \(C\) and is denoted \(\mathdefin{\mathop{\mathrm{len}}(C)}\). The between two vertices \(x\) and \(y\) of \(G\), denoted by \(\mathdefin{\mathop{\mathrm{dist}}_G(x,y)}\), is minimum length of an \((x,y)\)-path in \(G\) if there is one, or if there is none. For non-empty subsets \(X\) and \(Y\) of \(V(G)\), define \(\mathdefin{\mathop{\mathrm{dist}}_G(X,Y)}\mathrel{\vcenter{:}}= \min\set{\mathop{\mathrm{dist}}_G(x,y):(x,y)\in X\times Y}\). For an integer \(r\geqslant 0\) and a vertex \(x\) of \(G\), the is \(\mathdefin{B_G(x,r)}\mathrel{\vcenter{:}}= \set{y\in V(G):\mathop{\mathrm{dist}}_G(x,y)\leqslant r}\). For subsets \(X\) of \(V(G)\), let \(\mathdefin{B_G(X,r)}\mathrel{\vcenter{:}}= \bigcup_{x\in X}B_G(x,r)\).

Let \(G\) be a graph and let \(d\) be a nonnegative integer. A collection \(\mathscr{C}\) of subgraphs of \(G\) is a if \(\mathop{\mathrm{dist}}_G(V(A),V(B))> d\) for every pair of distinct \(A,B\in\mathscr{C}\).

Let \(G\) be a graph and let \(H\) be a non-null subgraph of \(G\) that contains at least one vertex from each connected component of \(G\). An of \(G\) is an edge-minimal spanning subgraph \(U\) of \(G\) such that \(\mathop{\mathrm{dist}}_U(V(H), v)=\mathop{\mathrm{dist}}_G(V(H), v)\) for every vertex \(v\in V(G)\). Observe that \(U\) is a spanning forest in \(G\) and each component of \(U\) contains exactly one vertex of \(H\), which we call the of the component. For each \(v\in V(U)\) the of \(v\), denoted by , is the root of the component of \(U\) that contains \(v\); and is the unique path in \(U\) between \(v\) and \(\mathop{\mathrm{proj}}_U(v)\). The of an edge \(vw\) in \(G\) and the of \(G\) are defined as follows: \[\mathdefin{\mathop{\mathrm{span}}(G, H, U, vw)} \mathrel{\vcenter{:}}= \mathop{\mathrm{dist}}_{H}(\mathop{\mathrm{proj}}_U(v), \mathop{\mathrm{proj}}_U(w)),\] \[\mathdefin{\mathop{\mathrm{span}}(G, H, U)} \mathrel{\vcenter{:}}= \max(\set{\mathop{\mathrm{span}}(G, H, U, vw) : vw\in E(G)} \setminus \set{\infty}).\] The of \(G\) is the number \(\max_U \mathop{\mathrm{span}}(G,H,U)\), where the maximum is taken over all \(H\)-supported BFS-spanning subgraphs of \(G\).

Let \(d\geqslant 1\) and \(\ell\geqslant 3\) be integers. Let \(G\) be a graph and let \(C\) be a cycle in \(G\) of length at least \(\ell\). There exists a cycle \(C'\) in \(G\) of length at least \(\ell\) such that either

\(V(C') \subseteq B_G(V(C), 3d)\) and the length of \(C'\) is at most \(6d+2\), or

\(V(C')\subseteq B_G(V(C), 2d)\) and the \(C'\)-span of \(G[B_G(V(C'), d)]\) is at most \(\ell\).

Proof. We say that a pair \((Q,P)\) is if \(Q\) is a non-null path in \(C\), \(P\) is a path in \(G\) of length at most \(4d+1\), and \(Q\cup P\) is a cycle of length at least \(\ell\). Observe that, for any edge \(e\) of \(C\), \((C-e,e)\) is a good pair. Among all good pairs, let \((Q,P)\) be one that minimises \(\mathop{\mathrm{len}}(Q)\).

Let \(D=Q\cup P\) and let \(G_D\mathrel{\vcenter{:}}= G[B_G(V(D),d)]\). Since \(Q\subseteq C\) and \(\mathop{\mathrm{len}}(P)\leqslant 4d+1\), we have that \(V(D)\subseteq B_G(V(C),2d)\). Thus, if \(\mathop{\mathrm{span}}(G_D,D,U)\leqslant\ell\) for every \(D\)-supported BFS-spanning subgraph \(U\) of \(G_D\), then [item:small-span:medium-cycle-or-small-span] holds for \(C'=D\) and there is nothing to prove.

Therefore, we assume there is a \(D\)-supported BFS-spanning subgraph \(U\) of \(G_D\) and an edge \(vw\) of \(G_D\) with \(\infty > \mathop{\mathrm{span}}(G_D,D,U,vw)>\ell\). Let \(R\mathrel{\vcenter{:}}= U\relax{v}\cup vw\cup U\relax{w}\). Since \(\mathop{\mathrm{span}}(G_D, D, U, vw)>\ell\geqslant 3\), \(vw\not\in E(D)\) and \(V(U\relax{v})\cap V(U\relax{w})=\varnothing\), thus \(R\) is a path whose edges and inner vertices do not appear in \(D\). Also observe that \(\mathop{\mathrm{len}}(R) = \mathop{\mathrm{len}}(U\relax{v})+1+\mathop{\mathrm{len}}(U\relax{w})\leqslant 2d+1\). Now let \(x\) and \(y\) be the endpoints of \(R\). The argument splits into cases depending on the locations of \(x\) and \(y\) in \(D=Q\cup P\).

If \(x\in V(P)\) and \(y \in V(P)\), then consider the unique cycle \(C'\) in \(R\cup P\). Since \(\mathop{\mathrm{dist}}_{D}(x,y)>\ell\), we know that \(\mathop{\mathrm{len}}(C')\geqslant\ell\). On the other hand, \(\mathop{\mathrm{len}}(C') \leqslant\mathop{\mathrm{len}}(R)+\mathop{\mathrm{len}}(P) \leqslant 2d+1 + 4d+1 = 6d+2\). Finally \(V(R) \subseteq B_G(V(P),d)\) and \(V(P) \subseteq B_G(V(C),2d)\) which implies \(V(C') \subseteq B_G(V(C),3d)\). This proves that [item:medium:medium-cycle-or-small-span] holds.

Otherwise, we may assume \(x\in V(Q)\setminus V(P)\) without loss of generality. Then, the graph \(D\cup R\) has two cycles that contain \(R\). One of these cycles, \(D'\), contains at most \(\lfloor\tfrac{1}{2}\mathop{\mathrm{len}}(P)\rfloor\leqslant 2d\) edges of \(P\). Note also that \(\mathop{\mathrm{len}}(D')\geqslant\mathop{\mathrm{dist}}_{D}(x,y)>\ell\). Let \(Q'\mathrel{\vcenter{:}}= D'\cap Q\) and \(P'\mathrel{\vcenter{:}}= D'\cap (P\cup R)\). Note that \(x\) lies in \(Q'\) so \(Q'\) is non-null. Also, observe that \(x\) has two neighbors in \(Q\) (since \(x \notin V(P)\)) and \(D'\) contains only one of these two. Hence, \(\mathop{\mathrm{len}}(Q')<\mathop{\mathrm{len}}(Q)\). Finally, \(\mathop{\mathrm{len}}(P')= \mathop{\mathrm{len}}(P\cap D')+\mathop{\mathrm{len}}(R)\leqslant 2d+2d+1=4d+1\). Altogether, \((Q',P')\) is a good pair and \(\mathop{\mathrm{len}}(Q')<\mathop{\mathrm{len}}(Q)\), which contradicts the choice of \((Q,P)\).

This concludes the proof of the lemma. ◻

For every cycle \(C\), for every \(y\in V(C)\), and for every pair of positive integers \((\alpha,\beta)\), there exists a set \(Z \subseteq V(C)\) such that

\(y\in Z\);

\(|Z|\leqslant 2\beta+1\);

\(B_C(Z,\floor{\alpha/2})\) is connected and has size at least \(\min \set{\mathop{\mathrm{len}}(C),2(\alpha\beta+\floor{\alpha/2})+1}\);

For each vertex \(v\) in \(C\), if \(\mathop{\mathrm{dist}}_C(v,y)\leqslant\alpha\beta\) then \(\mathop{\mathrm{dist}}_C(v,Z)\leqslant\alpha/2\).

Proof. Fix an orientation of \(C\). Let \(v_0 v_1 \cdots v_{\alpha\beta}\) be the walk in \(C\) such that \(v_0=y\), and \(v_{i+1}\) is the successor of \(v_i\) in the clockwise cyclic ordering of \(C\) for all \(i\). Similarly, let \(u_0 u_1 \cdots u_{\alpha\beta}\) be the walk in \(C\) such that \(u_0=y\), and \(u_{i+1}\) is the successor of \(u_i\) in the anticlockwise cyclic ordering of \(C\) for all \(i\). Let \(Z\mathrel{\vcenter{:}}= \set{v_\alpha, v_{2\alpha}, \dots, v_{\alpha\beta}}\cup \set{y}\cup \set{u_\alpha, u_{2\alpha}, \dots, u_{\alpha\beta}}\). We show that \(Z\) satisfies the outcome of the lemma. Observe that [item:y-in-Z:pre-def-of-pad] and [item:size:pre-def-of-pad] are immediate. For any pair of consecutive vertices in the sequence \(v_{\beta\alpha}, v_{(\beta-1)\alpha}, \dots, v_{\alpha}, y, u_{\alpha}, u_{2\alpha}, \dots, u_{\beta\alpha}\), the union of their radius \(\lfloor \alpha/2 \rfloor\) balls is connected, thus \(B_C(Z,\floor{\alpha/2})\) is connected. If \(|B_C(Z,\floor{\alpha/2})|<\mathop{\mathrm{len}}(C)\), then \(v_{\alpha\beta+\floor{\alpha/2}} \cdots v_2 v_1 y u_1 u_2 \cdots u_{\alpha\beta+\floor{\alpha/2}}\) defines a path in \(C\), which implies \(|B_C(Z,\floor{\alpha/2})| \geqslant 2(\alpha\beta+\floor{\alpha/2})+1\). Hence [item:connected:pre-def-of-pad] holds. Finally, [item:padding-property:pre-def-of-pad] follows from the fact that every vertex in \(\set{v_1, v_2,\dots, v_{\alpha\beta}}\cup \set{y} \cup \set{u_1, u_2,\dots, u_{\alpha\beta}}\) has distance at most \(\alpha/2\) from some vertex in \(Z\). ◻

For cycles \(C\), vertices \(y\in V(C)\), and positive integers \(\alpha,\beta\), let \(\mathdefin{\mathop{\mathrm{pad}}(C,y,\alpha,\beta)}\) denote the corresponding set \(Z\) constructed in [lem:pre-def-of-pad].

Let \(H\) be a disjoint union of cycles \(C_1\cup \cdots \cup C_p\), let \(Y\subseteq V(H)\), and let \((\alpha,\beta)\) be a pair of positive integers. Define \[\mathdefin{\mathop{\mathrm{pad}}(H,Y,\alpha,\beta)} \mathrel{\vcenter{:}}= \bigcup_{i\in [p]}\;\; \bigcup_{y\in Y\cap V(C_i)} \mathop{\mathrm{pad}}(C_i,y,\alpha,\beta).\]

The outcomes of [lem:pre-def-of-pad] generalise to \(\mathop{\mathrm{pad}}(H,Y,\alpha,\beta)\) in the following way:

If \(H\) is a disjoint union of cycles, \(Y\subseteq V(H)\), and \((\alpha,\beta)\) is a pair of positive integers, then

\(Y\subseteq \mathop{\mathrm{pad}}(H,Y,\alpha,\beta)\subseteq V(H)\);

\(|\mathop{\mathrm{pad}}(H,Y,\alpha,\beta)|\leqslant|Y|(2\beta+1)\);

for each component \(C\) of \(H\), every component of \(C[V(C)\cap B_H(\mathop{\mathrm{pad}}(H,Y,\alpha,\beta),\lfloor\alpha/2\rfloor)]\) has at least \(\min \set{\mathop{\mathrm{len}}(C),2(\alpha\beta+\lfloor\alpha/2\rfloor)+1}\) vertices;

For each vertex \(v\) in \(H\), if \(\mathop{\mathrm{dist}}_H(v,Y)\leqslant\alpha\beta\) then \(\mathop{\mathrm{dist}}_H(v,\mathop{\mathrm{pad}}(H,Y,\alpha,\beta))\leqslant\alpha/2\).

Proof. [item:Y-in-pad:def-of-pad] and [item:size:def-of-pad] follow immediately from [lem:pre-def-of-pad]. Observe that for each component \(C\) of \(H\), \(V(C)\cap B_H(\mathop{\mathrm{pad}}(H,Y,\alpha,\beta), \lfloor\alpha/2\rfloor)=\bigcup_{y\in Y\cap V(C)}B_C(\mathop{\mathrm{pad}}(C, y, \alpha,\beta), \lfloor\alpha/2\rfloor)\), hence [item:connected:def-of-pad] holds by [lem:pre-def-of-pad]. To see that [item:padding-property:def-of-pad] holds, consider any \(v\in V(H)\) with \(\mathop{\mathrm{dist}}_H(v, Y)\leqslant\alpha\beta\). Let \(C\) be the component of \(H\) that contains \(v\), then there exists \(y\in Y\cap V(C)\) such that \(\mathop{\mathrm{dist}}_C(v,y)\leqslant\alpha\beta\). Then [lem:pre-def-of-pad] implies that \(\mathop{\mathrm{dist}}_C(v,\mathop{\mathrm{pad}}(C,y,\alpha,\beta))\leqslant\alpha/2\), therefore \(\mathop{\mathrm{dist}}_H(v,\mathop{\mathrm{pad}}(H,Y,\alpha,\beta))\leqslant\alpha/2\). ◻

Let \(k,d,r,R,\ell\) be positive integers with \(R\geqslant r > d\) and \(\ell\geqslant 3\). Let \(G\) be a graph, let \(\mathscr{C}\) be a non-empty \(2d\)-packing of cycles in \(G\) each of length at least \(\ell\), let \(U\) be a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_R\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}), R)]\), and let \(W\) be the set of endpoints of all edges \(e\in E(G_R)\) with \(\mathop{\mathrm{span}}(G_R,\bigcup\mathscr{C}, U, e)>\ell\). If the \(\bigcup\mathscr{C}\)-span of \(G_d\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}), d)]\) is at most \(\ell\), then either

\(G\) contains a \(d\)-packing of \(k\) cycles each of length at least \(\ell\), or

there exists \(X\subseteq V(\bigcup\mathscr{C})\) with \(|X|\leqslant(s(k)-1)(2\ceil{\ell/2}+1)\) such that \[W\cup \bigcup_{\set{C,D}\in \binom{\mathscr{C}}{2}} \left(B_G(V(C), r)\cap B_G(V(D), r) \right)\subseteq B_G(W, r-d-1) \subseteq B_G(X, R+r+d).\]

Proof. Let \(\mathdefin{\mathcal{E}}\mathrel{\vcenter{:}}= \set{e\in E(G_R) : \mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e)>\ell}\). (Thus, \(W\) is the set of endpoints of edges in \(\mathcal{E}\).) For each \(e=uv\in \mathcal{E}\), let \[\mathdefin{P_e}\mathrel{\vcenter{:}}= U\relax{u}\cup uv \cup U\relax{v}.\] Since \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, uv)>\ell\geqslant 3\), \(uv\not\in E(\bigcup\mathscr{C})\) and \(V(U\relax{u})\cap V(U\relax{v})=\varnothing\), thus \(P_e\) is a path whose edges and inner vertices do not appear in \(\bigcup\mathscr{C}\).

For each edge \(e=uv\in \mathcal{E}\), let \(\mathdefin{\mathop{\mathrm{proj}}_U(e)} \mathrel{\vcenter{:}}= \set{\mathop{\mathrm{proj}}_U(u), \mathop{\mathrm{proj}}_U(v)}\). Let be the auxiliary graph with vertex set \(\mathcal{E}\), where two distinct elements \(e,f\in V(H)\) are adjacent if and only if \[\mathop{\mathrm{dist}}_G(V(P_e), V(P_f)) \leqslant d \quad \text{or}\quad \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(e), \mathop{\mathrm{proj}}_U(f)) \leqslant d\ell.\] Let be a maximal independent set in \(H\) and consider the graph \[\textstyle\mathdefin{G'}\mathrel{\vcenter{:}}= \bigcup \mathscr{C} \cup \bigcup_{e\in I}P_e.\] Recall that \(\mathscr{C}\) is a collection of pairwise vertex-disjoint cycles. Also since \(\mathop{\mathrm{dist}}_G(V(P_e), V(P_f))>d\) for all distinct \(e,f\in I\), \((P_e : e\in I)\) is a collection pairwise vertex-disjoint paths. Furthermore, no edge or inner vertex of \(P_e\) appears in \(\bigcup\mathscr{C}\) for all \(e\in \mathcal{E}\). Therefore, every vertex \(v\in V(G')\) satisfies \(\deg_{G'}(v) \in \{2,3\}\), and the degree-\(3\) vertices of \(G'\) are precisely the endpoints of paths in \((P_e : e\in I)\). Hence \(G'\) has exactly \(2|I|\) degree-\(3\) vertices.

The argument splits into the following two cases: (1) \(2|I|\geqslant s(k)\), in which case it is shown that [item:packing:big-span-and-intersecting-balls] holds, and (2) \(2|I|\leqslant s(k)-1\), in which case it is shown that [item:alternative:big-span-and-intersecting-balls] holds.

Case (1) \(2|I|\geqslant s(k)\): A is a path \(S\) in \(\bigcup\mathscr{C}\) between an endpoint of \(P_e\) and an endpoint of \(P_f\) for some \(e,f\in I\), such that the inner vertices of \(S\) are degree-\(2\).

Every cycle in \(G'\) has length at least \(\ell\).

Proof of Claim. Every cycle in \(\mathscr{C}\) has length at least \(\ell\) and every cycle in \(G'\) that is not in \(\mathscr{C}\) contains a \(\mathscr{C}\)-segment. Thus, it suffices to show that every \(\mathscr{C}\)-segment has length greater than \(\ell\). Let \(S\) be a \(\mathscr{C}\)-segment whose endpoints \(x\) and \(y\) correspond with an endpoint \(x\) of \(P_e\) and an endpoint \(y\) of \(P_f\) for some \(e,f\in I\). If \(e=f\), then \(\mathop{\mathrm{len}}(S) \geqslant \mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e) > \ell\) since \(e\in \mathcal{E}\). If \(e\not=f\), then \(\mathop{\mathrm{len}}(S) \geqslant \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(x,y) \geqslant \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(e), \mathop{\mathrm{proj}}_U(f)) > d\ell \geqslant \ell\). ◻

For every pair of vertex-disjoint cycles \(D\) and \(D'\) in \(G'\), \(\mathop{\mathrm{dist}}_G(V(D), V(D')) > d\).

Proof of Claim. Assume for a contradiction that there exists a pair of vertex-disjoint cycles \(D\) and \(D'\) in \(G'\) such that \(\mathop{\mathrm{dist}}_G(V(D), V(D'))\leqslant d\). Consider any \(u\in V(D)\) and \(u'\in V(D')\) with \(\mathop{\mathrm{dist}}_G(u,u') \leqslant d\).

If \(u\in V(P_e)\) and \(u'\in V(P_f)\) for some \(e,f\in I\) with \(P_e\subseteq D\) and \(P_f\subseteq D'\), then since \(D\) and \(D'\) are vertex-disjoint, \(e\not=f\). Therefore \(\mathop{\mathrm{dist}}_G(u,u') \geqslant\mathop{\mathrm{dist}}_G(V(P_e), V(P_f)) > d\), a contradiction. Hence it may be assumed that \(u\not\in V(P_e)\) for every \(e\in I\) with \(P_e\subseteq D\). Consequently, there exists a unique \(C\in \mathscr{C}\) such that \(u\in V(C)\).

Let \(P\) be a shortest \((u,u')\)-path in \(G\). Since \(\mathop{\mathrm{dist}}_G(u,u')\leqslant d\), \(\mathop{\mathrm{len}}(P)\leqslant d\), so \(V(P)\subseteq B_G(V(C), d)\). In particular, since \(\mathscr{C}\) is a \(2d\)-packing in \(G\), \(u'\in B_G(V(C), d)\) and \(u'\not\in B_G(V(\bigcup\mathscr{C})\setminus V(C), d)\). Therefore \(\mathop{\mathrm{proj}}_U(u')\in V(C)\), \(V(U\relax{u'})\subseteq B_G(V(C), d)\), and \(\mathop{\mathrm{len}}(U\relax{u'})\leqslant d\). Furthermore, either \(u'\in V(C)\) or \(u'\) is an internal vertex of \(P_e\) for some \(e\in I\) with \(P_e\subseteq D'\). In the former case, \(\mathop{\mathrm{proj}}_U(u')=u'\in V(D')\), and in the latter case \(\mathop{\mathrm{proj}}_U(u')\in V(U\relax{u'})\subseteq V(P_e) \subseteq V(D')\). Hence \(\mathop{\mathrm{proj}}_U(u')\in V(D')\) in both cases.

Let \(v_0, v_1, \dots, v_s\) be the sequence of vertices along \(P\) such that \(v_0=u\), \(v_s=u'\), and \(s\leqslant d\). Since \(V(P)\subseteq B_G(V(C), d) \subseteq V(G_d)\), an assumption of the lemma implies that \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e) = \mathop{\mathrm{span}}(G_d, \bigcup\mathscr{C}, U[V(G_d)], e) \leqslant\ell\) for every \(e\in E(P)\). Therefore: \[\begin{align} \mathop{\mathrm{dist}}_C(u,\mathop{\mathrm{proj}}_U(u'))=\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(u,\mathop{\mathrm{proj}}_U(u')) &\leqslant\sum_{i=1}^{s}\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v_{i-1}), \mathop{\mathrm{proj}}_U(v_i))\notag\\ &= \sum_{i=1}^{s}\textstyle\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, v_{i-1}v_i)\leqslant s\ell \leqslant d\ell.}\label{eq:dist-between-u-and-proj95U40u3941} \end{align}\tag{1}\] Now consider a shortest \((u,\mathop{\mathrm{proj}}_U(u'))\)-path \(S\) in \(C\). Recall that \(u\in V(D)\) and \(\mathop{\mathrm{proj}}_U(u')\in V(D')\). Let \(x\) be the first vertex in \(S\) starting from \(u\) such that \(x\in V(P_e)\) for some \(e\in I\) with \(P_e\subseteq D\). Let \(y\) be the first vertex in \(S\) starting from \(\mathop{\mathrm{proj}}_U(u')\) such that \(y\in V(P_f)\) for some \(f\in I\) with \(P_f\subseteq D'\). Since \(D\) and \(D'\) are vertex-disjoint, both vertices \(x\) and \(y\) exist and \(e\not=f\). Note that \(\mathop{\mathrm{dist}}_C(x,y)\leqslant\mathop{\mathrm{dist}}_C(u, \mathop{\mathrm{proj}}_U(u')) \leqslant d\ell\) by 1 . On the other hand, \(x\in V(C)\cap V(P_e)\subseteq \mathop{\mathrm{proj}}_U(e)\), \(y\in V(C)\cap V(P_f) \subseteq \mathop{\mathrm{proj}}_U(f)\), and \(e\) and \(f\) are distinct elements of \(I\) together imply \(\mathop{\mathrm{dist}}_C(x,y)\geqslant\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(e), \mathop{\mathrm{proj}}_U(f)) > d\ell\), a contradiction. ◻

Since \(2|I|\geqslant s(k)\), \(G'\) has at least \(s(k)\) degree-\(3\) vertices. So [thm:simonovits] implies that \(G'\) contains \(k\) pairwise vertex-disjoint cycles. By [clm:cycles-in-G39-are-long], each of these cycles has length at least \(\ell\). By [clm:disjoint-cycles-in-G39-are-far-apart], these cycles form a \(d\)-packing in \(G\). Thus outcome [item:packing:big-span-and-intersecting-balls] holds.

Case (2) \(2|I|\leqslant s(k)-1\): Let \[\textstyle Y\mathrel{\vcenter{:}}= \bigcup_{e\in I}\mathop{\mathrm{proj}}_U(e) \quad \text{and}\quad X\mathrel{\vcenter{:}}= \mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y, 2d, \ceil{\ell/2}).\] Note that \(Y\subseteq V(\bigcup\mathscr{C})\) and \(|Y|= 2|I| \leqslant s(k)-1\). Then by [cor:def-of-pad], \(X\subseteq V(\bigcup\mathscr{C})\) and \(|X|\leqslant|Y|(2\ceil{\ell/2}+1)\leqslant(s(k)-1)(2\ceil{\ell/2}+1)\).

\(W\subseteq B_G(X, R+2d+1)\).

Proof of Claim. Consider any \(e\in \mathcal{E}\) and let \(v\) be an endpoint of \(e\). Note that \(e\in V(H)\). If \(e\in I\), then \(\mathop{\mathrm{proj}}_U(v)\in \mathop{\mathrm{proj}}_U(e) \subseteq Y\subseteq X\), so \(v\in B_G(X,R)\) as desired. Hence it may be assumed that \(e\in V(H)\setminus I\). Since \(I\) is a maximal independent set in \(H\), there exists \(f\in I\) such that \(ef\in E(H)\). Then there are two cases, (i) \(\mathop{\mathrm{dist}}_G(V(P_e), V(P_f))\leqslant d\), or (ii) \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(e), \mathop{\mathrm{proj}}_U(f))\leqslant d\ell\).

Case (i) \(\mathop{\mathrm{dist}}_G(V(P_e), V(P_f))\leqslant d\): Let \(u\in V(P_e)\) and \(u'\in V(P_f)\) such that \(\mathop{\mathrm{dist}}_G(u,u') = \mathop{\mathrm{dist}}_G(V(P_e), V(P_f))\), and let \(P\) be a shortest \((u,u')\)-path in \(G\). Let \(Q\) be the walk in \(G\) starting from \(\mathop{\mathrm{proj}}_U(u')\) and going to \(u'\) along \(P_f\), then following \(P\) to \(u\), and finally going to \(v\) along \(P_e\). Let \(s\) be the length of \(\mathop{\mathrm{proj}}_U(u')Qu'\). Since \(U\) is a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_R\), \(\mathop{\mathrm{dist}}_G(V(\bigcup\mathscr{C}), u') = s\). Then \(s\leqslant\mathop{\mathrm{dist}}_G(V(\bigcup\mathscr{C}), u)+\mathop{\mathrm{dist}}_G(u,u')\), which implies \(\mathop{\mathrm{dist}}_G(V(\bigcup\mathscr{C}), u) \geqslant s-d\). Since each endpoint of \(e\) is at distance at most \(R\) from \(V(\bigcup\mathscr{C})\) in \(G\), the length of \(u Q v\) is at most \(R+1-(s-d)\). (The \(+1\) accounts for the fact that \(uQv\) may contain the edge \(e\).) It follows that \(Q\) has length at most \(s+d+R+1-(s-d) =R+2d+1\). Recall that, since \(f\in I\), \(\mathop{\mathrm{proj}}_U(u')\in \mathop{\mathrm{proj}}_U(f)\subseteq Y\), thus \(v\in B_G(\mathop{\mathrm{proj}}_U(u'), R+2d+1) \subseteq B_G(Y, R+2d+1) \subseteq B_G(X, R+2d+1)\), as desired.

Case (ii) \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(e), \mathop{\mathrm{proj}}_U(f))\leqslant d\ell\): Since \(\mathop{\mathrm{proj}}_U(f) \subseteq Y\), \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(w,Y)\leqslant d\ell \leqslant 2d\ceil{\ell/2}\) for some \(w\in \mathop{\mathrm{proj}}_U(e)\). Then [cor:def-of-pad] implies that \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(w, X)\leqslant d\). Hence \(v\in B_G(w, R+1) \subseteq B_G(X,R+d+1)\), as desired. ◻

\(\bigcup_{\set{C,D}\in \binom{\mathscr{C}}{2}} \left(B_G(V(C), r)\cap B_G(V(D), r)\right) \subseteq B_G(W,r-d-1)\).

Proof of Claim. By an assumption of the lemma, \(r>d\). Let \(p\mathrel{\vcenter{:}}= |\mathscr{C}|\) and enumerate \(\mathscr{C}\) as \(C_1, C_2, \dots, C_p\). For each \(i\in [p]\), let \(U_i\mathrel{\vcenter{:}}= U[B_U(V(C_i), r)]\). Then \((V(U_i) : i\in [p])\) is a partition of \(B_G(\bigcup\mathscr{C}, r)\).

Consider each \(a\in \bigcup_{\set{C,D}\in \binom{\mathscr{C}}{2}} \left(B_G(V(C), r)\cap B_G(V(D), r)\right)\). Since \(a\in B_G(V(\bigcup\mathscr{C}), r)\), there exists a unique \(i\in [p]\) such that \(a\in V(U_i)\). Therefore \(a\in B_G(V(C_i), r)\cap B_G(V(\bigcup\mathscr{C})\setminus V(C_i), r)\) and \(a\not\in V(\bigcup\mathscr{C})\setminus V(C_i)\). Let \(Q\) be a shortest \((a, V(\bigcup\mathscr{C})\setminus V(C_i))\)-path in \(G\). Note that \(Q\) has an edge and \(V(Q) \subseteq B_G(\bigcup\mathscr{C}, r)\). Let \(u_a v_a\) be the first edge on \(Q\) such that \(u_a\in V(U_i)\) and \(v_a\not\in V(U_i)\). Thus \(v_a\in V(U_j)\) for some \(j\in [p]\setminus \set{i}\). Therefore \(u_av_a\) is an edge of \(G_R\) with \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, u_av_a)=\infty\), so \(\set{u_a,v_a}\subseteq W\). If \(u_av_a\) is one of the last \(d\) edges of \(Q\), then \(u_a\in B_G(V(\bigcup\mathscr{C}) \setminus V(C_i), d)\), implying \(u_a\not\in V(U_i)\), a contradiction. Hence \(\mathop{\mathrm{len}}(aQu_a)\leqslant\mathop{\mathrm{len}}(Q)-(d+1) \leqslant r-d-1\) and \(a\in B_G(u_a, r-d-1) \subseteq B_G(W, r-d-1)\), as desired. ◻

[clm:W-is-hit] and [clm:intersections-are-hit] together imply \[W\cup \bigcup_{\set{C,D}\in \binom{\mathscr{C}}{2}}\left(B_G(V(C), r)\cap B_G(V(D), r)\right) \subseteq B_G(W, r-d-1) \subseteq B_G(X, R+r+d),\] hence [item:alternative:big-span-and-intersecting-balls] holds.

This concludes the proof of the lemma. ◻

Let \(k,r,\ell\) be positive integers with \(\ell\geqslant 3\). Let \(G\) be a graph, let \(\mathscr{C}\) be a non-empty collection of pairwise vertex-disjoint cycles in \(G\), and let \(U\) be a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_r\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}), r)]\). If \(\mathcal{H}\) is a collection of non-null connected subgraphs of \(G_r\) such that \(\mathop{\mathrm{span}}(G_r, \bigcup\mathscr{C}, U, e) \leqslant\ell\) for every \(e\in E(\bigcup\mathcal{H})\), then either

\(\mathcal{H}\) contains \(k\) pairwise vertex-disjoint members, or

there exists \(Y\subseteq V(\bigcup\mathscr{C})\) with \(|Y|\leqslant k-1+|\mathscr{C}|\) such that \(B_U(B_{\bigcup\mathscr{C}}(Y,\lfloor \ell/2 \rfloor), r)\cap V(H)\not=\varnothing\) for all \(H\in \mathcal{H}\).

Proof. For each \(C\in \mathscr{C}\), arbitrarily choose a vertex \(\mathdefin{v_C}\in V(C)\) and let \(\mathdefin{P_C}\mathrel{\vcenter{:}}= C-B_C(v_C, \lfloor \ell/2\rfloor)\). Then \((P_C : C\in \mathscr{C})\) is a collection of pairwise vertex-disjoint paths (note that \(V(P_C)=\varnothing\) is possible). Let \(\mathdefin{F}\mathrel{\vcenter{:}}= \bigcup_{C\in \mathscr{C}}P_C\). For each \(H\in \mathcal{H}\), let \(\mathdefin{\mathop{\mathrm{proj}}_U(H)}\mathrel{\vcenter{:}}= \set{\mathop{\mathrm{proj}}_U(v):v\in V(H)}\).

Consider each \(H\in \mathcal{H}\). For each \(uv\in E(H)\), since \(\mathop{\mathrm{span}}(G_r, \bigcup\mathscr{C}, U, uv)\) is finite, there exists \(C\in \mathscr{C}\) such that \(\{\mathop{\mathrm{proj}}_U(u), \mathop{\mathrm{proj}}_U(v)\}\subseteq V(C)\). Moreover, since \(H\) is connected and \(\mathscr{C}\) is a collection of pairwise vertex-disjoint cycles, there exists a unique \(\mathdefin{C(H)}\in \mathscr{C}\) such that \(\mathop{\mathrm{proj}}_U(H) \subseteq V(C(H))\) (this is true even when \(E(H)=\varnothing\)). Let be the set of all \(H\in \mathcal{H}\) such that \(\mathop{\mathrm{proj}}_U(H)\subseteq V(P_{C(H)})\), and for each such \(H\), let be the minimal subpath of \(P_{C(H)}\) with \(\mathop{\mathrm{proj}}_U(H)\subseteq V(S_H)\).

Since \(F\) is a disjoint union of paths and \((S_H:H\in \mathcal{H}')\) is a collection of paths in \(F\), the Helly property for intervals implies that either (1) \((S_H:H\in \mathcal{H}')\) has \(k\) pairwise vertex-disjoint members, or (2) there exists \(Z\subseteq V(F)\) with \(|Z|\leqslant k-1\) such that \(Z\cap V(S_H)\not=\varnothing\) for all \(H\in \mathcal{H}'\).

Case (1) \((S_H:H\in \mathcal{H}')\) has \(k\) pairwise vertex-disjoint members: Then there exists \(\mathcal{P}\subseteq \mathcal{H}'\) with \(|\mathcal{P}|=k\) such that \(V(S_A)\cap V(S_B)=\varnothing\) for all distinct \(A,B\in \mathcal{P}\). Therefore \(\mathop{\mathrm{proj}}_U(A)\cap \mathop{\mathrm{proj}}_U(B)=\varnothing\) for all distinct \(A,B\in \mathcal{P}\), which implies that \(V(A)\cap V(B)=\varnothing\) for all distinct \(A,B\in \mathcal{P}\). Hence \(\mathcal{P}\) is a collection of \(k\) pairwise vertex-disjoint members of \(\mathcal{H}\), so [item:packing:cycle-helly-for-small-span-collection] holds.

Case (2) there exists \(Z\subseteq V(F)\) with \(|Z|\leqslant k-1\) such that \(Z\cap V(S_H)\not=\varnothing\) for all \(H\in \mathcal{H}'\): Let \(Y\mathrel{\vcenter{:}}= Z\cup \{v_C:C\in \mathscr{C}\}\), then \(Y\subseteq V(\bigcup\mathscr{C})\) and \(|Y|\leqslant k-1+|\mathscr{C}|\). We now show that \(B_{\bigcup\mathscr{C}}(Y,\lfloor \ell/2 \rfloor)\cap \mathop{\mathrm{proj}}_U(H)\not=\varnothing\) for all \(H\in \mathcal{H}\), which implies that \(B_U(B_{\bigcup\mathscr{C}}(Y,\lfloor \ell/2 \rfloor), r) \cap V(H)\not=\varnothing\) for all \(H\in \mathcal{H}\), then [item:alternative:cycle-helly-for-small-span-collection] holds. Consider any \(H\in \mathcal{H}\) and let \(C\mathrel{\vcenter{:}}= C(H)\). It may be assumed that \(B_C(v_C,\lfloor \ell/2 \rfloor)\cap \mathop{\mathrm{proj}}_U(H)=\varnothing\) and \(Z\cap \mathop{\mathrm{proj}}_U(H)=\varnothing\). Then \(\mathop{\mathrm{proj}}_U(H)\subseteq V(P_C)\) and \(H\in \mathcal{H}'\). Let \(z\in Z\cap V(S_H)\) as promised by the premise of the present case. The minimality of \(S_H\) implies its endpoints lie in \(\mathop{\mathrm{proj}}_U(H)\), thus \(z\) is an inner vertex of \(S_H\). Since \(H\) is connected, there exists a path \(q_0q_1\cdots q_s\) in \(H\) such that \(\mathop{\mathrm{proj}}_U(q_0)\) and \(\mathop{\mathrm{proj}}_U(q_s)\) are the two endpoints of \(S_H\). Let \(p_i\mathrel{\vcenter{:}}= \mathop{\mathrm{proj}}_U(q_i)\) for each \(i\in \{0, \dots, s\}\). Then \(z\in V(S_H)=V(p_0S_H p_s)\) and \(z\not=p_s\). Let \(t\) be minimum such that \(z\not\in V(p_tS_H p_s)\). Then \(t\in [s]\) and \(z\in V(p_{t-1}S_H p_s)\). It follows that \(p_tS_H p_s\) is a subpath of \(p_{t-1}S_H p_s\), and \(z\in V(p_{t-1}S_H p_t)\). Since \(z\not\in \mathop{\mathrm{proj}}_U(H)\), \(p_{t-1}, z, p_t\) are distinct vertices in \(P_C\). Therefore \(C[B_C(v_C, \floor{\ell/2}+1)]\) is a path of length \(2(\floor{\ell/2}+1)\), implying that the \((p_{t-1}, p_t)\)-path in \(C\) that does not contain \(z\) has length at least \(2(\floor{\ell/2}+1) > \ell\). However by an assumption of the lemma \(\mathop{\mathrm{dist}}_C(p_{t-1}, p_t) \leqslant\ell\), therefore \(\mathop{\mathrm{len}}(p_{t-1}S_H p_t) \leqslant\ell\). Consequently \(B_C(z,\lfloor \ell/2 \rfloor) \cap \{p_{t-1}, p_t\} \not=\varnothing\), hence \(B_{\bigcup\mathscr{C}}(Y,\lfloor \ell/2 \rfloor)\cap \mathop{\mathrm{proj}}_U(H)\not=\varnothing\), as desired.

This concludes the proof of the lemma. ◻

Let \(k,d,r,\ell\) be positive integers with \(r\geqslant\ceil{d/2}\) and \(\ell\geqslant 3\). Let \(R\mathrel{\vcenter{:}}= r+\ceil{d/2}\), let \(G\) be a graph, let \(\mathscr{C}\) be a non-empty \(d\)-packing of cycles in \(G\) each of length at least \(\ell\), let \(U\) be a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_R\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}), R)]\), and let \(W\) be the set of endpoints of all edges \(e\in E(G_R)\) such that \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e) > \ell\). Then either

\(G\) contains a \(d\)-packing of \(k\) cycles each of length at least \(\ell\), or

there exists \(Y\subseteq V(\bigcup\mathscr{C})\) with \(|Y|\leqslant 2(k-1)\) such that, by letting \(G_r\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}), r)]\) and \(X\mathrel{\vcenter{:}}= \mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y, 2\ceil{d/2}+1, \ceil{\ell/2})\), we have that \[G_r-\big(B_G(W, \lfloor d/2\rfloor)\cup B_{\bigcup\mathscr{C}\cup U}(X,R)\big)\] has no cycles of length at least \(\ell\).

Proof. If \(|\mathscr{C}| \geqslant k\), then [item:packing:hitting-long-cycles-close-to-packing] holds, hence it may be assumed that \(|\mathscr{C}|\leqslant k-1\). Let be the set of all cycles in \(G_r - B_G(W, \lfloor d/2 \rfloor)\) of length at least \(\ell\). For each \(D\in \mathcal{D}\), let be a \(D\)-supported BFS-spanning subgraph of \(G[B_G(V(D), \lceil d/2 \rceil)]\), and let \(\mathdefin{H_D}\mathrel{\vcenter{:}}= D\cup U_D\).

\(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e)\leqslant\ell\) for every \(D\in \mathcal{D}\) and every \(e\in E(H_D)\).

Proof of Claim. Consider any \(D\in \mathcal{D}\) and any edge \(e\in E(H_D)\). Without loss of generality, \(e=uv\) where \(u\in B_G(V(D), \ceil{d/2}-1)\). Since \(\ceil{d/2}-1 \leqslant\floor{d/2}\) and \(B_G(V(D), \floor{d/2}) \cap W = \varnothing\), \(u\not\in W\). This along with \(uv\in E(G_R)\) implies that \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, uv) \leqslant\ell\), as desired. ◻

Now \(\mathdefin{\mathcal{H}} \mathrel{\vcenter{:}}= \set{H_D : D\in \mathcal{D}}\) is a collection of non-null connected subgraphs of \(G_R\) that, by [clm:edges-of-H95D-have-big-span], satisfies \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e)\leqslant\ell\) for every \(e\in E(\bigcup\mathcal{H})\). Hence we may proceed by cases depending on the outcome of [lem:cycle-helly-for-small-span-collection].

Case [item:packing:cycle-helly-for-small-span-collection] \(\mathcal{H}\) contains \(k\) pairwise vertex-disjoint members: Then there exists \(\mathcal{P}\subseteq \mathcal{D}\) with \(|\mathcal{P}|=k\) such that \(V(H_A)\cap V(H_B)=\varnothing\) for all distinct \(A,B\in \mathcal{P}\). Recall that \(V(H_D)=V(U_D)=B_G(V(D), \ceil{d/2})\) for all \(D\in \mathcal{D}\), thus \(\mathcal{P}\) is a \((2\ceil{d/2})\)-packing of \(k\) cycles in \(G\) each of length at least \(\ell\), so [item:packing:hitting-long-cycles-close-to-packing] holds.

Case [item:alternative:cycle-helly-for-small-span-collection] there exists \(Y\subseteq V(\bigcup\mathscr{C})\) with \(|Y|\leqslant k-1+|\mathscr{C}|\) such that for \(Z\mathrel{\vcenter{:}}= B_{\bigcup\mathscr{C}}(Y,\floor{\ell/2})\), \(B_U(Z, R)\cap V(H)\not=\varnothing\) for all \(H\in \mathcal{H}\): Since \(|\mathscr{C}|\leqslant k-1\), \(|Y|\leqslant 2(k-1)\). Let \(X\mathrel{\vcenter{:}}= \mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y, 2\ceil{d/2}+1, \ceil{\ell/2})\). The following shows that \(B_G(W, \lfloor d/2\rfloor)\cup B_{\bigcup\mathscr{C}\cup U}(X,R)\) meets every cycle in \(G_r\) of length at least \(\ell\), which implies that [item:alternative:hitting-long-cycles-close-to-packing] holds. Consider any cycle \(D\) in \(G_r\) of length at least \(\ell\). It may be assumed that \(D\) has no vertex in \(B_G(W, \lfloor d/2\rfloor)\). Then \(D\in \mathcal{D}\). Let \(u\in B_U(Z, R)\cap V(H_D)\) as promised by the premise of the present case. Since \(Z\subseteq V(\bigcup\mathscr{C})\), there exists \(z\in Z\) such that \(z=\mathop{\mathrm{proj}}_U(u)\). Since \(u\in V(H_D)\), there exists \(v\in V(D)\) and a path \(q_0q_1\cdots q_s\) in \(H_D\) such that \(q_0=v\), \(q_s=u\), and \(s\leqslant\ceil{d/2}\). Then by [clm:edges-of-H95D-have-big-span], \[\begin{align} \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), z) &\leqslant\sum_{i=1}^s \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(q_{i-1}), \mathop{\mathrm{proj}}_U(q_i))\\ &= \sum_{i=1}^s \textstyle\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, q_{i-1}q_i) \leqslant s\ell \leqslant\lceil d/2 \rceil \ell. \end{align}\] Furthermore, since \(z\in Z=B_{\bigcup\mathscr{C}}(Y, \floor{\ell/2})\), \[\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), Y) \leqslant\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), z) + \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(z, Y) \leqslant\lceil d/2 \rceil \ell + \floor{\ell/2}\leqslant(2\ceil{d/2}+1)\ceil{\ell/2}.\] Since \(X=\mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y, 2\ceil{d/2}+1, \ceil{\ell/2})\), [cor:def-of-pad] implies \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), X)\leqslant\ceil{d/2}\). Finally, since \(v\in V(D) \subseteq V(G_r)\), \(v\in B_U(\mathop{\mathrm{proj}}_U(v), r)\), thus \(v\in B_{\bigcup\mathscr{C}\cup U}(X,r+\ceil{d/2})\). Consequently, \(D\) has a vertex in \(B_{\bigcup\mathscr{C}\cup U}(X,R)\) and [item:alternative:hitting-long-cycles-close-to-packing] holds.

This concludes the proof of the lemma. ◻

We now prove a quantitative version of [thm:main-in-intro].

Let \(f:\N^2\to\N\) and \(g:\N\to\N\) be the following functions: \[f(k,\ell) = (51s(k)+104k-155)(2\ceil{\ell/2}+1)+k-1, \qquad g(d) = 21d.\] For all positive integers \(k,d,\ell\) with \(\ell\geqslant 3\), for every graph \(G\), either \(G\) has a \(d\)-packing of \(k\) cycles each of length at least \(\ell\), or there exists \(X\subseteq V(G)\) with \(|X|\leqslant f(k, \ell)\) and \(G-B_G(X, g(d))\) has no cycle of length at least \(\ell\).

Proof. If \(G\) has a \(d\)-packing of \(k\) cycles each of length at least \(\ell\), then there is nothing to prove. Therefore we assume that \(G\) does not have a \(d\)-packing of \(k\) cycles each of length at least \(\ell\).

Let be a maximal \(d\)-packing of cycles in \(G\) such that \(\ell \leqslant\mathop{\mathrm{len}}(D)\leqslant 6d+2\) for all \(D\in \mathcal{Z}\). Let be a maximal \(2d\)-packing of cycles in \(G\) such that \(\mathop{\mathrm{len}}(C)\geqslant\ell\) and the \(C\)-span of \(G[B_G(V(C), d)]\) is at most \(\ell\) for all \(C\in \mathscr{C}\).

Note that \(\mathcal{Z}\) and \(\mathscr{C}\) have size at most \(k-1\), and each may be the empty set.

Every cycle in \(G\) of length at least \(\ell\) contains a vertex in \(B_G(\bigcup \mathscr{C}, 4d)\cup B_G(\bigcup\mathcal{Z}, 4d)\).

Proof of Claim. Assume for a contradiction that there exists a cycle \(C\) in \(G\) such that \(C\) has length at least \(\ell\) and contains no vertex in \(B_G(\bigcup \mathscr{C}, 4d)\cup B_G(\bigcup\mathcal{Z}, 4d)\). Proceed by cases depending on the outcomes of [lem:medium-cycle-or-small-span].

Case [item:medium:medium-cycle-or-small-span] there exists a cycle \(C'\) in \(G\) of length at least \(\ell\) such that \(V(C')\subseteq B_G(V(C), 3d)\) and the length of \(C'\) is at most \(6d+2\): Then \(V(C') \cap B_G(\bigcup\mathcal{Z}, d)=\varnothing\), therefore \(\mathcal{Z}\cup \set{C'}\) contradicts the maximality of \(\mathcal{Z}\).

Case [item:small-span:medium-cycle-or-small-span] there exists a cycle \(C'\) in \(G\) of length at least \(\ell\) such that \(V(C')\subseteq B_G(V(C), 2d)\) and the \(C'\)-span of \(G[B_G(V(C'), d)]\) is at most \(\ell\): Then \(V(C')\cap B_G(\bigcup\mathscr{C}, 2d)=\varnothing\), therefore \(\mathscr{C}\cup \set{C'}\) contradicts the maximality of \(\mathscr{C}\). ◻

Let \(\mathdefin{Z} \mathrel{\vcenter{:}}= \textstyle B_G(\bigcup\mathcal{Z}, 4d)\) and let be a set consisting of one vertex from each cycle in \(\mathcal{Z}\). Then \[\label{eq:size-of-X950} |X_0|\leqslant k-1.\tag{2}\] Furthermore, since each cycle in \(\mathcal{Z}\) has length at most \(6d+2\), \[\label{eq:Z-in-X950-ball} Z \subseteq B_G(X_0, 7d+1).\tag{3}\]

If \(\mathscr{C}=\varnothing\), then 2 and 3 along with [clm:long-cycles-are-close-to-packing] imply that the theorem holds. Hence from this point on we assume that \(\mathscr{C}\not=\varnothing\) and thus, \(\bigcup\mathscr{C}\)-span is now well-defined for graphs that contain \(\bigcup\mathscr{C}\) as a subgraph.

Let \[\textstyle \mathdefin{G_d}\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}), d)].\]

The \(\bigcup\mathscr{C}\)-span of \(G_d\) is at most \(\ell\).

Proof of Claim. Suppose \(U\) is a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_d\) and \(e\in E(G_d)\). First consider the case that both endpoints of \(e\) lie in \(B_G(V(C), d)\) for some \(C\in \mathscr{C}\). Let \(G_C\mathrel{\vcenter{:}}= G[B_G(V(C), d)]\). Since \(\mathscr{C}\) is a \(2d\)-packing in \(G\), \(S\mathrel{\vcenter{:}}= U[V(G_C)]\) is a \(C\)-supported BFS-spanning subgraph of \(G_C\) such that \(\mathop{\mathrm{span}}(G_C, C, S, e) = \mathop{\mathrm{span}}(G_d, \bigcup\mathscr{C}, U, e)\). Furthermore since \(\mathop{\mathrm{span}}(G_C, C, S, e)\) is finite and the \(C\)-span of \(G_C\) is at most \(\ell\) (by definition of \(C\in \mathscr{C}\)), \(\mathop{\mathrm{span}}(G_C, C, S, e) \leqslant\ell\). Thus \(\mathop{\mathrm{span}}(G_d, \bigcup\mathscr{C}, U, e) \leqslant\ell\). On the other hand, if \(e\) is an edge between \(B_G(V(C), d)\) and \(B_G(V(D), d)\) for distinct \(C,D\in\mathscr{C}\), then \(\mathop{\mathrm{span}}(G_d, \bigcup\mathscr{C}, U, e) = \infty\). It follows that the \((\bigcup \mathscr{C}, U)\)-span of \(G_d\) is at most \(\ell\). Moreover, since \(U\) was an arbitrary \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_d\), the \(\bigcup\mathscr{C}\)-span of \(G_d\) is at most \(\ell\), as desired. ◻

Let \[\mathdefin{r}\mathrel{\vcenter{:}}= 6d,\] \[\textstyle \mathdefin{G_r}\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}),r)],\] \[\mathdefin{R}\mathrel{\vcenter{:}}= r+\ceil{d/2},\] \[\textstyle \mathdefin{G_R}\mathrel{\vcenter{:}}= G[B_G(V(\bigcup\mathscr{C}), R)].\] Let be a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_R\).

Let be the set of all endpoints of edges \(e\in E(G_R)\) such that \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e)>\ell\). Since \(\mathscr{C}\) is a \(2d\)-packing in \(G_R\), every edge \(e\in E(G[B_G(V(C), d)])\) has finite \((\bigcup\mathscr{C}, U)\)-span for all \(C\in \mathscr{C}\). Thus [clm:G95d-has-small-span] implies that every edge \(e\in E(G[B_G(V(C), d)])\) satisfies \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e) \leqslant\ell\).

Therefore for all \(C\in \mathscr{C}\), \[\label{eq:d-1-balls-are-clean-of-W} \textstyle W\cap B_G(V(C), d-1) = \varnothing.\tag{4}\]

Let \[\mathdefin{I}\mathrel{\vcenter{:}}= \bigcup_{\set{C,D}\in \binom{\mathscr{C}}{2}}B_G(V(C), r)\cap B_G(V(D), r).\]

By [clm:G95d-has-small-span] the \(\bigcup\mathscr{C}\)-span of \(G_d\) is at most \(\ell\). Since \(R\geqslant r >d\), [lem:big-span-and-intersecting-balls] implies that there exists \(\mathdefin{X_1} \subseteq V(\bigcup\mathscr{C})\) such that \[\label{eq:size-of-X951} |X_1|\leqslant(s(k)-1)(2\ceil{\ell/2}+1),\tag{5}\] and \[\label{eq:W-and-intersections-in-X951-ball} W\cup I\subseteq B_G(W, r-d-1) \subseteq B_G(X_1, R+r+d).\tag{6}\]

Since \(\mathscr{C}\) is a \(2d\)-packing, it is a \(d\)-packing. Therefore since \(r\geqslant\ceil{d/2}\), [lem:hitting-long-cycles-close-to-packing] implies that there exists \(\mathdefin{Y_2}\subseteq V(\bigcup\mathscr{C})\) with \(|Y_2|\leqslant 2(k-1)\) such that, by letting \[\textstyle\mathdefin{X_2}\mathrel{\vcenter{:}}= \mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y_2, 2\ceil{d/2}+1, \ceil{\ell/2}),\] and \[\mathdefin{L}\mathrel{\vcenter{:}}= B_G(W, \lfloor d/2 \rfloor) \cup B_{\bigcup\mathscr{C}\cup U}(X_2,R),\] we have that \[\label{eq:L-hits-long-cycles-in-G95r} \textstyle \text{G_r-L has no cycles of length at least \ell.}\tag{7}\] Then by [cor:def-of-pad], \[\label{eq:size-of-X952} |X_2|\leqslant|Y_2|(2\ceil{\ell/2}+1)\leqslant 2(k-1)(2\ceil{\ell/2}+1).\tag{8}\]

Let \[\mathdefin{F_{-1}} \mathrel{\vcenter{:}}= \textstyle \bigcup\mathscr{C}-L,\] \[\mathdefin{F_0} \mathrel{\vcenter{:}}= \textstyle G-\big(Z\cup B_G( V(\bigcup \mathscr{C}), r-2d)\big),\] \[\mathdefin{F_0^-}\mathrel{\vcenter{:}}= \textstyle G-\big(Z\cup B_G(V(\bigcup \mathscr{C}), r-d)\big).\] Then \(F_0^-\) is an induced subgraph of \(F_0\). Moreover by [clm:long-cycles-are-close-to-packing], \[\label{eq:no-long-cycles-in-F950} \text{F_0 and F_0^- contain no cycle of length at least \ell.}\tag{9}\]

Let \(\mathdefin{p}\mathrel{\vcenter{:}}= |\mathscr{C}|\) and enumerate \(\mathscr{C}\) as . For each \(i\in [p]\) let \[\mathdefin{F_i}\mathrel{\vcenter{:}}= G[B_G(V(C_i), r)]-L,\] \[\mathdefin{F_i^-}\mathrel{\vcenter{:}}= G[B_G(V(C_i), r-d)]-L.\] Then \(F_i^-\) is an induced subgraph of \(F_i\). Moreover, 7 guarantees that for all \(i\in [p]\),

\[\label{eq:no-long-cycles-in-F95i} \text{F_i contains no cycle of length at least \ell.}\tag{10}\]

Let \[\label{eq:def-of-M} \mathdefin{M} \mathrel{\vcenter{:}}= B_G(X_0\cup X_1\cup X_2, R+r+d),\tag{11}\] then by 3 and 6 , \[\begin{align} Z\cup L\cup I &\subseteq B_G(X_0, 7d+1)\cup B_G(W, \lfloor d/2 \rfloor) \cup B_{\bigcup\mathscr{C}\cup U}(X_2,R)\cup B_G(X_1, R+r+d)\notag\\ &\subseteq B_G(X_0, 7d+1)\cup B_G(W, r-d-1) \cup B_G(X_2,R)\cup B_G(X_1, R+r+d)\notag\\ &= B_G(X_0, 7d+1) \cup B_G(X_2,R)\cup B_G(X_1, R+r+d)\notag\\ &\subseteq M.\label{eq:M-contains-Z-and-L-and-I} \end{align}\tag{12}\]

For each \(i\in [p]\), define \(\mathdefin{U_i} \mathrel{\vcenter{:}}= U[B_U(V(C_i), r-d)]\). Then \(\bigcup_{i\in [p]}U_i\) is a forest and the sets \(V(U_1), V(U_2), \dots, V(U_p)\) form a partition of \(B_G(V(\bigcup\mathscr{C}), r-d)\). See 1 for a summary of the many key definitions given so far.

Figure 1: Simplified drawing showing the interplay between many of the key definitions so far.

For each pair \(i,j\in [p]\), a path \(P\mathrel{\vcenter{:}}= v_0 v_1\cdots v_s\) in \(G\) with \(s\geqslant 2\) is an if

\(v_0\in V(U_i)\) and \(v_s\in V(U_j)\);

\(v_1\cdots v_{s-1}\) is a path in \(F_0^-\). An is an \((i,j)\)-ear for some \(i,j\in [p]\). The of \(P\) is the path \(P_1\mathrel{\vcenter{:}}= U\relax{v_0}\), and the of \(P\) is the path \(P_2\mathrel{\vcenter{:}}= U\relax{v_s}\). Therefore \(P_1\) is the unique path in \(U_i\) between \(v_0\) and \(\mathop{\mathrm{proj}}_U(v_0)\), and \(P_2\) is the unique path in \(U_j\) between \(v_s\) and \(\mathop{\mathrm{proj}}_U(v_s)\). Note that \(V(P_1)\cap V(P_2)\) may be non-empty for \((i,j)\)-ears where \(i=j\). Let \[\mathdefin{\mathop{\mathrm{proj}}_U(P)}\mathrel{\vcenter{:}}= \set{\mathop{\mathrm{proj}}_U(v_0), \mathop{\mathrm{proj}}_U(v_s)}.\] Then \(\mathop{\mathrm{proj}}_U(P)\) is a non-empty subset of \(V(\bigcup\mathscr{C})\). 2 shows typical examples of ears and their projections. Define the walk \[\mathdefin{W_P} \mathrel{\vcenter{:}}= P_1\cup P \cup P_2.\] Note that the first and second legs of \(P\) have exactly \(r-d\) edges, whereas \(P\) may be arbitrarily long. \(P\) is said to be if \(V(W_P)\cap B_G(M, d) = \varnothing\).

Figure 2: E is an (i,i)-ear with \mathop{\mathrm{proj}}_U(E) = \set{x}, Q is a (j,j)-ear with \mathop{\mathrm{proj}}_U(Q) = \set{v,w}, and P is an (i,j)-ear with \mathop{\mathrm{proj}}_U(P) = \set{x,y}. — Figure 2: \(E\) is an \((i,i)\)-ear with \(\mathop{\mathrm{proj}}_U(E) = \set{x}\), \(Q\) is a \((j,j)\)-ear with \(\mathop{\mathrm{proj}}_U(Q) = \set{v,w}\), and \(P\) is an \((i,j)\)-ear with \(\mathop{\mathrm{proj}}_U(P) = \set{x,y}\).

Suppose \(P\mathrel{\vcenter{:}}= v_0 v_1\cdots v_s\) is an admissible \((i,j)\)-ear and let \(P_0 \mathrel{\vcenter{:}}= v_1 \cdots v_{s-1}\). For each \(m\in \set{-1,0,1,\dots, p}\), let \[\mathdefin{\Psi_m(P)} \mathrel{\vcenter{:}}= \begin{cases} \varnothing& \text{if m\not\in \set{-1,0,i,j},}\\ B_{\bigcup\mathscr{C}-L}(\mathop{\mathrm{proj}}_U(P), d\ell) & \text{if m=-1,}\\ B_G(V(P_0), d) & \text{if m=0,}\\ B_G(V(W_P)\cap V(U_m), d) & \text{if m\in \set{i,j}.} \end{cases}\]

If \(P\) is an admissible ear, then

\(G[\Psi_{-1}(P)]\) is a subgraph of \(F_{-1}\) and has at most two components;

\(G[\Psi_0(P)]\) is a connected subgraph of \(F_0\);

for all \(m\in [p]\), \(G[\Psi_m(P)]\) is a subgraph of \(F_m\) and has \(c_m\) components where \(c_m\in \set{0,1,2}\). Moreover, \(\sum_{m\in [p]}c_m \leqslant 2\).

Proof of Claim. Write \(P=v_0v_1\cdots v_s\) and let \(i,j\in [p]\) such that \(P\) is an \((i,j)\)-ear. Let \(P_1\) and \(P_2\) be the first and second legs of \(P\) respectively, and let \(P_0 \mathrel{\vcenter{:}}= v_1\cdots v_{s-1}\). Let \(u_0\mathrel{\vcenter{:}}= \mathop{\mathrm{proj}}_U(v_0)\) and \(u_s\mathrel{\vcenter{:}}= \mathop{\mathrm{proj}}_U(v_s)\). Recall that \(Z\cup L\subseteq M\) by 12 .

To prove [item-1:components-of-Psi], it suffices to show that \(B_{C_i-L}(u_0, d\ell)\) is a connected set of vertices in \(C_i-L\), and \(B_{C_j-L}(u_s, d\ell)\) is a connected set of vertices in \(C_j-L\). However this is trivial since each is a ball centred at some vertex.

Next, we prove [item:0:components-of-Psi]. Since \(P\) is admissible, \(B_G(V(W_P), d) \cap M=\varnothing\). Thus \(P_0\subseteq W_P\) and \(Z\subseteq M\) together imply \(B_G(V(P_0), d) \cap Z=\varnothing\). Furthermore since \(P_0\subseteq F_0^-\), \(V(P_0) \cap B_G(V(\bigcup\mathscr{C}), r-d)=\varnothing\). Hence \(B_G(V(P_0), d)\) and \(Z\cup B_G(V(\bigcup\mathscr{C}), r-2d)\) are disjoint. Therefore, since \(P_0\) is connected, \(G[B_G(V(P_0), d)]\) is a connected subgraph of \(G-(Z\cup B_G(V(\bigcup\mathscr{C}), r-2d))\). In other words, \(G[\Psi_0(P)]\) is a connected subgraph of \(F_0\).

It remains to prove [item:positive:components-of-Psi]. Let \(m\in [p]\). Note that \(m\not=0\). If \(m\not\in \set{i,j}\), then \(\Psi_m(P) = \varnothing\), implying that \(G[\Psi_m(P)]\subseteq F_m\) and \(c_m=0\). Therefore it suffices to show that \(B_G(V(P_1), d)\) is a connected set of vertices in \(F_i\), and \(B_G(V(P_2), d)\) is a connected set of vertices in \(F_j\). We only prove the first statement as the second is symmetric. Since \(P\) is admissible and \(L\subseteq M\), \(B_G(V(W_P), d)\cap L=\varnothing\), thus \(B_G(V(P_1), d)\cap L=\varnothing\). Furthermore, since \(V(P_1)\subseteq V(U_i) \subseteq B_G(V(C_i), r-d)\), \(B_G(V(P_1), d)\subseteq B_G(V(C_i), r)\setminus L\). Therefore, since \(P_1\) is connected, \(B_G(V(P_1), d)\) is a connected set of vertices in \(G[B_G(V(C_i), r)]-L\). In other words, \(B_G(V(P_1), d)\) is a connected set of vertices in \(F_i\) as desired. ◻

If \(P\) and \(Q\) are admissible ears such that \(\Psi_{-1}(P) \cap \Psi_{-1}(Q)=\varnothing\), then \[\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(P), \mathop{\mathrm{proj}}_U(Q)) > d\ell.\]

Proof of Claim. Let \(P=v_0v_1\cdots v_s\) and let \(i,j\in [p]\) such that \(P\) is an \((i,j)\)-ear. Let \(P_1\) and \(P_2\) be the first and second legs of \(P\) respectively, and let \(P_0 \mathrel{\vcenter{:}}= v_1\cdots v_{s-1}\). Similarly, write \(Q=w_0w_1\cdots w_h\) and let \(i',j'\in [p]\) such that \(Q\) is an \((i',j')\)-ear. Let \(Q_1\) and \(Q_2\) be the first and second legs of \(Q\) respectively, and let \(Q_0 \mathrel{\vcenter{:}}= w_1\cdots w_{h-1}\).

Proceed by contraposition and suppose that \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(P), \mathop{\mathrm{proj}}_U(Q)) \leqslant d\ell\). Let \(S\) be a shortest path in \(\bigcup\mathscr{C}\) between \(\mathop{\mathrm{proj}}_U(P)\) and \(\mathop{\mathrm{proj}}_U(Q)\), and let \(C\in \mathscr{C}\) such that \(S\subseteq C\). The following shows that \(S\subseteq C-L\), which implies that \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}-L}(\mathop{\mathrm{proj}}_U(P), \mathop{\mathrm{proj}}_U(Q))\leqslant d\ell\), hence \(\Psi_{-1}(P)\cap \Psi_{-1}(Q)\not=\varnothing\) as required. As a first step, we show that the components of \(C[V(C)\cap L]\) each have at least \(\gamma\mathrel{\vcenter{:}}= \min\set{\mathop{\mathrm{len}}(C), d\ell+2}\) vertices. Recall that \(X_2=\mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y_2, \alpha, \beta)\) (where \(\alpha=2\ceil{d/2}+1\) and \(\beta=\ceil{\ell/2}\)). Since \(X_2\subseteq V(\bigcup\mathscr{C})\) and the components of \(\bigcup\mathscr{C}\cup U\) are the graphs \(C_1\cup U[B_U(V(C_1), R)],\dots, C_p\cup U[B_U(V(C_p), R)]\), for all \(t \geqslant 0\) we have \[\label{eq:C-intersect-L} V(C)\cap B_{\bigcup\mathscr{C}\cup U}(X_2, t) = V(C)\cap B_{\bigcup\mathscr{C}}(X_2, t) = B_C(V(C)\cap X_2, t).\tag{13}\] By [cor:def-of-pad] and \(2(\alpha\beta+\lfloor\alpha/2\rfloor)+1\geqslant(d+1)(\ell+1) > d\ell+2\), the components of \(C[V(C)\cap B_{\bigcup\mathscr{C}}(X_2, \floor{\alpha/2})]\) each have at least \(\min\set{\mathop{\mathrm{len}}(C),d\ell+2} = \gamma\) vertices. Then 13 implies the components of \(C[B_C(V(C)\cap X_2, \floor{\alpha/2})]\) each have at least \(\gamma\) vertices. Since \(R\geqslant\floor{\alpha/2}\), the components of \(C[B_C(V(C)\cap X_2, R)]\) each have at least \(\gamma\) vertices, hence the components of \(C[V(C)\cap B_{\bigcup\mathscr{C}\cup U}(X_2, R)]\) each have at least \(\gamma\) vertices by 13 . Now recall that \(L=B_G(W, \floor{d/2})\cup B_{\bigcup\mathscr{C}\cup U}(X_2, R)\). Since \(\floor{d/2}\leqslant d-1\), 4 implies \(B_G(W, \floor{d/2})\cap V(C)=\varnothing\), thus \(V(C)\cap L = V(C)\cap B_{\bigcup\mathscr{C}\cup U}(X_2, R)\). It follows that the components of \(C[V(C)\cap L]\) each have at least \(\gamma\) vertices, as required. Next, since \(P\) and \(Q\) are admissible and \(L\subseteq M\) by 12 , the set of endpoints of \(S\) is disjoint from \(L\). Assume for a contradiction that \(V(S)\cap L\not=\varnothing\). Then there exists a component of \(C[V(C)\cap L]\) that is a subgraph of \(S\), implying \(\mathop{\mathrm{len}}(S)=|V(S)|-1 \geqslant\min\set{\mathop{\mathrm{len}}(C)-1, d\ell+1}\). However, by definition of \(S\), \(\mathop{\mathrm{len}}(S) \leqslant\min\set{\mathop{\mathrm{len}}(C)/2, d\ell} < \min\set{\mathop{\mathrm{len}}(C)-1,d\ell+1}\), a contradiction. Hence \(V(S)\cap L=\varnothing\), implying \(S\subseteq C-L\) as desired. ◻

If \(P\) and \(Q\) are admissible ears such that \(\Psi_m(P) \cap \Psi_m(Q)=\varnothing\) for all \(m\in \set{0,1, \dots, p}\), then \[\mathop{\mathrm{dist}}_G(V(W_P), V(W_Q)) > d.\]

Proof of Claim. Write \(P=v_0v_1\cdots v_s\) and let \(i,j\in [p]\) such that \(P\) is an \((i,j)\)-ear. Let \(P_1\) and \(P_2\) be the first and second legs of \(P\) respectively, and let \(P_0 \mathrel{\vcenter{:}}= v_1\cdots v_{s-1}\). Similarly, write \(Q=w_0w_1\cdots w_h\) and let \(i',j'\in [p]\) such that \(Q\) is an \((i',j')\)-ear. Let \(Q_1\) and \(Q_2\) be the first and second legs of \(Q\) respectively, and let \(Q_0 \mathrel{\vcenter{:}}= w_1\cdots w_{h-1}\).

Proceed by contraposition and suppose that \(\mathop{\mathrm{dist}}_G(V(W_P), V(W_Q)) \leqslant d\). Let \(v\in V(W_P)\) and \(w\in V(W_Q)\) such that \(\mathop{\mathrm{dist}}_G(v,w) \leqslant d\). Then either (1) \(v\in V(P_0)\) or \(w\in V(Q_0)\), or (2) \(v\not\in V(P_0)\) and \(w\not\in V(Q_0)\).

Case (1) \(v\in V(P_0)\) or \(w\in V(Q_0)\): Without loss of generality assume the latter. Then it is immediate that \(v\in B_G(w, d) \subseteq \Psi_0(Q)\), so it suffices to show that \(v\in \Psi_0(P)\). If \(v\in V(P_0)\), then \(v\in \Psi_0(P)\). Otherwise \(v\) lies in the first or second leg of \(P\). Without loss of generality \(v\in V(P_1)\). Let \(S\mathrel{\vcenter{:}}= v P_1 v_0\). Recall that \(w\in V(Q_0) \subseteq V(F_0^-)\). Also, recall that \(P_1\) is a shortest path in \(G\) between \(V(\bigcup\mathscr{C})\) and \(v_0\), and \(\mathop{\mathrm{len}}(P_1)=r-d\), thus \(B_G(v,\mathop{\mathrm{len}}(S)) \subseteq B_G(V(\bigcup\mathscr{C}), r-d)\). Hence \(B_G(v, \mathop{\mathrm{len}}(S))\) is disjoint from \(V(F_0^-)\). Therefore since \(w\in B_G(v, d)\cap V(F_0^-)\), \(\mathop{\mathrm{len}}(S)\leqslant d-1\). Then \(S\cup v_0v_1\) is a path between \(v\) and \(V(P_0)\) of length at most \(d\), which implies that \(v\in B_G(V(P_0), d) = \Psi_0(P)\), as desired.

Case (2) \(v\not\in V(P_0)\) and \(w\not\in V(Q_0)\): Without loss of generality assume that \(v\in V(P_1)\) and \(w\in V(Q_1)\). It is immediate that \(w\in B_G(v, d) \subseteq \Psi_i(P)\), so it suffices to show that \(w\in \Psi_i(Q)\). By [clm:components-of-Psi] \(\Psi_i(P) \subseteq V(F_i)\), thus \(w\in B_G(V(C_i), r)\). This along with \(w\in V(Q_1) \subseteq V(U_{i'}) \subseteq B_G(V(C_{i'}), r)\) shows that \(w\in B_G(V(C_i), r)\cap B_G(V(C_{i'}), r)\). Now since \(Q\) is admissible and \(w\in V(W_Q)\), \(w\not\in M\). In particular \(w\not\in I\) by 12 . Consequently, \(i=i'\). Hence \(w \in B_G(V(Q_1), d) \subseteq \Psi_{i'}(Q) = \Psi_{i}(Q)\), as desired. ◻

If \(P\) is an admissible ear and there exists sets \(S\subseteq V(\bigcup\mathscr{C})\) and \(S'\subseteq V(G)\) such that \(S\cap \Psi_{-1}(P)\not=\varnothing\) or \(S'\cap \bigcup_{m=0}^p\Psi_m(P)\not=\varnothing\), then \(B_G(\mathop{\mathrm{pad}}(\bigcup\mathscr{C}, S, 2d, \ceil{\ell/2}) \cup S',r) \cap V(P)\not=\varnothing\).

Proof of Claim. First suppose that \(S\cap \Psi_{-1}(P)\not=\varnothing\). Then \(S\cap B_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(P), d\ell)\not=\varnothing\). In other words, there exists \(u\in \mathop{\mathrm{proj}}_U(P)\) such that \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(u, S) \leqslant d\ell \leqslant 2d \ceil{\ell/2}\). Then [cor:def-of-pad] implies \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(u, \mathop{\mathrm{pad}}(\bigcup\mathscr{C}, S, 2d, \ceil{\ell/2}))\leqslant d\). Moreover, since \(B_G(u, r-d)\cap V(P)\not=\varnothing\), \(B_G(\mathop{\mathrm{pad}}(\bigcup\mathscr{C}, S, 2d, \ceil{\ell/2}), r) \cap V(P)\not=\varnothing\) as required.

Next, suppose that \(S'\cap \bigcup_{m=0}^p\Psi_m(P)\not=\varnothing\). Since \(\bigcup_{m=0}^p\Psi_m(P)\subseteq B_G(V(W_P), d)\), \(S\cap B_G(V(W_P), d) \not=\varnothing\). Then since \(V(W_P)\subseteq B_G(V(P), r-d)\), \(S'\cap B_G(V(P), r)\not=\varnothing\), hence \(B_G(S', r)\cap V(P)\not=\varnothing\) as required. ◻

Let be pairwise vertex-disjoint graphs such that \(F_i^\star\) is isomorphic to \(F_i\) for all \(i\in \set{-1,0,\dots, p}\). Note that unlike \((F_{-1}^\star, F_0^\star, \dots, F_p^\star)\), the graphs in \((F_{-1}, F_0, \dots, F_p)\) may intersect each other. For each \(i\in\set{-1, 0,\dots, p}\) let be an isomorphism from \(F_i\) to \(F_i^\star\). Let \(\mathdefin{F^\star} = F_{-1}^\star\cup \bigcup_{i=0}^{p}F_i^\star\).

Let and be minimum-width tree-decompositions of \(F_{-1}^\star\) and \(\bigcup_{i=0}^{p}F_i^\star\) respectively. Let and be the underlying trees of \(\beta_{-1}\) and \(\beta_{\geqslant 0}\) respectively, which we may assume to be vertex-disjoint. Let be a tree that contains \(T_{-1} \cup T_{\geqslant 0}\) as a spanning subgraph. Then \(\mathdefin{\beta}\mathrel{\vcenter{:}}= \beta_{-1} \cup \beta_{\geqslant 0}\) is a tree-decomposition of \(F^\star\). Now \(\bigcup\mathscr{C}-L\) is a forest by 7 , thus \(\beta_{-1}\) has width at most \(1\). Furthermore, [thm:birmele], 9 , and 10 together imply that \(\beta_{\geqslant 0}\) has width less than \(\ell-1\). Therefore for all \(t\in V(T)\), \[\label{eq:size-of-bags} |\beta(t)| \leqslant\begin{cases} 2 & \text{if t\in V(T_{-1}),}\\ \ell-1 & \text{if t\in V(T_{\geqslant 0}).} \end{cases}\tag{14}\]

For subsets \(S\subseteq V(F^\star)\), let \(\mathdefin{T(S)}\mathrel{\vcenter{:}}= T[\set{t\in V(T) : \beta(t)\cap S\not=\varnothing}]\).

An ear \(P\) is , for some \(i\in [p]\), if it is an \((i,i)\)-ear and there exists a cycle in \(W_P\cup C_i\) of length less than \(\ell\). An ear is if it is \(i\)-problematic for some \(i\in [p]\). An ear is if it is not problematic. For non-problematic admissible ears \(P\), let \(\mathdefin{\Psi^\star(P)}\mathrel{\vcenter{:}}= \bigcup_{m=-1}^{p}\pi_m(\Psi_m(P))\). Let be the set of all graphs \(T(\Psi^\star(P))\) where \(P\) is a non-problematic admissible ear. By [clm:components-of-Psi], \(F^\star[\Psi^\star(P)]\) has at most five components for every non-problematic admissible ear \(P\). Therefore \(\mathcal{A}\) is a collection of subgraphs of \(T\) each with at most five components.

Let \(\mathdefin{k^\star}\) be the minimum integer such that \(2k^\star \geqslant s(k)+2(k-1)\). Proceed by cases depending on the outcome of [thm:alon] when applied to \(T\), \(\mathcal{A}\), and \(k^\star\).

Case [item:packing:alon] \(\mathcal{A}\) has \(k^\star\) pairwise vertex-disjoint members: Then there exists a collection of \(k^\star\) non-problematic admissible ears such that \((T(\Psi^\star(P)) : P\in \mathcal{N})\) is a collection of pairwise vertex-disjoint graphs. Thus \((\Psi^\star(P):P\in \mathcal{N})\) is a collection of pairwise disjoint sets of vertices of \(F^\star\). Consequently, for all distinct \(P,Q\in \mathcal{N}\) and all \(m\in \{-1, 0, \dots, p\}\) we have \(\Psi_m(P)\cap \Psi_m(Q)=\varnothing\). Then by [clm:dist-and-proj] and [clm:dist-and-W], for all distinct \(P,Q\in \mathcal{N}\), \[\label{eq:W95P-and-W95Q-are-far-in-C} \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(P), \mathop{\mathrm{proj}}_U(Q)) > d\ell.\tag{15}\] and \[\label{eq:W95P-and-W95Q-are-far-in-G} \mathop{\mathrm{dist}}_G(V(W_P), V(W_Q)) > d,\tag{16}\]

For each \(P\in \mathcal{N}\), either \(W_P\) is a path or \(W_P\) contains a cycle. Let be the set of all \(P\in \mathcal{N}\) such that \(W_P\) is a path.

\(G\) contains a \(d\)-packing of \(|\mathcal{N}\setminus \mathcal{P}|\) cycles each of length at least \(\ell\).

Proof of Claim. For each ear \(E\in \mathcal{N}\setminus \mathcal{P}\), let \(D_P\) be a cycle in \(W_E\). Therefore 16 implies that \(\set{D_E : E\in \mathcal{N}\setminus \mathcal{P}}\) is a \(d\)-packing of \(|\mathcal{N}\setminus \mathcal{P}|\) cycles in \(G\). Now consider each \(E\in \mathcal{N}\setminus \mathcal{P}\). Since \(W_E\) contains a cycle, \(E\) must be an \((i,i)\)-ear for some \(i\in [p]\). Then since \(E\) is non-problematic, every cycle in \(W_E\cup C_i\) has length at least \(\ell\), implying \(\mathop{\mathrm{len}}(D_E)\geqslant\ell\). ◻

If \(|\mathcal{N}\setminus \mathcal{P}| \geqslant k\), then by [clm:non-problematic-walks-with-cycles] \(G\) contains a \(d\)-packing of \(k\) cycles each of length at least \(\ell\), a contradiction. Hence \(|\mathcal{N}\setminus \mathcal{P}| \leqslant k-1\), which along with \(|\mathcal{N}| = k^\star \geqslant s(k)/2+k-1\) implies that \(2|\mathcal{P}| \geqslant s(k)\).

Consider the graph \[\textstyle \mathdefin{G'}\mathrel{\vcenter{:}}= \bigcup\mathscr{C}\cup \bigcup_{E\in \mathcal{P}}W_E.\] Recall that \(\mathscr{C}\) is a collection of pairwise vertex-disjoint cycles. Also, 16 implies that \((W_E : E\in \mathcal{P})\) is a collection of pairwise vertex-disjoint paths. Furthermore, no edge or inner vertex of \(W_E\) appears in \(\bigcup \mathscr{C}\) for all \(E\in \mathcal{P}\). Therefore every vertex \(v\in V(G')\) satisfies \(\deg_{G'}(v)\in \set{2,3}\), and the degree-3 vertices of \(G'\) are precisely the endpoints of paths in \((W_E:E\in \mathcal{P})\). Hence \(G'\) has \(2|\mathcal{P}| \geqslant s(k)\) degree-3 vertices.

Any path in \(G'\) whose endpoints are degree-\(3\) vertices and whose inner vertices are degree-\(2\) is a . Any segment is either a \(W_E\) for some \(E\in \mathcal{P}\) (called a ) or is a path in \(\bigcup\mathscr{C}\) between an endpoint of \(W_P\) and an endpoint of \(W_Q\) for some \(P, Q\in \mathcal{P}\) (called a ).

Every cycle in \(G'\) has length at least \(\ell\).

Proof of Claim. Every cycle in \(\mathscr{C}\) has length at least \(\ell\). Now consider any cycle \(D\) in \(G'\) that is not in \(\mathscr{C}\). Then \(D\) contains a \(\mathcal{P}\)-segment. If \(D\) contains exactly one \(\mathcal{P}\)-segment, then there exists \(P\in \mathcal{P}\) and \(i\in [p]\) such that \(P\) is an \((i,i)\)-ear and \(D \subseteq W_P\cup C_i\). Since \(P\) is non-problematic, every cycle in \(W_P\cup C_i\) has length at least \(\ell\), implying \(\mathop{\mathrm{len}}(D)\geqslant\ell\). On the other hand, if \(D\) contains more than one \(\mathcal{P}\)-segment, then there exists distinct \(P,Q\in \mathcal{P}\) and a \(\mathscr{C}\)-segment \(S\) between an endpoint of \(W_P\) and an endpoint of \(W_Q\) such that \(S\subseteq D\). Thus 15 implies \(\mathop{\mathrm{len}}(D) > \mathop{\mathrm{len}}(S) \geqslant\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(P), \mathop{\mathrm{proj}}_U(Q)) > d\ell \geqslant\ell\). ◻

We remark that the following proof is similar to [clm:disjoint-cycles-in-G39-are-far-apart].

For every pair of vertex-disjoint cycles \(D\) and \(D'\) in \(G'\), \(\mathop{\mathrm{dist}}_G(V(D), V(D')) > d\).

If \(u\in V(W_P)\) and \(u'\in V(W_Q)\) for some \(P,Q\in \mathcal{P}\) with \(W_P\subseteq D\) and \(W_Q\subseteq D'\), then since \(D\) and \(D'\) are vertex-disjoint, \(P\not=Q\). Therefore \(\mathop{\mathrm{dist}}_G(u,u') \geqslant\mathop{\mathrm{dist}}_G(V(W_P), V(W_Q)) > d\) by 16 , a contradiction. Hence it may be assumed that \(u\not\in V(W_P)\) for every \(P\in \mathcal{P}\) with \(W_P\subseteq D\). Consequently, there exists \(C\in \mathscr{C}\) such that \(u\in V(C)\).

Let \(P\) be a shortest \((u,u')\)-path in \(G\). Since \(\mathop{\mathrm{dist}}_G(u,u')\leqslant d\), \(\mathop{\mathrm{len}}(P)\leqslant d\), so \(V(P)\subseteq B_G(V(C), d)\). In particular, since \(\mathscr{C}\) is a \(2d\)-packing in \(G\), \(u'\in B_G(V(C), d)\) and \(u'\not\in B_G(V(\bigcup\mathscr{C})\setminus V(C), d)\). Therefore \(\mathop{\mathrm{proj}}_U(u')\) exists and is a vertex of \(C\). Furthermore, either \(u'\in V(C)\) or \(u'\) lies in the first or second leg of some \(Q\mathrel{\vcenter{:}}= q_0 q_1 \cdots q_h\in \mathcal{P}\) with \(W_Q\subseteq D'\). In the former case, \(\mathop{\mathrm{proj}}_U(u')=u'\in V(D')\), and in the latter case \(\mathop{\mathrm{proj}}_U(u')\in V(U\relax{u'}) \subseteq V(U\relax{q_0}\cup U\relax{q_h}) \subseteq V(W_Q) \subseteq V(D')\). Hence \(\mathop{\mathrm{proj}}_U(u')\in V(D')\) in both cases.

Let \(v_0, v_1, \dots, v_s\) be the sequence of vertices along \(P\) such that \(v_0=u\), \(v_s=u'\), and \(s\leqslant d\). Since \(V(P)\subseteq B_G(V(C), d) \subseteq V(G_d)\), then [clm:G95d-has-small-span] implies that \(\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e) = \mathop{\mathrm{span}}(G_d, \bigcup\mathscr{C}, U[V(G_d)], e) \leqslant\ell\) for every \(e\in E(P)\). Therefore: \[\begin{align} \mathop{\mathrm{dist}}_C(u,\mathop{\mathrm{proj}}_U(u'))=\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(u,\mathop{\mathrm{proj}}_U(u')) &\leqslant\sum_{i=1}^{s}\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v_{i-1}), \mathop{\mathrm{proj}}_U(v_i))\notag\\ &= \sum_{i=1}^{s}\textstyle\mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, v_{i-1}v_i)\leqslant s\ell \leqslant d\ell.\label{eq:main-dist-between-u-and-proj95U40u3941} \end{align}\tag{17}\] Now consider a shortest \((u,\mathop{\mathrm{proj}}_U(u'))\)-path \(S\) in \(C\). Recall that \(u\in V(D)\) and \(\mathop{\mathrm{proj}}_U(u')\in V(D')\). Let \(x\) be the first vertex in \(S\) starting from \(u\) such that \(x\in V(W_Q)\) for some \(Q\in \mathcal{P}\) with \(W_Q\subseteq D\). Let \(y\) be the first vertex in \(S\) starting from \(\mathop{\mathrm{proj}}_U(u')\) such that \(y\in V(W_E)\) for some \(E\in \mathcal{P}\) with \(W_E\subseteq D'\). Since \(D\) and \(D'\) are vertex-disjoint, both vertices \(x\) and \(y\) exist and \(Q\not=E\). Note that \(\mathop{\mathrm{dist}}_C(x,y)\leqslant\mathop{\mathrm{dist}}_C(u, \mathop{\mathrm{proj}}_U(u')) \leqslant d\ell\) by 17 . On the other hand, \(x\in V(C)\cap V(W_Q) \subseteq \mathop{\mathrm{proj}}_U(Q)\), \(y\in V(C)\cap V(W_E)\subseteq \mathop{\mathrm{proj}}_U(E)\), \(Q\) and \(E\) are distinct elements of \(\mathcal{P}\subseteq \mathcal{N}\), and 15 together imply \(\mathop{\mathrm{dist}}_C(x,y)\geqslant\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(Q), \mathop{\mathrm{proj}}_U(E)) > d\ell\), a contradiction. ◻

Since \(G'\) is a graph with all vertices of degree \(2\) or \(3\) and contains at least \(s(k)\) degree-3 vertices, [thm:simonovits] implies that \(G'\) contains \(k\) pairwise vertex-disjoint cycles. By [clm:main-cycles-in-G39-are-long], each of these cycles has length at least \(\ell\), and by [clm:main-disjoint-cycles-in-G39-are-far-apart], these cycles form a \(d\)-packing in \(G\). Hence \(G\) contains a \(d\)-packing of \(k\) cycles each of length at least \(\ell\), a contradiction.

Case [item:covering:alon] there exists a subset \(\mathdefin{X^\star}\subseteq V(T)\) with \(|X^\star|\leqslant 50(k^\star-1)\) such that \(X^\star\cap V(A)\not=\varnothing\) for all \(A\in \mathcal{A}\): Recall that \(\mathcal{A}\) is the set of all graphs \(T(\Psi^\star(P))\) where \(P\) is a non-problematic admissible ear. Let \(\mathdefin{B_{-1}^\star}\mathrel{\vcenter{:}}= \bigcup_{t\in X^\star \cap V(T_{-1})}\beta(t)\) and \(\mathdefin{B_{\geqslant 0}^\star}\mathrel{\vcenter{:}}= \bigcup_{t\in X^\star \cap V(T_{\geqslant 0})}\beta(t)\). Consider any non-problematic admissible ear \(P\). The definition of \(X^\star\) implies that \((B_{-1}^\star\cup B_{\geqslant 0}^\star)\cap \Psi^\star(P)\not=\varnothing\). Therefore \(B_{-1}^\star\cap \pi_{-1}(\Psi_{-1}(P))\not=\varnothing\) or \(B_{\geqslant 0}^\star\cap \bigcup_{m=0}^{p}\pi_m(\Psi_m(P))\not=\varnothing\). Let \(\mathdefin{S_{-1}}\mathrel{\vcenter{:}}= \pi_{\!-1}^{-1}(B_{-1}^\star)\) and \(\mathdefin{S_{\geqslant 0}}\mathrel{\vcenter{:}}= \bigcup_{m=0}^{p}\pi_m^{-1}(B_{\geqslant 0}^\star)\). Then \(S_{-1}\subseteq V(\bigcup\mathscr{C})\), \(S_{\geqslant 0}\subseteq V(G)\), and \(S_{-1}\cap\Psi_{-1}(P)\not=\varnothing\) or \(S_{\geqslant 0}\cap \bigcup_{m=0}^{p}\Psi_m(P)\not=\varnothing\). Consequently, by letting \(\mathdefin{X_3}\mathrel{\vcenter{:}}= \mathop{\mathrm{pad}}(\bigcup\mathscr{C}, S_{-1}, 2d, \ceil{\ell/2})\cup S_{\geqslant 0}\), [clm:hitting-Phi-and-Psi] implies that \[\label{eq:X953-hits-non-problematic-admissible-ears} \text{\textstyle B_G(X_3,r)\cap V(P)\not=\varnothing for every non-problematic admissible ear P.}\tag{18}\] By [cor:def-of-pad], \[\begin{align} |X_3| &\leqslant\textstyle |\mathop{\mathrm{pad}}(\bigcup\mathscr{C}, S_{-1}, 2d, \ceil{\ell/2})| + |S_{\geqslant 0}|\notag\\ &\leqslant|S_{-1}|(2\ceil{\ell/2}+1) + |S_{\geqslant 0}|.\notag \intertext{Since |S_{-1}|\leqslant|B_{-1}^\star| and |S_{\geqslant 0}|\leqslant|B_{\geqslant 0}^\star|, we have} |X_3| &\leqslant|B_{-1}^\star|(2\ceil{\ell/2}+1) + |B_{\geqslant 0}^\star|.\notag \intertext{By \eqref{eq:size-of-bags},} |X_3|&\leqslant 2|X^\star \cap V(T_{-1})|(2\ceil{\ell/2}+1) + (\ell-1)|X^\star \cap V(T_{\geqslant 0})|.\notag \intertext{Since |X^\star \cap V(T_{-1})|+|X^\star \cap V(T_{\geqslant 0})|=|X^\star|\leqslant 50(k^\star-1) and \ell-1\leqslant 2\ceil{\ell/2}+1,} |X_3| &\leqslant(2|X^\star|-|X^\star \cap V(T_{\geqslant 0})|)(2\ceil{\ell/2}+1)\notag\\ &\leqslant 100(k^\star-1)(2\ceil{\ell/2}+1).\notag\\ \intertext{Since 2(k^\star-1) \leqslant s(k)+2(k-1)-1,} |X_3| &\leqslant 50(s(k)+2(k-1)-1)(2\ceil{\ell/2}+1).\label{eq:size-of-X953} \end{align}\tag{19}\]

For every cycle \(D\) in \(G\) of length at least \(\ell\), either

\(D\) contains a vertex in \(B_G(M\cup X_3,r)\), or

\(D\) is the union of pairwise internally disjoint paths \(Q_1\cup \cdots \cup Q_{2t}\) with \(t\geqslant 2\), such that

the start vertex of \(Q_i\) is the end vertex of \(Q_{i-1 \;\mathrm{mod}\;2t}\) for all \(i\in [2t]\);

\(V(Q_1\cup Q_3\cup \cdots \cup Q_{2t-1}) = V(D)\cap B_G(V(\bigcup\mathscr{C}), r-d)\);

\(\set{Q_2, Q_4, \dots, Q_{2t}}\) is a collection of problematic admissible ears.

Proof of Claim. Consider any cycle \(D\) in \(G\) of length at least \(\ell\). If \(D\) contains a vertex in \(B_G(M\cup X_3,r)\), then [item:D-is-close-to-M-or-X953:cycles-far-from-M-and-X953-decompose] holds. Hence it may be assumed that \(V(D)\cap B_G(M\cup X_3,r)=\varnothing\). Recall that \(Z\cup L\subseteq M\) by 12 , hence \(V(D)\cap Z\) and \(V(D)\cap L\) are empty.

As a preliminary step towards [item:decomposition:cycles-far-from-M-and-X953-decompose], we show that \(V(D)\subseteq (B_G(V(\bigcup\mathscr{C}), r-d)\setminus L)\cup V(F_0^-)\), \(V(D)\not \subseteq B_G(V(\bigcup\mathscr{C}), r-d)\setminus L\), and \(V(D)\not\subseteq V(F_0^-)\). Then, since \(G[B_G(V(\bigcup\mathscr{C}), r-d)\setminus L]\) and \(F_0^-\) are vertex-disjoint subgraphs of \(G\), it will follow that \(D\) is the union of pairwise internally disjoint paths \(Q_1\cup \cdots \cup Q_{2t}\) such that

the start vertex of \(Q_i\) is the end vertex of \(Q_{i-1 \;\mathrm{mod}\; 2t}\) for all \(i\in [2t]\);

\(V(Q_1\cup Q_3\cup \cdots \cup Q_{2t-1}) = V(D)\cap B_G(V(\bigcup\mathscr{C}), r-d)\);

for all \(i\in[t]\), \(\mathop{\mathrm{len}}(Q_{2i})\geqslant 2\) and the inner vertices of \(Q_{2i}\) lie in \(V(F_0^-)\).

Since \(V(D)\cap Z=\varnothing\), \(V(D)\subseteq B_G(V(\bigcup\mathscr{C}), r-d) \cup V(F_0^-)\). Furthermore, since \(V(D)\cap L=\varnothing\), \(V(D)\subseteq (B_G(V(\bigcup\mathscr{C}), r-d)\setminus L) \cup V(F_0^-)\). Now 7 implies \(V(D)\not\subseteq B_G(V(\bigcup\mathscr{C}), r-d)\setminus L\), and since \(F_0^-\) is an induced subgraph of \(G\), 9 implies \(V(D)\not\subseteq V(F_0^-)\). This completes the preliminary step.

To show [item:decomposition:cycles-far-from-M-and-X953-decompose], it now suffices to show that \(\set{Q_2, Q_4, \dots, Q_{2t}}\) is a collection of problematic admissible ears. Consider any \(Q\in \set{Q_2, Q_4, \dots, Q_{2t}}\) and let \(Q'\) be the path obtained from \(Q\) by deleting its endpoints. Since \(V(Q')\subseteq F_0^-\) and \(F_0^-\) is an induced subgraph of \(G\), \(Q'\) is a path in \(F_0^-\). Therefore since the endpoints of \(Q\) lie in \(B_G(V(\bigcup\mathscr{C}), r-d) = \bigcup_{i\in [p]}V(U_i)\), \(Q\) is an ear. To see that \(Q\) is admissible, note that since \(Q\subseteq D\) and \(V(D)\cap B_G(M,r)=\varnothing\), \(V(Q)\cap B_G(M,r)=\varnothing\), thus \(V(W_Q) \subseteq B_G(V(Q), r-d)\) implies that \(V(W_Q)\cap B_G(M, d)=\varnothing\). Finally, if \(Q\) is non-problematic, then 18 implies \(B_G(X_3,r)\cap V(Q)\not=\varnothing\), therefore \(B_G(X_3, r)\cap V(D)\not=\varnothing\), a contradiction. ◻

Let be the set of all pairs \(uv\in \binom{V(G)}{2}\) such that there exists a problematic admissible ear whose set of endpoints is \(\set{u,v}\). Consider the auxiliary graph \(\mathdefin{G_{\mathop{\mathrm{Aux}}}}\mathrel{\vcenter{:}}= G_R\cup \mathcal{E}\).

Let be the set of cycles \(D\) in \(G\) that satisfy \(B_G(M\cup X_3, r+d)\cap V(D)=\varnothing\) and \(\mathop{\mathrm{len}}(D)\geqslant\ell\). For each \(D\in \mathcal{D}\), let \(\mathdefin{H_D}\mathrel{\vcenter{:}}= G_{\mathop{\mathrm{Aux}}}[B_{G_{\mathop{\mathrm{Aux}}}}(V(D)\cap B_G(V(\bigcup\mathscr{C}), r-d), \ceil{d/2})]\). Observe that by decomposing \(D\in\mathcal{D}\) into a union of paths \(Q_1\cup \cdots \cup Q_{2t}\) as per [clm:cycles-far-from-M-and-X953-decompose], we may write \[\label{eq:H95D} H_D=G_{\mathop{\mathrm{Aux}}}[B_{G_{\mathop{\mathrm{Aux}}}}(V(Q_1\cup Q_3\cup \cdots \cup Q_{2t-1}), \ceil{d/2})].\tag{20}\]

For every pair \(D,D'\in \mathcal{D}\) with \(V(H_D)\cap V(H_{D'})=\varnothing\), \(\mathop{\mathrm{dist}}_G(V(D), V(D'))>d\).

Proof of Claim. Assume for a contradiction that there exists a pair \(D, D'\in\mathcal{D}\) with \(V(H_D)\cap V(H_{D'})=\varnothing\) such that \(\mathop{\mathrm{dist}}_G(V(D), V(D'))\leqslant d\). Recall that \(B_G(M\cup X_3, r)\cap V(D)=\varnothing\) and \(B_G(M\cup X_3, r)\cap V(D')=\varnothing\), hence we may write \(D=Q_1\cup \cdots \cup Q_{2t}\) and \(D'=Q_1'\cup \cdots \cup Q_{2s}'\) according to [clm:cycles-far-from-M-and-X953-decompose]. Let \(i\in [2t]\) and \(j\in [2s]\) such that \(\mathop{\mathrm{dist}}_G(V(Q_i),V(Q_j'))\leqslant d\). Let \(P\) be a shortest \((V(Q_i), V(Q_j'))\)-path in \(G\). Let \(u\) be the endpoint of \(P\) in \(Q_i\) and let \(u'\) be the endpoint of \(P\) in \(Q_j'\).

The following shows that if \(E\) is a path in \(Q_i\cup P\cup Q_j'\) with \(\mathop{\mathrm{len}}(E)\geqslant 2\) and \(V(E)\cap B_G(V(\bigcup\mathscr{C}), r-d)\) equals the set of endpoints of \(E\), then \(E\) is a problematic admissible ear: Since \(Q_i\cup Q_j'\subseteq D\cup D'\) and \(V(D\cup D')\cap B_G(M\cup X_3, r+d)=\varnothing\), \(V(Q_i\cup P\cup Q_j')\cap B_G(M\cup X_3, r)=\varnothing\). Then \[\label{eq:E-is-far-from-M-and-X953} V(E)\cap B_G(M\cup X_3, r)=\varnothing.\tag{21}\] Let \(E'\) be the path obtained from \(E\) by deleting its endpoints. Then 21 and 12 imply \(V(E')\cap Z=\varnothing\), thus \(E'\) is a path in \(F_0^-\). Therefore since the endpoints of \(E\) lie in \(B_G(V(\bigcup\mathscr{C}), r-d)\), \(E\) is an ear. Next, since \(V(W_E)\subseteq B_G(V(E), r-d)\), 21 implies \(V(W_E)\cap B_G(M, d)=\varnothing\), thus \(E\) is admissible. Therefore 21 and 18 imply that \(E\) is problematic.

Let \(V\mathrel{\vcenter{:}}= V(Q_1\cup Q_3\cup \cdots \cup Q_{2t-1})\) and \(V'\mathrel{\vcenter{:}}= V(Q_1'\cup Q_3'\cup \cdots \cup Q_{2s-1}')\). Observe that since \(V(H_D)\cap V(H_{D'})=\varnothing\), \(\mathop{\mathrm{dist}}_{G_{\mathop{\mathrm{Aux}}}}(V,V') \geqslant 2\ceil{d/2}+1>d\).

We now show that \(i\) is even, \(j\) is even, \(u\) is an inner vertex of \(Q_i\), and \(u'\) is an inner vertex of \(Q_j'\). By symmetry it suffices to prove that \(i\) is even and \(u\) is an inner vertex of \(Q_i\). Assume for a contradiction that \(i\) is odd or \(u\) is an endpoint of \(Q_i\). Then \(u'\) is an inner vertex of \(Q_j'\) and \(j\) is even, otherwise \(d \geqslant\mathop{\mathrm{len}}(P) \geqslant\mathop{\mathrm{dist}}_{G_R}(V, V') \geqslant\mathop{\mathrm{dist}}_{G_{\mathop{\mathrm{Aux}}}}(V,V') > d\), a contradiction. Note that \(u\in B_G(V(\bigcup\mathscr{C}), r-d)\) and \(u'\not\in B_G(V(\bigcup\mathscr{C}), r-d)\), thus \(u\not=u'\). Let \(x\) be an endpoint of \(Q_j'\). Let \(y\in V(P-u')\cap B_G(V(\bigcup\mathscr{C}), r-d)\) such that the path \(E\mathrel{\vcenter{:}}= x Q_j' u' \cup u' P y\) has minimum possible length. Such a \(y\) exists since \(u\) is a candidate and \(u\not=u'\). Since \(Q_j'\) is an ear, the inner vertices of \(Q_j'\) are disjoint from \(B_G(V(\bigcup \mathscr{C}), r-d)\), therefore \(E\cap B_G(V(\bigcup\mathscr{C}), r-d) = \{x,y\}\). Moreover, \(\mathop{\mathrm{len}}(E)\geqslant 2\) since \(E\) has an inner vertex \(u'\). Consequently, \(E\) is a problematic admissible ear, and \(xy\) is an edge of \(G_{\mathop{\mathrm{Aux}}}\). Then \(xy\cup yPu\) is a \((V',V)\)-path in \(G_{\mathop{\mathrm{Aux}}}\) of length at most \(d\), a contradiction. Hence \(i\) is even, \(j\) is even, \(u\) is an inner vertex of \(Q_i\), and \(u'\) is an inner vertex of \(Q_j'\).

For the final contradiction of the claim, we show that there exists edges \(e,e'\in E(G_{\mathop{\mathrm{Aux}}})\), such that \(e\) is between an endpoint of \(Q_i\) and an inner vertex of \(P\), and \(e'\) is between an endpoint of \(Q_j\) and an inner vertex of \(P\). This will imply \(d\geqslant\mathop{\mathrm{dist}}_{G_{\mathop{\mathrm{Aux}}}}(V, V')\), a contradiction. By symmetry, it suffices to prove the existence of \(e\). Let \(Q\) be a shortest path in \(Q_i\cup P\cup Q_j'\) between the set of endpoints of \(Q_i\) and the set of endpoints of \(Q_j'\). Then the endpoints of \(Q\) lie in \(B_G(V(\bigcup\mathscr{C}), r-d)\). If \(\mathop{\mathrm{len}}(Q)\leqslant 1\), then \(d\geqslant 1\geqslant\mathop{\mathrm{dist}}_{G_R}(V, V') \geqslant\mathop{\mathrm{dist}}_{G_{\mathop{\mathrm{Aux}}}}(V, V')\), a contradiction. Hence \(\mathop{\mathrm{len}}(Q)\geqslant 2\). If \(V(Q)\cap B_G(V(\bigcup\mathscr{C}), r-d)\) equals the set of endpoints of \(Q\), then \(Q\) is a problematic admissible ear and there exists an edge of \(G_{\mathop{\mathrm{Aux}}}\) between the endpoints of \(Q\), which implies \(d\geqslant 1 \geqslant\mathop{\mathrm{dist}}_{G_{\mathop{\mathrm{Aux}}}}(V, V')\), a contradiction. Hence it may be assumed that some inner vertex of \(Q\) lies in \(B_G(V(\bigcup\mathscr{C}), r-d)\). Since \(Q\subseteq Q_i\cup P\cup Q_j'\) and \(Q_i\) and \(Q_j'\) are ears, such a vertex lies in \(V(P)\). Let \(x\) be the endpoint of \(Q\) in \(Q_i\). Let \(y\in V(P)\cap B_G(V(\bigcup\mathscr{C}), r-d)\) such that the path \(E\mathrel{\vcenter{:}}= x Q u \cup u P y\) has minimum possible length. Since the inner vertices of \(Q_i\) and \(Q_j'\) are disjoint from \(B_G(V(\bigcup\mathscr{C}), r-d)\), \(u\) and \(u'\) are not in \(B_G(V(\bigcup\mathscr{C}), r-d)\), thus \(y\) is an inner vertex of \(P\). Furthermore, \(E\cap B_G(V(\bigcup\mathscr{C}), r-d) = \{x,y\}\). Also, \(\mathop{\mathrm{len}}(E)\geqslant 2\) since \(E\) has an inner vertex \(u\). It follows that \(E\) is a problematic admissible ear, and \(e\mathrel{\vcenter{:}}= xy\) is an edge of \(G_{\mathop{\mathrm{Aux}}}\) between an endpoint of \(Q_i\) and an inner vertex of \(P\), as required. ◻

\(U\) is a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_{\mathop{\mathrm{Aux}}}\).

Proof of Claim. Recall that for every edge \(e\in \mathcal{E}\), both endpoints of \(e\) have distance exactly \(r-d\) from \(V(\bigcup\mathscr{C})\) in \(G\). Hence \(\mathop{\mathrm{dist}}_{G\cup \mathcal{E}}(V(\bigcup\mathscr{C}), v)=\mathop{\mathrm{dist}}_G(V(\bigcup\mathscr{C}), v)\) for all \(v\in V(G\cup \mathcal{E})=V(G)\). Consequently, every \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G[B_G(V(\bigcup\mathscr{C}), R)]\) is a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \((G\cup \mathcal{E})[B_{G\cup \mathcal{E}}(V(\bigcup\mathscr{C}), R)]\). Therefore since \(G[B_G(V(\bigcup\mathscr{C}), R)] = G_R\) and \((G\cup \mathcal{E})[B_{G\cup \mathcal{E}}(V(\bigcup\mathscr{C}), R)] = G_R\cup \mathcal{E} = G_{\mathop{\mathrm{Aux}}}\), \(U\) is a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_{\mathop{\mathrm{Aux}}}\). ◻

For every \(D\in \mathcal{D}\), \(H_D\) is a non-null connected subgraph of \(G_{\mathop{\mathrm{Aux}}}\) such that every edge \(e\in E(H_D)\) satisfies \(\mathop{\mathrm{span}}(G_{\mathop{\mathrm{Aux}}}, \bigcup\mathscr{C}, U, e)\leqslant\ell\).

Proof of Claim. Consider any \(D\in \mathcal{D}\) and write \(D=Q_1\cup \cdots \cup Q_{2t}\) as per [clm:cycles-far-from-M-and-X953-decompose]. First note that \(\varnothing\not= V(Q_1\cup Q_3\cup \cdots \cup Q_{2t-1}) = V(D)\cap B_G(V(\bigcup\mathscr{C}), r-d)\subseteq V(G_R) = V(G_{\mathop{\mathrm{Aux}}})\). Now since \(\{Q_2, Q_4, \dots, Q_{2t}\}\) is a collection of problematic admissible ears, for each \(i\in [t]\) there exists an edge in \(G_{\mathop{\mathrm{Aux}}}\) between the endpoints of \(Q_{2i}\). Consequently, \(V(Q_1\cup Q_3\cup \cdots \cup Q_{2t-1})\) is a non-empty connected set of vertices in \(G_{\mathop{\mathrm{Aux}}}\). Then by 20 , \(H_D\) is a non-null connected subgraph of \(G_{\mathop{\mathrm{Aux}}}\). We now show that \(\mathop{\mathrm{span}}(G_{\mathop{\mathrm{Aux}}}, \bigcup\mathscr{C}, U, e)\leqslant\ell\) for every edge \(e\in E(H_D)\). Consider any edge \(e\in E(H_D)\). Since \(H_D\subseteq G_{\mathop{\mathrm{Aux}}} = G_R\cup \mathcal{E}\), either (1) \(e\in \mathcal{E}\) or (2) \(e\in E(G_R)\).

Case (1) \(e\in \mathcal{E}\): Then for some \(i\in [p]\) there exists an \(i\)-problematic admissible ear \(E\) that has the same endpoints as \(e\). Then \(E\) is an \((i,i)\)-ear and there exist a cycle in \(W_E\cup C_i\) of length less than \(\ell\). Therefore since \(\mathop{\mathrm{len}}(C_i)\geqslant\ell\), the endpoints of the walk \(W_E\) have distance less than \(\ell\) in \(C_i\), which implies \(\mathop{\mathrm{span}}(G_{\mathop{\mathrm{Aux}}}, \bigcup\mathscr{C}, U, e)<\ell\) as required.

Case (2) \(e\in E(G_R)\): Let \(V\mathrel{\vcenter{:}}= V(D)\cap B_G(V(\bigcup\mathscr{C}), r-d)\). Recall that \(W\subseteq M\) by 6 and 11 . We show that an endpoint of \(e\) is not in \(W\), which implies that \(\mathop{\mathrm{span}}(G_{\mathop{\mathrm{Aux}}}, \bigcup\mathscr{C}, U, e) = \mathop{\mathrm{span}}(G_R, \bigcup\mathscr{C}, U, e)\leqslant\ell\) as required. Recall that \(e\in E(H_D)\). Let \(P\) be a shortest path in \(G_{\mathop{\mathrm{Aux}}}\) between \(V\) and the set of endpoints of \(e\). Then \(\mathop{\mathrm{len}}(P)\leqslant\ceil{d/2}\) and \(e\not\in E(P)\). Let \(v\) be the endpoint of \(e\) in \(P\). If \(P\subseteq G_R\), then \(B_G(M, r+d)\cap V(D)=\varnothing\) implies that \(v\) is not in \(B_G(M, r+d-\mathop{\mathrm{len}}(P))\). Therefore \(v\not\in W\) as required. On the other hand \(P\not\subseteq G_R\), so \(P\) contains an edge from \(\mathcal{E}\). Let \(xy\in E(P)\cap \mathcal{E}\) such that \(\mathop{\mathrm{dist}}_P(v, \set{x,y})\) is minimum. Then \(\mathop{\mathrm{dist}}_G(v, \set{x,y}) \leqslant\ceil{d/2}\). Let \(E\) be a problematic admissible ear whose set of endpoints is \(\set{x,y}\). Since \(E\) is admissible, \(V(W_E)\cap B_G(M, d)=\varnothing\), thus \(\set{x,y}\subseteq V(W_E)\) implies that \(\set{x,y}\cap B_G(W, d)=\varnothing\). Therefore since \(\mathop{\mathrm{dist}}_G(v, \set{x,y})\leqslant\ceil{d/2}\), \(v\not\in W\) as required. ◻

Now \(\mathscr{C}\) is a non-empty collection of pairwise vertex-disjoint cycles in \(G\cup\mathcal{E}\) and, by [clm:U95Aux-is-BFS-spanning], \(U\) is a \(\bigcup\mathscr{C}\)-supported BFS-spanning subgraph of \(G_{\mathop{\mathrm{Aux}}}\). Note that the earlier definition of \(G_{\mathop{\mathrm{Aux}}}\) is equivalent to \((G\cup \mathcal{E})[B_{G\cup \mathcal{E}}(V(\bigcup\mathscr{C}), R)]\). Furthermore by [clm:main-edges-of-H95D-have-big-span], \(\mathdefin{\mathcal{H}}\mathrel{\vcenter{:}}= \set{H_D:D\in \mathcal{D}}\) is a collection of non-null connected subgraphs of \(G_{\mathop{\mathrm{Aux}}}\) such that \(\mathop{\mathrm{span}}(G_{\mathop{\mathrm{Aux}}}, \bigcup\mathscr{C}, U, e)\leqslant\ell\) for every \(e\in E(\bigcup\mathcal{H})\). Hence we may proceed by cases depending on the outcome of [lem:cycle-helly-for-small-span-collection].

Case [item:packing:cycle-helly-for-small-span-collection] \(\mathcal{H}\) contains \(k\) pairwise vertex-disjoint members: Then there exists \(\mathcal{D}'\subseteq \mathcal{D}\) with \(|\mathcal{D}'|=k\) such that \(V(H_A)\cap V(H_B)=\varnothing\) for all distinct \(A,B\in \mathcal{D}'\). By [clm:disjoint-H39s-implies-far-away-D39s], \(\mathcal{D}'\) is a \(d\)-packing of \(k\) cycles in \(G\), and by definition of \(\mathcal{D}\), each of these cycles has length at least \(\ell\). Hence \(G\) contains a \(d\)-packing of \(k\) cycles each of length at least \(\ell\), a contradiction.

Case [item:alternative:cycle-helly-for-small-span-collection] there exists \(\mathdefin{Y}\subseteq V(\bigcup\mathscr{C})\) with \(|Y|\leqslant k-1+|\mathscr{C}|\) such that for \(\mathdefin{X_4'}\mathrel{\vcenter{:}}= B_{\bigcup\mathscr{C}}(Y,\floor{\ell/2})\), \(B_U(X_4', R)\cap V(H)\not=\varnothing\) for all \(H\in \mathcal{H}\). Since \(|\mathscr{C}|\leqslant p\leqslant k-1\), \(|Y|\leqslant 2(k-1)\). Let \(\mathdefin{X_4}\mathrel{\vcenter{:}}= \mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y, 2\ceil{d/2}+1, \ceil{\ell/2})\). Then by [cor:def-of-pad], \[\label{eq:size-of-X954} |X_4|\leqslant|Y|(2\ceil{\ell/2}+1) \leqslant 2(k-1)(2\ceil{\ell/2}+1).\tag{22}\] Let \(\mathdefin{X}\mathrel{\vcenter{:}}= X_0\cup X_1 \cup X_2 \cup X_3 \cup X_4\). Then (2 , 5 , 8 , 19 , 22 ) imply \[\begin{align} |X| &\leqslant|X_0| + |X_1| + |X_2| + |X_3| + |X_4|\notag\\ &\leqslant k-1 + (s(k)-1)(2\ceil{\ell/2}+1) + 2(k-1)(2\ceil{\ell/2}+1)\notag\\ &\qquad\qquad+ 50(s(k)+2(k-1)-1)(2\ceil{\ell/2}+1) + 2(k-1)(2\ceil{\ell/2}+1)\notag\\ &= (51s(k)+104k-155)(2\ceil{\ell/2}+1)+k-1\notag\\ &=f(k,\ell).\label{eq:f40k41} \end{align}\tag{23}\]

By 11 , \[\begin{align} B_G(M\cup X_3, r+d)\cup B_G(X_4, r-\floor{d/2}) &\subseteq B_G(X, R+2r+2d)\qquad\qquad\notag\\ &\subseteq B_G(X, 21d)\notag\\ &= B_G(X, g(d)).\label{eq:g40d41} \end{align}\tag{24}\]

\(G-B_G(X, g(d))\) has no cycle of length at least \(\ell\).

Proof of Claim. Consider any cycle \(D\) in \(G\) of length at least \(\ell\). We show that \(B_G(X, g(d)) \cap V(D)\not=\varnothing\). If \(B_G(M\cup X_3, r+d)\cap V(D)\not=\varnothing\), then 24 implies \(B_G(X, g(d)) \cap V(D)\not=\varnothing\) as required. Hence it may be assumed that \(B_G(M\cup X_3, r+d)\cap V(D)=\varnothing\), in other words, \(D\in \mathcal{D}\). Let \(u \in B_U(X_4', R)\cap V(H_D)\) as promised by the case [item:alternative:cycle-helly-for-small-span-collection] above. Since \(X_4'\subseteq V(\bigcup\mathscr{C})\), there exists \(x\in X_4'\) such that \(x=\mathop{\mathrm{proj}}_U(u)\). Since \(u\in V(H_D) = B_{G_{\mathop{\mathrm{Aux}}}}(V(D)\cap B_G(V(\bigcup\mathscr{C}), r-d), \ceil{d/2})\), there exists \(v\in V(D)\cap B_G(V(\bigcup\mathscr{C}), r-d)\) and a path \(q_0 q_1\cdots q_s\) in \(H_D\) such that \(q_0=v\), \(q_s=u\), and \(s\leqslant\ceil{d/2}\). Then by [clm:main-edges-of-H95D-have-big-span], \[\begin{align} \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), x) &\leqslant\sum_{i=1}^{s}\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(q_{i-1}), \mathop{\mathrm{proj}}_U(q_i))\\ &= \sum_{i=1}^{s}\textstyle \mathop{\mathrm{span}}(G_{\mathop{\mathrm{Aux}}}, \bigcup\mathscr{C}, U, q_{i-1}q_i) \leqslant s\ell \leqslant\ceil{d/2}\ell. \end{align}\] Furthermore, since \(x\in X_4'=B_{\bigcup\mathscr{C}}(Y, \floor{\ell/2})\), \[\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), Y) \leqslant\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), x) + \mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(x, Y) \leqslant\ceil{d/2}\ell + \floor{\ell/2} \leqslant(2\ceil{d/2}+1)\ceil{\ell/2}.\] Since \(X_4=\mathop{\mathrm{pad}}(\bigcup\mathscr{C}, Y, 2\ceil{d/2}+1, \ceil{\ell/2})\), [cor:def-of-pad] implies \(\mathop{\mathrm{dist}}_{\bigcup\mathscr{C}}(\mathop{\mathrm{proj}}_U(v), X_4)\leqslant\ceil{d/2}\). Therefore since \(v\in B_G(V(\bigcup\mathscr{C}), r-d)\), \(v\in B_U(\mathop{\mathrm{proj}}_U(v), r-d)\), thus \(v\in B_{\bigcup\mathscr{C}\cup U}(X_4, r-\floor{d/2})\). Recall that \(v\in V(D)\), thus we have shown that \(D\) has a vertex in \(B_G(X_4, r-\floor{d/2})\). Then by 24 , \(B_G(X, g(d))\cap V(D)\not=\varnothing\), as desired. ◻

[clm:main-hitting] and 23 imply that the theorem holds. ◻

Acknowledgments↩︎

Part of this work was carried out during the following workshops: The Graph Theory Workshop held in January 2025 in Oberwolfach (Germany); the Twelve Annual Workshop on Geometry and Graphs held in February 2025 at the Bellairs Research Institute of McGill University (Barbados); the second Belgian Graph Theory Conference held in July 2025 in Brussels (Belgium); the Thirteenth Annual Workshop on Geometry and Graphs held in February 2026 at the Bellairs Research Institute of McGill University (Barbados); the Focused Workshop on Erdős–Pósa problems held in March 2026 in Będlewo (Poland); and the MATRIX workshop “Global Structure and Geometry of Graphs” held in April 2026 in Creswick (Australia). The authors are thankful to all the organizers and participants for providing a stimulating research environment. The fourth author would also like to thank David Wood for his feedback on the presentation of the paper.

References↩︎

[1]

P. Erdős and L. Pósa, “On independent circuits contained in a graph,” Canadian J. Mathematics, vol. 17, pp. 347–352, 1965, doi: 10.4153/CJM-1965-035-8.

[2]

E. Birmelé, J. A. Bondy, and B. A. Reed, “The Erdős–Pósa property for long circuits,” Combinatorica, vol. 27, no. 2, pp. 135–145, 2007, doi: 10.1007/s00493-007-0047-0.

[3]

S. Fiorini and A. Herinckx, “A tighter Erdős–Pósa function for long cycles,” J. Graph Theory, vol. 77, no. 2, pp. 111–116, 2014, doi: 10.1002/jgt.21776.

[4]

F. Mousset, A. Noever, N. Škorić, and F. Weissenberger, “A tight Erdős–Pósa function for long cycles,” J. Combinatorial Theory, Series B, vol. 125, pp. 21–32, 2017, doi: 10.1016/j.jctb.2017.01.004.

[5]

H. Bruhn, F. Joos, and O. Schaudt, “Long cycles through prescribed vertices have the Erdős–Pósa property,” J. Graph Theory, vol. 87, no. 3, pp. 275–284, 2018, doi: 10.1002/jgt.22156.

[6]

N. Kakimura, K. Kawarabayashi, and D. Marx, “Packing cycles through prescribed vertices,” J. Combinatorial Theory, Series B, vol. 101, no. 5, pp. 378–381, 2011, doi: 10.1016/j.jctb.2011.03.004.

[7]

M. Pontecorvi and P. Wollan, “Disjoint cycles intersecting a set of vertices,” J. Combinatorial Theory, Series B, vol. 102, no. 5, pp. 1134–1141, 2012, doi: 10.1016/j.jctb.2012.05.004.

[8]

F. Joos, “Parity linkage and the Erdős–Pósa property of odd cycles through prescribed vertices in highly connected graphs,” J. Graph Theory, vol. 85, no. 4, pp. 747–758, 2017, doi: 10.1002/jgt.22103.

[9]

N. Kakimura and K. Kawarabayashi, “Packing cycles through prescribed vertices under modularity constraints,” Advances in Applied Mathematics, vol. 49, no. 2, pp. 97–110, 2012, doi: 10.1016/j.aam.2012.03.002.

[10]

I. J. Dejter and V. Neumann-Lara, “Unboundedness for generalized odd cyclic transversality,” in Combinatorics (Eger, 1987), vol. 52, North-Holland, Amsterdam, 1988, pp. 195–203.

[11]

C. Thomassen, “On the presence of disjoint subgraphs of a specified type,” J. Graph Theory, vol. 12, no. 1, pp. 101–111, 1988, doi: 10.1002/jgt.3190120111.

[12]

P. Wollan, “Packing cycles with modularity constraints,” Combinatorica, vol. 31, no. 1, pp. 95–126, 2011, doi: 10.1007/s00493-011-2551-5.

[13]

W. Cames van Batenburg, T. Huynh, G. Joret, and J.-F. Raymond, “A tight Erdős–Pósa function for planar minors,” Advances in Combinatorics, 2019, doi: 10.19086/aic.10807.

[14]

D. Rautenbach and B. Reed, “The Erdős–Pósa property for odd cycles in highly connected graphs,” Combinatorica, vol. 21, no. 2, pp. 267–278, 2001, doi: 10.1007/s004930100024.

[15]

C. Thomassen, “The Erdős–Pósa property for odd cycles in graphs of large connectivity,” Combinatorica, vol. 21, no. 2, pp. 321–333, 2001, doi: 10.1007/s004930100028.

[16]

K. Kawarabayashi and P. Wollan, “Non-zero disjoint cycles in highly connected group labelled graphs,” J. Combinatorial Theory, Series B, vol. 96, no. 2, pp. 296–301, 2006, doi: 10.1016/j.jctb.2005.08.001.

[17]

J. P. Gollin, K. Hendrey, O. Kwon, S. Oum, and Y. Yoo, “A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups,” Mathematische Annalen, pp. 1–53, 2025, doi: 10.1007/s00208-025-03293-5.

[18]

N. Robertson and P. Seymour, “Graph minors. V. Excluding a planar graph,” J. Combinatorial Theory, Series B, vol. 41, no. 1, pp. 92–114, 1986, doi: 10.1016/0095-8956(86)90030-4.

[19]

P. Aboulker, S. Fiorini, T. Huynh, G. Joret, J.-F. Raymond, and I. Sau, “A tight Erdős–Pósa function for wheel minors,” SIAM J. Discrete Mathematics, vol. 32, no. 3, pp. 2302–2312, 2018, doi: 10.1137/17M1153169.

[20]

T. Kloks, C. M. Lee, and J. Liu, “New algorithms for \(k\)-face cover, \(k\)-feedback vertex set, and \(k\)-disjoint cycles on plane and planar graphs,” in Revised papers from the 28th international workshop on graph-theoretic concepts in computer science, 2002, pp. 282–295.

[21]

D. Bienstock and N. Dean, “On obstructions to small face covers in planar graphs,” J. Combinatorial Theory, Series B, vol. 55, no. 2, pp. 163–189, 1992, doi: 10.1016/0095-8956(92)90040-5.

[22]

M. Bonamy et al., “Jones’ conjecture in subcubic graphs,” Electronic J. Combinatorics, vol. 28, no. 4, pp. Paper No. 4.5, 12, 2021, doi: 10.37236/9192.

[23]

F. V. Fomin, S. Saurabh, and D. M. Thilikos, “Strengthening Erdős–Pósa property for minor-closed graph classes,” J. Graph Theory, vol. 66, no. 3, pp. 235–240, 2011, doi: 10.1002/jgt.20503.

[24]

S. Fiorini, G. Joret, and D. R. Wood, “Excluded forest minors and the Erdős–Pósa property,” Combinatorics, Probability and Computing, vol. 22, no. 5, pp. 700–721, 2013, doi: 10.1017/S0963548313000266.

[25]

V. Dujmović, G. Joret, P. Micek, and P. Morin, “Tight bound for the Erdős–Pósa property of tree minors,” Combinatorics, Probability and Computing, vol. 34, no. 2, pp. 321–325, 2025, doi: 10.1017/S0963548324000415.

[26]

D. Chatzidimitriou, J.-F. Raymond, I. Sau, and D. M. Thilikos, “An \(O(\log\) OPT\()\)-approximation for covering and packing minor models of \(\theta_r\),” Algorithmica, vol. 80, no. 4, pp. 1330–1356, 2018, doi: 10.1007/s00453-017-0313-5.

[27]

A. C. Giannopoulou, O. Kwon, J.-F. Raymond, and D. M. Thilikos, “Packing and covering immersion models of planar subcubic graphs,” in Graph-theoretic concepts in computer science, vol. 9941, Springer, Berlin, 2016, pp. 74–84.

[28]

H. Bruhn, M. Heinlein, and F. Joos, “Long cycles have the edge-Erdős–Pósa property,” Combinatorica, vol. 39, no. 1, pp. 1–36, 2019, doi: 10.1007/s00493-017-3669-x.

[29]

W. C. van Batenburg, G. Joret, and A. Ulmer, “Erdős–Pósa from ball packing,” SIAM J. Discrete Mathematics, vol. 34, no. 3, pp. 1609–1619, 2020, doi: 10.1137/19m1309225.

[30]

H. Bruhn, M. Heinlein, and F. Joos, “The edge-Erdős–Pósa property,” Combinatorica, vol. 41, no. 2, pp. 147–173, 2021, doi: 10.1007/s00493-020-4071-7.

[31]

B. Reed, “Mangoes and blueberries,” Combinatorica, vol. 19, no. 2, pp. 267–296, 1999, doi: 10.1007/s004930050056.

[32]

C.-H. Liu, “Packing topological minors half-integrally,” J. London Mathematical Society, vol. 106, no. 3, pp. 2193–2267, 2022, doi: 10.1112/jlms.12633.

[33]

T. Huynh, F. Joos, and P. Wollan, “A unified Erdős–Pósa theorem for constrained cycles,” Combinatorica, vol. 39, no. 1, pp. 91–133, 2019, doi: 10.1007/s00493-017-3683-z.

[34]

J. P. Gollin, K. Hendrey, K. Kawarabayashi, O. Kwon, and S. Oum, “A unified half-integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups,” J. London Mathematical Society, vol. 109, no. 1, p. e12858, 2024, doi: 10.1112/jlms.12858.

[35]

N. Kakimura and K. Kawarabayashi, “Half-integral packing of odd cycles through prescribed vertices,” Combinatorica, vol. 33, no. 5, pp. 549–572, 2013, doi: 10.1007/s00493-013-2865-6.

[36]

V. Dujmović, G. Joret, P. Micek, and P. Morin, arXiv:2412.13893; to appear in the Journal of the London Mathematical Society“Erdős–Pósa property of cycles that are far apart,” 2024.

[37]

J. Ahn, J. P. Gollin, T. Huynh, and O. Kwon, “A coarse Erdős–Pósa theorem,” in Proceedings of the 2025 annual ACM-SIAM symposium on discrete algorithms, SODA 2025, 2025, pp. 3363–3381, doi: 10.1137/1.9781611978322.109.

[38]

J. Ahn, J. P. Gollin, T. Huynh, and O. Kwon, arXiv:2407.05883“A coarse Erdős–Pósa theorem,” 2025.

[39]

E. Birmelé, “Tree-width and circumference of graphs,” J. Graph Theory, vol. 43, no. 1, pp. 24–25, 2003, doi: 10.1002/jgt.10099.

[40]

A. Gyárfás and J. Lehel, “A Helly-type problem in trees,” Combinatorial Theory and its applications, vol. 4, pp. 571–584, 1970, [Online]. Available: https://www.renyi.hu/~gyarfas/Cikkek/02_GyarfasLehel_AHellyTypeProblemInTrees.pdf.

[41]

N. Alon, “Covering a hypergraph of subgraphs,” Discrete Mathematics, vol. 257, no. 2, pp. 249–254, 2002, doi: 10.1016/S0012-365X(02)00427-2.

[42]

M. Distel, U. Giocanti, J. Hodor, C. Legrand-Duchesne, and P. Micek, arXiv:2601.18439“A coarse Gallai theorem,” 2026.

[43]

A. Georgakopoulos and P. Papasoglu, “Graph minors and metric spaces,” Combinatorica, vol. 45, no. 3, 2025, doi: 10.1007/s00493-025-00150-6.

[44]

T. Nguyen, A. Scott, and P. Seymour, arXiv:2508.14332“Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture,” 2025.

[45]

S. Albrechtsen and J. Davies, arXiv:2508.15342“Counterexample to the conjectured coarse grid theorem,” 2025.

[46]

M. Simonovits, “A new proof and generalizations of a theorem of Erdős and Pósa on graphs without \(k+1\) independent circuits,” Acta Mathematica Academiae Scientiarum Hungarica, vol. 18, pp. 191–206, 1967, doi: 10.1007/BF02020974.

Princeton University, Princeton, NJ 08544, USA (mchudnov@math.princeton.edu). Supported by NSF Grants DMS-2348219 and CCF-2505100, AFOSR grant FA9550-25-1-0275, and a Guggenheim Fellowship.↩︎
School of Computer Science and Electrical Engineering, University of Ottawa, Ottawa, Canada (vida.dujmovic@uottawa.ca). Research supported by NSERC and a University of Ottawa Research Chair.↩︎
Département d’Informatique, Université libre de Bruxelles, Belgium (gwenael.joret@ulb.be). G. Joret is supported by the Belgian National Fund for Scientific Research (FNRS).↩︎
School of Mathematics, Monash University, Australia (raj.kaul@monash.edu). Research supported by an Australian Government Research Training Program Scholarship.↩︎
Department of Theoretical Computer Science, Jagiellonian University, Kraków, Poland (piotr.micek@uj.edu.pl). Research supported by the National Science Center of Poland under grant UMO-2023/05/Y/ST6/00079 within the WEAVE-UNISONO program.↩︎
School of Computer Science, Carleton University, Ottawa, Canada (morin@scs.carleton.ca). Research supported by NSERC.↩︎
Mathematical Institute, University of Oxford, Oxford, UK (alexander.scott@maths.ox.ac.uk). Research supported by EPSRC grant EP/X013642/1↩︎
The problem was discussed in March 2024 at the Barbados Graph Theory Workshop held at the Bellairs Research Institute of McGill University.↩︎
Proof. We show that there is no function \(f\) such that [thm:main-in-intro] holds with \(f\) and \(g(d)=d-1\). Assume for a contradiction that there is a function \(f\). Let \(s\mathrel{\vcenter{:}}= f(k,\ell)\). Construct a graph \(G\) as follows: Write \(V(K_{2s+1})=[2s+1]\) and let \(K_{2s+1}^*\) be the graph obtained from \(K_{2s+1}\) by replacing each edge \(ij\) with a path \(P_{ij}\) between \(i\) and \(j\), and of length \(d\). Let \(\set{C_1, \dots, C_{2s+1}}\) be a collection of pairwise vertex-disjoint cycles each of length \(\ell\) such that \(V(C_i)\cap V(K_{2s+1}^*)=\set{i}\) for all \(i\in [2s+1]\). Let \(G\mathrel{\vcenter{:}}= K_{2s+1}^*\cup C_1\cup \cdots \cup C_{2s+1}\). Since \(G-[2s+1]\) is a forest, every cycle in \(G\) has a vertex in \([2s+1]\). Moreover, since distinct \(i,j\in[2s+1]\) have \(\mathop{\mathrm{dist}}_G(i,j)=d\), \(G\) does not have two cycles at distance more than \(d\). Hence \(G\) does not have a \(d\)-packing of \(k\) cycles each of length at least \(\ell\). To reach a contradiction, we now show that for every set \(X\subseteq V(G)\) with \(|X|\leqslant s\), \(G-B_G(X,d-1)\) has a cycle of length at least \(\ell\). Notice that every vertex \(v \in V(G)\) either lies in \(V(C_i)\) for some \(i\in [2s+1]\), or is an inner vertex of \(P_{ij}\) for some \(i,j\in [2s+1]\). Then \(B_G(v,d-1)\) intersects either one or two cycles in \(\set{C_1, \dots, C_{2s+1}}\) since each \(P_{ij}\) has length \(d\). It follows that \(B_G(X, d-1)=\bigcup_{v\in X}B_G(v, d-1)\) intersects at most \(2|X| \leqslant 2s\) cycles in \(\set{C_1, \dots, C_{2s+1}}\), hence missing at least one of them, as required. \(\square\)↩︎
Very recently, a proof of the conjecture by Sandra Albrechtsen, Marthe Bonamy, Romain Bourneuf, and James Davies was announced at the Focused Workshop on Erdős–Pósa problems held in March 2026 in Będlewo, Poland.↩︎
Here and throughout, \(\log x\) denotes the base-\(2\) logarithm of \(x\).↩︎

FAR-APART ERDŐS–PÓSA PROPERTY OF LONG CYCLES

Abstract

1 Introduction↩︎

1.1 Far-Apart Erdős–Pósa Property of Cycles↩︎

1.2 Coarse Motivations↩︎

2 Tools↩︎

3 Proof of the Main Result↩︎

Acknowledgments↩︎

References↩︎

Subjects

Updated on Academus