A linear list-coloring bound in terms of the Hadwiger number

Proof. A coloring from the common list \{1,\ldots,\ell(G)\} shows that \chi(G)\le\ell(G).□

Proof. Start with a stable-set distribution having inclusion probabilities at least 1/r. Conditional independent deletion of each included vertex reduces every marginal to exactly 1/r and preserves stability. Put M=\lceil n/r\rceil. Partition each resulting stable set I into parts of size at most M, assigning its probability mass to each part. This gives a finite measure of total mass at most

Every vertex still has mass 1/r. Add mass on the empty set to make the total exactly two and divide by two.□

Proof. Expose the variables in order. The martingale of conditional expectations has differences of conditional mean zero and absolute value at most b. Convexity bounds the conditional exponential moment of a difference at \lambda by \cosh(\lambda b)\le\exp(\lambda^2b^2/2). Multiplying these bounds and applying Markov’s inequality with \lambda=u/(sb^2) gives the upper tail. Apply the same argument to -Z and add the two bounds.□

Proof. For every set R of at most s vertices, put B_R=\bigcup_{v\in R}N_P(v). Whenever both B_R and its complement have size at least k/3, fix a matching of size \lfloor k/8\rfloor across this cut. Such a matching exists: otherwise the endpoints of a maximal smaller matching form a vertex cover of the crossing edges, of size less than k/4. Both sides remain nonempty after their removal, contradicting k-connectivity. The number of possible sets R, and hence of matchings, is at most (n+1)^{s+1}.

The neighborhood assumption ensures that P-U has more than \lfloor k/32\rfloor vertices. If it fails the asserted connectivity, there are a set Z\subseteq V(P)\setminus U with |Z|<k/32 and nonempty anticomplete sides A,A' partitioning V(P)\setminus(U\cup Z). Every vertex of either side has more than k/3 neighbors in that same side, since it has at least k/2 neighbors outside U and loses fewer than k/32 to Z. In particular both sides have size at least k/3.

Make s independent uniform draws from A. For each vertex v\in A, the probability that none of the draws is an open neighbor of v is at most \exp(-ks/(3n)). The union bound over A is less than one by the choice of s. Thus the set R of drawn vertices, after repetitions are removed, satisfies A\subseteq B_R. Since A,A' are anticomplete, A'\cap B_R=\varnothing. The matching fixed for this cut has every edge incident with U\cup Z, for otherwise an edge would join A to A'. But U contains fewer than k/32 of its endpoints, and Z contains fewer than k/32 vertices. They cannot cover its \lfloor k/8\rfloor disjoint edges. This contradiction proves the lemma.□

Proof. Changing one sampled stable set changes W_i on at most 2M vertices. It changes a union of remainders on at most the same number of vertices. Adding or deleting a vertex changes fractional chromatic number by at most one, so all the quantities in the statement have bounded differences at most 2M per trial.

For sufficiently large t, r\log(2y)\ge1, and hence N\le(B+1)r\log(2y). With A_0=4Q_0(B+1), we obtain

Lemma 2.5 therefore gives

Since 1\le y\le\log t, the exponent in the last line has magnitude at least t^{7/10} for all sufficiently large t. The cutoff depends only on \delta and the fixed constants. Independence between different vertices is not used.□

Proof. Build a binary decomposition of P, making all choices before sampling. A node is an induced subgraph. Stop at a node of order at most 2k, and also at a larger node which is k-connected. Otherwise choose a separator of size less than k, partition the vertices outside it into two nonempty anticomplete sides, and form two children by adding the separator to each side.

There are O(n^2+1) nodes. To see this, give a node of order u>2k potential u-k. Each large child’s potential is strictly smaller than its parent’s, since the other exclusive side is nonempty. If both children are large, their potentials sum to at most their parent’s: their orders sum to u+|S|<u+k, where S is the separator. If just one child is large, its potential alone is at most the parent’s. Thus at each depth the sum of the large-node potentials is at most n, while the depth of a large-node branch is at most n. The small leaves contribute at most two children per large node, in addition to a possible small root.

Every separator and every small leaf has order at most 2k. Its expected intersection size with W is at most 2kp\le r/1000. Lemma 3.3 and a union bound over the decomposition show that, with probability 1-o(1), all these intersections have fewer than r/100 vertices. If every k-connected leaf had expected fractional chromatic number at most r/4 after restriction to W, the same lemma would give, again with probability 1-o(1), fractional chromatic number less than 3r/10 in every such leaf. A small leaf has this latter bound as well, since its fractional chromatic number is at most its order.

Fix an outcome satisfying all these conclusions. Write F=P[W]. The assumption of the lemma gives f(F)>r/2, whereas every leaf restriction has fractional chromatic number less than 3r/10. We compare these bounds by replacing every vertex of F with a clique of the same large order. Ordinary-chromatic connectivity extraction in this larger graph will produce a subgraph of large chromatic number that cannot cross any of the blown-up separators. It must lie in one blown-up leaf, giving the contradiction.

For a positive integer m, form F^{(m)} by replacing each vertex of F with a clique of order m, and replacing each edge with a complete join between its two replacement cliques. Every color class of F^{(m)} projects to a stable set of F and uses at most one vertex of each replacement clique. Dividing the multiplicities of these projected stable sets by m therefore gives a fractional coloring of F. Consequently

For each leaf restriction, choose a fractional coloring of weight less than 3r/10. Round its finitely many stable-set weights up to multiples of 1/m. Give a distinct color slot to each unit of weight 1/m. Every original vertex belongs to at least m slots, so its m copies can be assigned distinct slots containing that vertex. A slot is a stable set upstairs: it contains at most one copy of any original vertex, and its original vertices form a stable set. The rounding adds only a bounded number of slots, independent of m for this fixed leaf. There are finitely many leaves, so for all sufficiently large m, every blown-up leaf restriction has a coloring with fewer than 31mr/100 colors.

Apply Theorem 2.2 to F^{(m)} with the integer parameter k'=\lceil mr/50\rceil. For sufficiently large m, (13) exceeds 7k'. We obtain a k'-connected subgraph J with

Each restricted separator of the decomposition has fewer than r/100 vertices, so its blow-up has fewer than mr/100<k' vertices. Thus J cannot meet both exclusive sides of any such split: deleting its vertices in the separator would disconnect J with fewer than k' deletions. Nor can J be contained in the separator, because its order is greater than k'. Descending the decomposition places J inside a single blown-up leaf restriction, contradicting that leaf’s coloring bound.

It follows that some k-connected leaf satisfies (12). This argument also covers the case where P is too small to be k-connected: if all leaves were small, the same contradiction would apply. Finally, the blow-up is only an auxiliary graph for the extraction theorem, which requires no minor exclusion; no bound on its clique-minor number was used.□

Proof. By (12) and Lemma 3.3, the events

all hold with probability 1-o(1): the individual failure probability is at most 2\exp(-t^{7/10}), and q\le Q_0(\log t)^2.

For each outcome of W_i satisfying \mathcal A_i, choose optimal dual weights on H[W_i\cap V(H)] of total weight a_i>r/5. Choose these weights as a function of W_i alone. Conditional on this one copy, each other copy still satisfies the vertex survival bound (9). Therefore the expected weight on vertices belonging to some other copy is at most (q-1)pa_i. Markov’s inequality shows that the probability of \mathcal A_i together with the loss of more than a_i/4 is at most 4(q-1)p.

Taking a union bound over i, we conclude that, except with probability 4q(q-1)p+o(1), all private sets retain weight at least 3a_i/4>3r/20>r/8. Restriction to T_i preserves dual feasibility: each stable set in H[T_i] is also a stable set in H[W_i\cap V(H)]. Hence f(H[T_i])>r/8. In this calculation we have conditioned only on a single copy at a time, not on the simultaneous events \mathcal A_1,\ldots,\mathcal A_q.

Theorem 2.1 now gives

so each private set contains the required model. The models are vertex-disjoint because the private sets are disjoint.□

Proof. Each fixed vertex belongs to U with probability at most qp\le10^{-4} by (10). Before sampling, fix k neighbors of each vertex of H, possible since H is k-connected. The expected number of those neighbors in U is at most k/10000. Having at least k/2 of them in U thus requires a deviation greater than k/3\ge r/3. Lemma 3.3 and a union bound over at most n vertices prove the neighborhood assertion with probability 1-o(1). This assertion holds for all vertices of H, including those in U.

For the connectivity assertion, use the family of test matchings in Lemma 2.6 for the fixed graph H, with order bound n and connectivity parameter k. Fix this family before sampling the fresh copies, and set

The number of tests is at most

Here the constants are absolute, since D_0 is fixed.

The endpoint set of each test matching is a fixed set to which Lemma 3.3 applies. It has size at most k/4, so its expected intersection size with U is at most k/40000. A count of at least k/32 therefore requires a deviation greater than k/64\ge r/64. Lemma 3.3 and the displayed bound on the number of tests show that, with probability 1-o(1), every test matching has fewer than k/32 endpoints in U. Together with the neighborhood assertion, these are the hypotheses of Lemma 2.6, which gives the claimed connectivity.□

Proof of Lemma 3.2. If P is empty, take all the stable sets empty. Otherwise use the experiment (8) and suppose that every outcome of positive probability has f(P[W])>r/2. Lemma 3.4 supplies a fixed H. By (10), the failure probability in Lemma 3.5 is at most 4\cdot10^{-4}+o(1). Thus Lemmas 3.5 and 3.6 hold simultaneously with positive probability for sufficiently large t. Fix such an outcome, including its q disjoint K_{2x} models.

Partition the t labels of a prospective K_t model into b=\lceil t/x\rceil nonempty blocks of size at most x. Assign a different private model to each single block and each unordered pair of distinct blocks. There are b+\binom b2=b(b+1)/2\le b^2=q assignments. In a model assigned to one block, retain one bag for each label of that block. In a model assigned to two blocks, retain one bag for each label in their union. At most 2x bags are retained from each model, and every pair of distinct labels appears together in one assigned model.

Choose a port vertex in every retained bag. There are at most 2xq ports, and each has at least k/2 neighbors in H-U. By (7), we can choose a distinct such neighbor for every port, greedily. Let m be the actual number of chosen neighbors, so 1\le m\le2xq. Their labels partition them into t nonempty groups. The graph H-U has connectivity at least

so Theorem 2.3 provides pairwise disjoint connected sets in H-U containing these groups.

For each label, unite its connected set in H-U with all its assigned private bags and their port edges. This set is nonempty and connected. Different labels give disjoint sets: their connected sets in H-U are disjoint, all private bags are disjoint, and the bags lie in U. Every two label sets are adjacent because their labels occur together in an assigned clique model. These sets form a K_t model in P, contrary to h(P)<t. Some outcome of the sampling experiment must therefore have fractional chromatic number at most r/2, as required.□

Proof of Proposition 3.1. Fix a sufficiently large integer t, and let G satisfy the hypotheses of the proposition. The empty graph needs no colors, so suppose that G is nonempty. Set

and let J be the largest nonnegative integer for which r_J\ge t/\log t. For each j\in\{0,\ldots,J\}, allocate a separate block of

bins. Allocate a further 16t bins for cleanup. All these bins are distinct. Their total number n_{\mathrm{bin}} is at most a fixed constant times t. Indeed, y_j\le2^j, so

Also J+1=O(\log\log t), since 2^J\le4\log t. Choose an integer

For all sufficiently large t, we have n_{\mathrm{bin}}\le D_{\mathrm{bin}}t. Finally choose a positive integer L such that

Let \mathcal L be any finite list assignment on G with |\mathcal L(v)|\ge Lt at every vertex. Map each color in the finite union \bigcup_v\mathcal L(v) independently and uniformly to one of the n_{\mathrm{bin}} bins. We claim that a map can be fixed such that every vertex has an allowable color in at least half the bins of every block, including cleanup.

For a fixed vertex and a block of u bins, failure of this property implies that a subset of \lceil u/2\rceil bins is missed by its list. For a specified such subset, the probability of being missed is at most

There are at most 2^u choices for the missed subset, so (14) bounds the failure probability by e^{-u}. Every nonfinal block has u\ge B(\log2)t/\log t, and the cleanup block has u=16t. Thus, with c_B=\min\{B\log2,16\}>0 and \log t\ge1, a union bound over all vertices and blocks gives failure probability at most

For sufficiently large t, the desired map therefore exists; fix one. This probability estimate depends on the list sizes, but not on the number of distinct colors in their union.

Call a vertex eligible for a bin if its list has a color assigned to that bin. It remains eligible whenever it survives to a later stage. At the start, Theorem 2.1 gives f(G)\le4t=r_0. At stage j, let P be the current induced remainder. If it is empty, stop. Otherwise h(P)<t, |V(P)|\le t^{11/10}, and inductively f(P)\le r_j. For each bin of that stage, take its eligible vertex set inside P. Every vertex belongs to at least half these sets. Lemma 3.2, with n=t^{11/10}, supplies a stable set for each bin such that deleting the eligible covered vertices leaves fractional chromatic number at most r_j/2=r_{j+1}. Retain one covering bin for every vertex removed at this stage.

After stage J, the remaining graph has fractional chromatic number at most r_{J+1}<t/\log t. If it is nonempty, put \rho=t/\log t and independently sample a stable set in each cleanup bin from a fractional coloring distribution having every vertex inclusion probability at least 1/\rho. Such a distribution exists because f\le\rho. Every remaining vertex is eligible in at least 8t cleanup bins, so its probability of being missed by all eligible samples is at most

The probability that any remaining vertex is missed is therefore at most t^{11/10}t^{-8}=t^{-69/10}<1. Choose an outcome covering every remaining vertex and again retain one covering bin for each vertex.

Every vertex now has a retained bin and belongs to the stable set associated with that bin. Choose any color in its original list which maps to that bin. If two vertices receive the same color, the global map sends that color to their common retained bin. Both vertices lie in that bin’s stable set and are therefore nonadjacent. This is a proper \mathcal L-coloring of G.

The choices of constants were made in the order \gamma, B, D_{\mathrm{bin}}, and L. All subsequent cutoffs depend only on these constants, and every thinning estimate is uniform over the intermediate graphs and eligibility sets. Enlarging one absolute t_0 to satisfy the finitely many cutoff requirements proves the proposition.□

Proof. For the first assertion, extend any list assignment on H with lists of size at least \ell(P) to the other vertices of P, retaining the given lists on V(H). A list coloring of P restricts to one of H; additional edges among V(H) cause no difficulty.

For the second assertion, write s=\ell(P-Z) and give every vertex of P a list of size at least s+|Z|. Greedily color P[Z]. At any such step there are at most |Z|-1 colors to avoid. Delete from each remaining list the colors used on its neighbors in Z. At most |Z| entries are removed, so P-Z can be colored from the remaining lists. This proves \ell(P)\le s+|Z|; the empty-graph cases hold as well under our convention.

For the third assertion, repeatedly remove a vertex of degree at most q from the current graph. In the reverse order, every vertex has at most q already colored neighbors, so lists of size at least q+1 suffice.□

Proof. We induct on |V(P)|. The hypothesis about induced k-connected subgraphs is inherited by induced subgraphs of P. The budget gives |A|\le2k.

If |V(P)|\le2k, extend \varphi greedily. At each vertex there are at most 2k-1 colors used by already colored vertices and at most k-1 forbidden colors. Since the lists have size at least m+6k, a choice is available. This includes the empty graph.

If P is k-connected, then \ell(P)\le m by hypothesis. For every v\notin A, remove B_v and the colors on its precolored neighbors from \mathcal L(v). The remaining list has size at least

By Lemma 4.1, \ell(P-A)\le m, so these lists color P-A. Combining this coloring with \varphi proves the assertion in this case. If P-A is empty there is nothing to extend.

It remains to consider |V(P)|>2k when P is not k-connected. Choose a partition

where V_1,V_2 are nonempty, there are no edges between them, and |Z|<k. Assign to each vertex its constraint cost

Interchange the sides if necessary so that w(V_1)\ge w(V_2). We color the side with the larger constraint cost first, leaving the other side to absorb the cost of precoloring the whole separator. In particular,

We first color P_1=P[V_1\cup Z]. Retain the precoloring on A_1=A\cap(V_1\cup Z). At its other vertices use forbidden sets

These extra prohibitions make the eventual separator coloring compatible with the precolored vertices on the other side. Their total cost obeys

Repeated occurrences of the same color can only reduce the left side.

The sets B'_v need not all have size less than k, but each satisfies

We now convert every vertex with |B'_v|\ge k into a precolored vertex. Process these vertices one at a time. Choose a color from \mathcal L(v) avoiding B'_v and all colors on its currently precolored neighbors in P_1, and then discard the forbidden set at this newly precolored vertex. Its contribution to the constraint cost changes from |B'_v| to k, so the total cost does not increase. In particular, throughout this procedure there are at most 2k precolored vertices. Each choice therefore avoids at most

colors and is possible. Every promoted vertex lies in Z\setminus A, since the original forbidden sets on V_1\setminus A had size less than k. Its chosen color also avoids all precolored neighbors in V_2, by the definition of B'_v.

After the conversions, the constraints on P_1 satisfy all the hypotheses of the lemma: its precoloring is proper, its remaining forbidden sets have size less than k, and its total cost is at most 2k^2. Since V_2 is nonempty, |V(P_1)|<|V(P)|, and induction supplies a coloring \psi_1 of P_1. It respects all the original constraints in P_1. It also avoids every color \varphi(x) at a separator neighbor of x\in A\cap V_2: this was enforced either by an original precoloring, by a conversion, or by a retained forbidden set.

Next consider P_2=P[V_2\cup Z]. Precolor Z according to \psi_1 and retain \varphi on A\cap V_2. The resulting precoloring on Z\cup(A\cap V_2) is proper by the preceding compatibility property. For each vertex of V_2\setminus A, retain its original forbidden set B_v. The new constraint cost is

using (16). All its remaining forbidden sets have size less than k. Since V_1 is nonempty, induction applies to P_2. Its coloring agrees with \psi_1 on Z. The two colorings therefore combine into a proper coloring of P, because there are no edges between V_1 and V_2. They extend the original precoloring and respect every original forbidden set.□

Proof. Suppose otherwise and put m=\ell(P)-6k-1, a nonnegative integer. Every induced k-connected subgraph then has list chromatic number at most m. Apply Lemma 4.2 with no precolored vertices and no forbidden colors. It says that every list assignment of size at least m+6k=\ell(P)-1 is colorable, contradicting the definition of \ell(P).□

Proof. Process the indicated outside vertices in any order. Assign each one an as yet unused unordered pair of its neighbors in X. Suppose this fails when processing a vertex v. Choose t distinct vertices in N_P(v)\cap X. Every pair of the chosen vertices has already been assigned to a different previously processed outside vertex adjacent to both. The corresponding paths of length two have mutually distinct internal vertices, all outside X. They form a subdivision of K_t and hence give a K_t minor, a contradiction. Thus the assignment never fails and is an injection into the unordered pairs from X.□

Proof. Write R=P-X-Y and s=\ell(R), and set

We show that P is u-choosable. Given any lists of size at least u, first restrict each list to exactly u entries. Denote the resulting assignment by \mathcal L. Its total palette \mathcal C=\bigcup_{v\in V(P)}\mathcal L(v) is finite, but its size is otherwise unrestricted.

Independently for each color in \mathcal C, reserve that color with probability

Since u\ge(4L+d+5)t>2Lt, this is a probability strictly between zero and one. Reservation is global: all occurrences of a color are reserved together. For each vertex v, the number Z_v of reserved entries in \mathcal L(v) has distribution \operatorname{Bin}(u,p) and mean \mu=2Lt. This mean is independent of s, and overlaps between different lists do not affect this marginal distribution.

For completeness, for every real \lambda its exponential moment obeys

Markov’s inequality with \lambda=-\log2 and \lambda=\log2, respectively, gives

Let

By Lemma 4.4, |T|\le\binom{|X|}{2}. Put \eta=\min\{(1-\log2)/2,\,2\log2-1\}>0. A union bound using (18) and (19) shows that the probability of either of the failures

is at most

for sufficiently large t. There are only polynomially many tested vertices even if P has arbitrarily many vertices. No independence between different vertices’ failure events is required. Fix a reservation for which neither failure occurs.

Use the reserved entries to color P[X]. They provide at least Lt colors at each of its vertices, and Proposition 3.1 applies because |X|\le t^{11/10} and h(P[X])<t. If X is empty this step is vacuous. Write the coloring as \varphi_X.

For each vertex v\notin X, delete from its list the colors on its neighbors in X:

If v\in T, every deleted entry is reserved, so at most 4Lt entries are deleted. If v\notin T, fewer than t entries are deleted because v has fewer than t neighbors in X. In particular, the uniform bound

holds. We have removed only colors actually used on neighbors in X; there is no need to discard all reserved entries at the other vertices.

The bound in (20) is at least dt+1. By Lemma 4.1, the dt-degenerate graph P[Y] therefore has a coloring \varphi_Y from these lists. This coloring has no conflict with \varphi_X.

Finally, at each vertex of R delete from \mathcal L_1(v) the colors used by its neighbors in Y. There are at most dt such neighbors, so its resulting list has size at least

The definition of s=\ell(R) supplies a coloring of R from these lists, with nothing to do if R is empty. The three colorings combine properly, since both pruning steps excluded colors used on neighbors in the previously colored parts. We have colored every u-list assignment on P, proving

Only the fixed cutoff in Proposition 3.1 and the last exponential-versus-polynomial estimate impose a sufficiently-large-t requirement. Neither depends on the graph order or palette size.□

Proof. Choose a nonempty minor R of P whose density d is as large as possible. If d<10^4, the claimed density estimate holds with C_*=10^4. We may therefore assume d\ge10^4. Put n=|V(R)|. The graph R has no isolated vertex, since deleting one would increase its positive density. Contracting an edge xy with c_{xy} common neighbors loses exactly 1+c_{xy} edges. The maximality of d gives

There is a vertex v of degree at most 2d. Therefore J=R[N_R(v)] has at most 2d vertices and minimum degree at least d-1.

We first record a bound for connected dominating sets in any connected graph C of order at most 2d and minimum degree at least d/2. Take

independent uniform samples from V(C). A fixed vertex has a neighbor in each draw with probability at least 1/4, so the probability that some vertex has no sampled neighbor is at most

Consequently, some choice of at most m sampled vertices dominates C. The diameter of C is at most 11: along a shortest path, the open neighborhoods of the vertices at positions 0,3,6,\ldots are pairwise disjoint, each has at least d/2 vertices, and the graph has at most 2d vertices. There are at most four such positions. Joining each sampled vertex to one fixed sampled vertex along a shortest path therefore gives a connected dominating set of size at most 11m\le66\log(2d), which is at most

We have M\le101\log(2d) and d\ge6M. For the latter inequality, x/\log(2x) is increasing for x\ge10^4, and 10^4>606\log(20000).

We now construct

pairwise adjacent, disjoint connected sets. Start with J_0=J. At step i, choose a component C_i of J_i, take a connected dominating set B_i of C_i of size at most M, and put J_{i+1}=C_i-B_i. For every retained vertex, passing to a component deletes no neighbor. Its neighbors in the original graph J that have disappeared are therefore all in previously chosen bags. As long as at most qM\le d/3 bag vertices have been deleted, each retained vertex has degree at least

In particular, each chosen component has at least d/2+1 vertices, whereas M\le d/6; its deletion of B_i leaves a nonempty graph. The construction consequently continues for all q steps.

Every later bag lies inside C_i-B_i, so it has an edge to B_i by domination. The bags form a K_q model. Since d/(3M)\ge2,

The hypothesis h(P)<t implies d/\log(2d)<606t. The elementary inequality \log(2d)\le2\sqrt d for d\ge1 first gives d<(1212t)^2. Since 2\cdot1212^2<2^{22} and t\ge2,

It follows that d<7272t\log(2t). Together with the case d<10^4 and the inequality d(P)\le d, this proves the density claim with C_*=10^4.

Every nonempty subgraph of P has average degree at most 2C_*t\log(2t), and hence has a vertex of degree at most \lfloor2C_*t\log(2t)\rfloor. Successively deleting such vertices and coloring in the reverse order proves the asserted list-coloring bound. The empty graph causes no exception.□

Proof. Choose a fixed positive even integer s with \epsilon s/2>4, and put B_*=2s. We first show that, in any graph without a K_t minor, every set U of size b\ge B_*t contains a vertex with at least t^{-\epsilon}b nonneighbors in U distinct from itself. Suppose otherwise, and set \delta=t^{-\epsilon}. Sample an ordered sequence of st distinct vertices of U uniformly, and divide its positions into t batches of size s.

After any previously exposed sampled positions have been fixed, a further position is uniform among at least b-st\ge b/2 remaining vertices. For any already exposed vertex, the conditional probability that this new vertex is a nonneighbor is consequently at most 2\delta. Consider a fixed nontrivial cut of one batch. Expose a fixed position on its smaller side first, and then the positions on its larger side. If the cut has no crossing edge, at least s/2 successive exposures must all be nonneighbors of the first vertex. The probability is at most (2\delta)^{s/2}. Taking the union over at most 2^s cuts, the probability that the batch is disconnected is at most 2^s(2\delta)^{s/2}. For two fixed batches to be anticomplete, every position of the second batch must be a nonneighbor of one fixed position of the first; this has probability at most (2\delta)^s. Thus the probability that some batch is disconnected or some two batches are anticomplete is at most

For large t, the batches can therefore be chosen connected and pairwise adjacent, giving a K_t model. This contradiction proves the claim.

Let T_0 consist of the vertices appearing in the sum in (21). If A or T_0 is empty, there is nothing to prove. Otherwise, delete all vertices outside A\cup T_0 and all edges with both ends in T_0. Process the vertices of T_0 one at a time. Throughout the procedure, the vertices representing A carry a graph that only gains edges. Each unprocessed vertex retains precisely its original neighborhood in A, because there were no edges between vertices of T_0.

For an unprocessed vertex v, put b_v=|N_P(v)\cap A|. Apply the preceding claim to its neighborhood in the current graph on A, which is a subgraph of a minor of P. Choose there a vertex with at least t^{-\epsilon}b_v missing neighbors in that neighborhood, and contract v onto this vertex. This operation adds at least t^{-\epsilon}b_v new edges to the graph on A. After all vertices have been processed, the resulting graph on A is a minor of P. By Lemma 5.1,

For sufficiently large t, C_*\log(2t)\le t^\epsilon, proving (21). Dividing by B_*t, and then using B_*\ge1, proves the last assertion.□

Proof. Choose an induced subgraph H of smallest order v\ge2k such that

Such a subgraph exists: the given graph has density greater than 2k and, being simple, has more than 4k+1 vertices. The equality v=2k is impossible because \binom{2k}{2}<2k^2. Deleting any one vertex therefore leaves at least 2k vertices, and minimality implies

for every x\in V(H).

Suppose that H is not k-connected. There is a separator Z of size z<k and nonempty anticomplete sides A,B partitioning V(H)\setminus Z. Every neighbor of a vertex of A lies in A\cup Z, and likewise for B. Both H[A\cup Z] and H[B\cup Z] therefore have at least 2k vertices and are proper induced subgraphs of H. Their minimality bounds give

a contradiction. Thus H is k-connected.□

Proof. Choose an integer D_K satisfying the displayed inequality, and keep it fixed. Write n=|V(P)|. Delete edges to obtain a spanning subgraph P_0 with exactly dn edges, where d=D_Kt. This is possible because D_Ktn is an integer. Restoring deleted edges at the end preserves the connectivity of any induced subgraph. Put

We take t large enough that p_0\ge2.

We will find a small dense subgraph on vertices untouched by the contractions. First we contract a maximum family of connected p_0-vertex sets within an edge-loss budget. We then retain untouched vertices whose degrees have not fallen too far. A second maximal choice of a connected set will stop before reaching p_0, since reaching that order would enlarge the first family. The failure of its one-vertex extensions will force a dense neighborhood, even after the contracted vertices are removed.

Choose a family \mathcal C of as many pairwise disjoint connected vertex sets of P_0, each of size p_0, as possible subject to

Here P_0/\mathcal C denotes the simple graph obtained by contracting each set in the family and suppressing loops and parallel edges. The empty family is allowed, so a maximum exists. Let R=P_0/\mathcal C, and let X be the set of contracted vertices. The vertices outside X are identified with their original vertices in P_0, and edges between two such vertices are unchanged. We have

Indeed the total vertex loss in the contractions is at most n, so (22) gives the lower edge bound.

Let B be the union of the following three sets:

The first exclusion ensures that the vertices retained below are original vertices. The second limits how many neighbors a retained vertex can lose when X is removed from the eventual neighborhood. The third bounds the order of that neighborhood by bounding the degrees of the vertices that define it. Since \lambda/4=D_Kt/400\ge B_*t, Lemma 5.2 bounds the second set by t^{2\epsilon}|X|. The degree sum and (23) bound the third set by 2n/t^{4\epsilon}. For sufficiently large t, p_0\ge t^{5\epsilon}/2, and hence

By Lemma 5.1, the number of edges within B is at most

To bound the edges from B to its complement, first count the vertices outside B with fewer than B_*t neighbors in B: their contribution is at most B_*tn. Lemma 5.2 bounds all remaining crossing edges by

The same bounds hold if B is empty. It follows that

for sufficiently large t, since D_K>400B_*.

Starting with R-B, repeatedly delete a vertex v whose degree in the current graph is less than d/4, or less than \deg_R(v)/8. Charge each deleted edge to the endpoint deleted first. The total charge is at most

The process cannot delete every vertex, because R-B initially has more than dn/2 edges. The surviving nonempty set S satisfies

The second degree bound will let us compare a neighborhood in R with the part remaining in S, once the loss caused by contracting its defining set is controlled.

For a nonempty connected vertex set U in R, let \mathcal L(U) be the number of edges lost when U is contracted to one vertex. If N_R(U) denotes its external neighborhood, then the exact loss is

The first term counts the internal edges that become loops. At each outside neighbor, all but one of its edges into U become parallel edges and are suppressed, giving the second term.

Choose a connected set H\subseteq S of largest possible order u\le p_0 subject to

A singleton is admissible. We have u<p_0. Indeed H contains only untouched original vertices, so it is connected in P_0 as well. If u=p_0, append it to \mathcal C. Contracting the old family and then H gives the same graph as contracting the enlarged family. The actual edge losses add, as do the vertex losses; combining (22) and (27) would make this a larger admissible family, a contradiction.

Write N=N_R(H), and put

We first show that at least one sixteenth of N lies in S. By (26),

By (25), a\ge du/4=25\lambda u and a\ge b/8. As |N|\le b, this gives

In particular N\cap S is nonempty, since a\ge25\lambda u>0.

Fix w\in N\cap S, and contract H to a vertex h. Contracting the edge hw next loses exactly

edges: the common neighbors of h and w are precisely N_R(w)\cap N. If this loss were at most \lambda, the connected set H\cup\{w\}, whose order is at most p_0, would satisfy the budget \mathcal L(H\cup\{w\})\le\lambda u. This would contradict the maximality of u. Thus w has more than \lambda-1 neighbors in N. Since w\in S is not in B, it has fewer than \lambda/4 neighbors in X. For \lambda\ge4, it follows that

Using N\cap S\subseteq N\setminus X and (28), we obtain

Consequently,

Every vertex of H\subseteq S has degree less than dt^{4\epsilon} in R. Therefore

Since D_K is fixed, this is at most t^{1.06} once t^{3\epsilon}\ge D_K. Also,

Lemma 5.3, applied to R[N\setminus X], now gives an induced (Kt)-connected subgraph of order at most t^{1.06}. All vertices in N\setminus X are untouched original vertices, and the edges between them in R are exactly their edges in P_0. Restoring the deleted edges on the same vertex set gives the required induced subgraph of P.□

Proof. If every nonempty subgraph had a vertex of degree at most 2D_Kt+1, reverse deletion order would color arbitrary lists of size 2D_Kt+2. Thus some subgraph has minimum degree at least 2D_Kt+2. Passing to the induced subgraph on its vertices preserves this degree bound, so that induced subgraph has density at least D_Kt+1. Apply Lemma 5.4 there.□

Proof. Replace each vertex v by two vertices v^-,v^+ and an arc v^-v^+ of capacity one. For each edge uv, add arcs u^+v^- and v^+u^-, both of capacity j. Add a source s with arcs sa^- of capacity j for a\in A, and a sink z with arcs b^+z of capacity j for b\in B.

Start with zero flow. Whenever the residual directed graph has an s–z path, augment by one unit along it. Residual capacities remain integral. Stop upon reaching value j, or if no residual s–z path exists. In the latter case let R be the vertices reachable from s in the residual graph. Every original arc from R to its complement is saturated, and every original arc entering R from its complement has zero flow. Flow conservation therefore shows that the capacity of the outgoing cut equals the current flow value.

If this value is less than j, no capacity-j arc crosses the cut. Its outgoing arcs are consequently unit arcs v^-v^+, for a set X of fewer than j original vertices. Any A–B path in P-X would give an s–z path avoiding those cut arcs, which is impossible. This contradicts the hypothesis. Thus an integral flow of value j is reached.

Decompose that flow into unit s–z paths and directed cycles, and discard the cycles. Each original vertex is used by at most one of the unit paths because its unit arc has capacity one. The corresponding paths in P are therefore vertex-disjoint. On each such path, take its first visit to B and its last preceding visit to A, and retain the segment between them. This gives the asserted endpoint convention without changing the number or disjointness of the paths.□

Proof. Replace each vertex of A by two copies. For every original edge, join all copies of one endpoint to all copies of the other, treating a vertex outside A as having a single copy. Write A^* for the 2r source copies. The target set B is unchanged.

Let X^* be a set of fewer than 2r vertices of this new graph. At least one source copy and at least one target survive. In the original graph delete the set X of vertices all of whose copies were deleted. Then |X|\le |X^*|<2r, so the surviving original source and target are connected in P-X. A simple path between them lifts to a path in the copy graph minus X^* by choosing a surviving copy at each vertex. Thus X^* cannot separate A^* from B.

Lemma 6.1 now gives 2r vertex-disjoint paths from A^* to B. Every source copy is an endpoint of one path, so no source copy is internal to another path. Identifying the two copies of each source therefore introduces exactly the permitted common starts and no other overlaps. The endpoint convention in Lemma 6.1 also excludes internal vertices in B.□

Proof. We use two successive path packings. The first sends two paths from each root towards the given clique model and leaves some model bags untouched. Its path–bag unions may overlap, but each vertex lies in at most two of them. This bound will certify a second packing to untouched bags, producing the disjoint rooted model.

Let R be the prescribed root set. Start with 4k disjoint bags of a clique model. At most k of these bags meet R, so choose 3k bags disjoint from R and call them eligible. Choose one representative in each eligible bag. Lemma 6.2, applied to these representatives as targets, gives two paths from each root, with their 2k ends in distinct eligible bags.

Among all such double systems, now allowing arbitrary endpoints within the eligible bags but still requiring distinct end bags, choose one of minimum total length. No path meets an eligible bag that is not an end bag of the system: its first such visit would allow that path to be truncated and assigned the unused bag, strictly reducing total length. Consequently at least k eligible bags are untouched by every path. Choose k of them and contract each to a single target vertex; let T be the resulting set of k targets.

For each of the 2k paths of the double system, take its union with its own end bag. These 2k connected sets are unchanged by the contractions just made. Every vertex belongs to at most two of them. Indeed, a vertex outside R belongs to at most one path and at most one eligible bag, whereas a root belongs to its two paths and to no eligible bag. Paths may pass through other used end bags; this observation already allows for those intersections.

In the contracted graph, delete fewer than k vertices. They meet fewer than 2k of the connected sets just described, so at least one such set survives intact, including its root. At least one vertex of T also survives. The surviving set has an edge to every surviving vertex of T, because its end bag was adjacent to every one of the contracted eligible bags. Hence these deletions cannot separate R from T.

Apply Lemma 6.1 with j=k. All k roots and all k targets are used as endpoints, and none is internal on another path. Expand each contracted target bag and add to it the vertices of its root-to-target path. The resulting bags are connected and disjoint. They remain pairwise adjacent through the original edges between the target bags, and each contains its assigned root.□

Proof. The pairs (x_i,y_i) are admissible in Definition 6.4: their endpoint sets are disjoint across paths, and a path meeting J only once gives a permitted coincident pair. Apply wovenness to all these pairs. On each path meeting J, replace the entire segment from x_i to y_i by the path supplied inside J. Its retained prefix and suffix have no vertices in J except their attachment endpoints. They are disjoint from the interiors of all the replacement paths. The retained pieces of different original paths are themselves disjoint, and the replacement paths are disjoint by wovenness. The resulting concatenations are therefore simple, vertex-disjoint paths with the required endpoints and intersections. Notice that a replaced segment may have made excursions outside J; those excursions are removed, explaining the inclusion rather than equality in (i).

For successive replacements, the new vertices at a later step lie in a district disjoint from every earlier district and its model. Thus no new intersection with an earlier model is introduced. A prescribed root that is an original path endpoint remains that endpoint at every step. In its own district it is a first or last visit of that path, and no other path contains it. Its bag therefore has precisely the allowed path intersection.□

Proof. We set aside the prescribed roots and pair endpoints, then split the remaining vertices into one part containing an unrooted clique model and a second, still highly connected part in which to join its bags to the roots and route all prescribed pairs.

Fix an admissible root set and a system of at most 3t pairs. Let Z be the union of the roots and all pair endpoints. For sufficiently large t the displayed upper bound on s is at most t, so |Z|\le7t. Put k'=\lfloor K_0t/2\rfloor. Deleting Z leaves a k'-connected graph: deleting a further set of fewer than k' vertices still deletes fewer than K_0t vertices in total, and the order condition also follows from |V(J)|>K_0t. Every vertex of J, including each vertex of Z, has at least K_0t-|Z|\ge k' neighbors outside Z.

Independently place each vertex of J-Z in A with probability 1/1000, and write B'=V(J)\setminus(Z\cup A). We show that with probability tending to one both of the following hold:

For each vertex of J, fix k' of its neighbors outside Z. The number of these neighbors placed in A is a sum of k' independent indicators with mean k'/1000. By Lemma 2.5, the probability that it is below k'/2000 or above k'/2 is \exp(-\Omega(k')). A union bound over at most t^{1.06} vertices proves (31) with probability tending to one.

For (32), form in advance the cut-test matchings of Lemma 2.6 for J-Z, with connectivity parameter k' and order bound n=t^{1.06}. The number of tests is at most

A test matching has at most k'/4 endpoints. The expected number of its endpoints in A is at most k'/4000, whereas the cut test allows fewer than k'/32. This leaves a fixed positive multiple of k' as a deviation margin. Lemma 2.5, applied to at most k'/4 independent indicators, bounds each failure probability by \exp(-\Omega(k')). Their union has probability tending to zero. On the degree event (31), every vertex of J-Z has at least k'/2 neighbors outside A. Thus all hypotheses of Lemma 2.6 hold simultaneously with positive probability, and it gives (32). Fix such a split.

The graph J[A] is nonempty and has minimum degree at least k'/2000; hence its density is at least k'/4000=\Omega(t). Uniformly for the allowed values of s\ge2,

Lemma 5.1 therefore implies that J[A] contains a K_s model, for all sufficiently large t. If s=1, a single vertex of A supplies the model. Denote the model bags by M_1^0,\ldots,M_s^0 and select a port p_j\in M_j^0 from each bag.

Choose distinct representatives in B' for all the following roles: each port, each root, and each of the two endpoints of every noncoincident prescribed pair. A representative is required to be a neighbor of the vertex it represents. When a root is also a pair endpoint, its two roles receive different representatives. There are at most 2s+6t\le8t roles. By (31), each has at least k'/2 available neighbors in B', so greedy distinct selection is possible.

Partition the representatives into groups of size two: the port and root representatives for each j, and the two endpoint representatives for each noncoincident pair. By (30), for sufficiently large t,

Theorem 2.3 in J[B'] gives disjoint connected sets for these groups. Write C_j for the set joining the representatives of p_j and r_j. The set

is connected, using the two representative attachment edges. These sets are disjoint and remain pairwise adjacent through the original model on A.

In each other grouping set choose a path joining its two representatives, and extend it by their attachment edges to the original pair endpoints. Use the trivial path for every coincident pair. The nontrivial paths are disjoint inside B', all their original endpoints lie in Z, and different pairs have disjoint endpoint sets. The model bags contain no vertices of Z except their own roots. Consequently the only model–path intersections are roots that are endpoints of the respective pairs, exactly as in Definition 6.4.□

Proof. An internal visit to B would allow truncation at that visit, strictly shortening a path. Its new target cannot be the target of another path, by disjointness. For type (2), an internal visit to A likewise allows deletion of the initial segment, making that visit the new source. For type (1), all sources are already prescribed starts, and the allowed-intersection rule excludes any internal visit to A. This proves (i).

For (ii), let v\notin U have at least four neighbors on a path x_0x_1\cdots x_l, ordered from source to target. Its first and last neighbor indices i<j satisfy j-i\ge3. If v\notin A\cup B, replace the segment from x_i to x_j by x_i v x_j. This saves at least one edge and introduces no intersection with another path. If v\in B, truncate the path after x_i and use v as its target; here i+1\le l-2<l. If v\in A, the system must have type (2), since all type (1) sources belong to U. Start instead at v and follow the suffix from x_j to x_l; its length is 1+l-j\le l-2. These are valid systems with new free endpoint choices, contradicting minimality in every case.

To prove (iii), put U_0=U\setminus A for type (1) and U_0=U for type (2). Suppose that some nonempty induced subgraph P[S], S\subseteq U_0, has minimum degree greater than 2q. For every path meeting S, mark its first two vertices in S, or its only such vertex if there is just one. At most 2q vertices are marked. Each vertex of S belongs to exactly one path: the only possible overlaps were the repeated starts, which were removed in type (1).

For a path Q_i meeting S, let u_i be its first vertex in S. Its degree in P[S] is greater than 2q, so it has a neighbor v_i in S which is not marked. This vertex belongs to some path Q_j and is at least its third vertex in S. Direct an arrow from i to j, recording the edge u_i v_i. Every participating path has one outgoing arrow, so these arrows contain a directed cycle, possibly a loop.

For each arrow i\to j on this cycle, form a new path from the prefix of Q_i ending at u_i, the edge u_i v_i, and the suffix of Q_j starting at v_i. Leave all paths outside the cycle unchanged. On each cycle path Q_j, the retained prefix ends at u_j, while the retained suffix begins at the incoming arrow’s vertex, at least the third vertex of S on Q_j. The two retained pieces are disjoint and separated by at least two original path edges. Pieces lying on different original paths are disjoint except for the permitted repeated starts. Thus the new concatenations are simple and satisfy precisely the original disjointness conditions.

Every original source prefix is retained, so the required sources and their multiplicities are unchanged. This remains true if both paths with the same source belong to the directed cycle: only their suffixes are exchanged, and their shared initial vertex remains their only intersection. The target suffixes are permuted, preserving distinct targets. Such a permutation is allowed because no pairing was prescribed.

If the cycle has c paths, at least 2c original edges are removed between their retained prefixes and suffixes, and precisely c joining edges are inserted. The total length decreases by at least c>0. This final contradiction proves (iii).□

Proof. First truncate every input path at its first visit to D if necessary. Within either family this preserves all distinctness and disjointness requirements. Work in the graph consisting only of the vertices and edges of the two resulting path families; ambient edges are unnecessary. For each prescribed pair of second-family starts, identify its two vertices to form one temporary source. The paths of that family have no other vertices in H, and the first family avoids H, so each original path still gives a path after identification.

Write N=|Z|+m. There are now N sources, namely Z together with the m temporary sources, and there are two given routes from each source to D. Across these 2N routes, every vertex has congestion at most two, where congestion counts the number of routes containing the vertex. At a vertex of Z there are only its two first-family routes, since the second family avoids Z. At a temporary source there are only its two second-family routes, since the first family avoids H. Elsewhere there is at most one route from each family. This includes vertices of D, whose ends are distinct within each family but need not be distinct between the two families.

Deleting fewer than N vertices meets fewer than 2N routes. Some entire source-to-D route therefore survives. By Lemma 6.1, there are N disjoint paths from the full source set to D, with no internal source or target vertices. Every source is used, since the source set has cardinality N.

Each temporary source occurs on exactly one packed path and only as its starting endpoint. Lift the first edge of that path to whichever one of its two original starts supplied this edge, and keep the rest of the path unchanged. This selects exactly one original start from the pair. No switching between the two original starts is needed, because the identified vertex was not internal. Different temporary sources came from disjoint pairs, so all the lifted paths remain vertex-disjoint.

The only vertices of H in the graph of the original families were the 2m second-family starts. All their images were source vertices and could not be internal in the packing. Thus the lifted paths meet H exactly at the m selected starts; all unselected starts are absent. The target-end convention survives lifting, and every used vertex belongs to an original path family, as required.□

Proof. We use c_d from Lemma 4.5 and B_* from Lemma 5.2. All constants and cutoffs in this proof are independent of the history and of the lengths of its paths.

The two path collections. Remove the starting vertex from each first-system path, and collect all the resulting nonempty paths in a family \mathcal A. These paths are pairwise vertex-disjoint. Within one round the only intersections of first-system paths are their prescribed starts, which have been removed. Across rounds, a new first system avoids the old footprint except at its tips W. Every tip is a prescribed start, and no such start is internal on any path of the system. After stripping starts, the new paths therefore avoid the entire old footprint.

Let \mathcal B consist of the full second-system paths from all rounds. These too are pairwise vertex-disjoint: each new second system avoids the entire old footprint, which contains every earlier second-system path. No disjointness between \mathcal A and \mathcal B is asserted or needed. There are at most 4t first paths and 2t second paths per round, so, if q\le R_t rounds have been started,

Small sets and exceptional vertices. Let X_0 contain all districts J,D, all tip sets appearing in the history, and the ends of every path in both systems. Counting repetitions only increases the following bound:

Indeed, there are at most R_t+1 tip sets; the two systems together have at most 12t path-end occurrences per round.

Consider the footprints at the start of each round and also F_{\rm last}; call these at most R_t+1 sets the snapshots. The final snapshot will control neighbors of vertices outside the final footprint. Earlier snapshots will control the neighbors that a newly entering vertex has on older paths. At a snapshot T, let \mathcal A_T,\mathcal B_T be the two collections formed by systems already included in T. They use the original recorded paths, with only each first path’s own start removed; no vertices of the set X defined below have yet been removed from these collections. For either collection \mathcal C, declare a vertex v\in V(G)\setminus T exceptional if it has a neighbor on at least B_*t distinct members of \mathcal C.

To count these vertices, contract the disjoint connected paths of \mathcal C to a set of |\mathcal C| vertices. Vertices outside T are not contracted. Their numbers of distinct neighbors in the contracted set are exactly the numbers of paths they see. The resulting graph is a minor of G, so Lemma 5.2 implies that the number of exceptional vertices is at most

Apply this separately to \mathcal A_T and \mathcal B_T. By (34), the number at one snapshot is at most 6R_t t^{1+2\epsilon}. Let X be X_0 together with the exceptional vertices from all snapshots, including exceptional vertices outside F_{\rm last}. Then

for sufficiently large t, since \epsilon=1/200. Thus every required snapshot has been counted.

Put Y=F_{\rm last}\setminus X. The sets X,Y are disjoint, and every vertex of Y lies on a recorded path.

Neighbors from outside the footprint. Let v\notin X\cup Y. Then v\notin F_{\rm last}, so it was outside every recorded path union. Moreover, it belonged to the graph in which each system was minimized: every excluded set F\setminus W or F\cup R is contained in F_{\rm last}. By Lemma 6.8, it has at most three neighbors on each path. Nonexceptionality at the final snapshot bounds the number of paths it sees by fewer than B_*t in each collection. All stripped starts lie in X_0. Consequently

Degeneracy inside the footprint. Order the vertices of Y by their round of first entry into the footprint. Within a round, put vertices on \mathcal Q_1 first, and then the remaining new vertices on \mathcal Q_2. This partitions Y into at most two phases per round, because district vertices and all initial tips lie in X_0.

A vertex v entering in a given round was outside that round’s old footprint F. If v\in Y, it was not exceptional at the snapshot F. For every earlier system, its forbidden vertices belong to F, while v\notin F; hence v was eligible in the graph of that minimization and was outside its path union. The preceding argument therefore gives at most 6B_*t neighbors of v in Y from earlier rounds.

A first phase is contained in the union of at most 4t first-system paths with their starts removed. Lemma  6.8 makes its induced graph 8t-degenerate. A second phase is contained in the union of 2t minimizing second-system paths, so its induced graph is 4t-degenerate, and in particular 8t-degenerate. These are assertions about the induced graphs in G: all vertices of the relevant phase belong to the graph used for that minimization, which was an induced subgraph of G.

Finally, a vertex in the second phase of a round lies outside the entire first-system union and outside the old footprint. It therefore belongs to G-(F\setminus W). Lemma 6.8 bounds its neighbors in the first phase by 3(4t)=12t.

In any nonempty subgraph of G[Y], select the latest represented phase and a vertex of degree at most 8t within that phase. It has no neighbors in a later represented phase, at most 12t neighbors in an earlier phase of the same round, and at most 6B_*t neighbors in earlier rounds. Hence G[Y] is (6B_*+20)t-degenerate.

Equations () and (37) now verify every hypothesis of Lemma 4.5, with d=6B_*+20. It follows that

Since F_{\rm last}\subseteq X\cup Y, the graph G-F_{\rm last} contains G-X-Y as an induced subgraph. Monotonicity of list chromatic number proves the assertion. For the initial footprint the same proof has Y=\varnothing and X=W_0.□

Proof of Lemma 7.1. Let K_0=10^5\gamma be the integer fixed in Lemma 6.7, and put k=K_0t. Let D_{K_0} be supplied by Lemma 5.4. Use c_f from (33), put

and let c_0=4L+5 be the deletion constant for d=0. Choose a positive integer S satisfying

These choices involve only constants already fixed. We then take t sufficiently large for Lemmas 5.4, 6.7, 4.5, and 7.2 with the fixed parameters used below, and for all displayed size inequalities in the construction.

Suppose that r=\ell(G)\ge2St, h(G)<t, but no two vertex-disjoint induced subgraphs of G both have list chromatic number at least r-St. We will construct a K_t model.

Labels, rounds, and invariants. Partition the label set \{1,\ldots,t\} into m_0 nonempty blocks, each of size at most \lceil t/m_0\rceil. Schedule one round for each individual block and one for each unordered pair of distinct blocks. There are R_t rounds. The labels treated in a round form a set I, which is either a block or the union of its two assigned blocks. Its size s satisfies, for sufficiently large t,

Every pair of distinct labels occurs together in a scheduled round.

At the start of a round we maintain the following data.

1. (1)

   Pairwise disjoint nonempty connected vertex sets B_1,\ldots,B_t, with all adjacencies obtained in earlier rounds.

2. (2)

   A footprint F containing these sets and arising from the history rules of Lemma 7.2. It retains all vertices of every district and of both original minimizing path systems from every completed round.

3. (3)

   A k-connected induced region H with

   \ell(H)\ge r-c_ht,\qquad V(H)\cap F=W,

   where W=\{w_1,\ldots,w_t\} consists of distinct tips with w_j\in B_j.

In particular, no vertex of H-W belongs to an earlier footprint. The distinction between the footprint and the sets B_j is useful: unused path vertices remain in the footprint and are accounted for by Lemma 7.2.

The inequalities in () imply r>6k. Lemma 4.3 supplies a k-connected induced subgraph H with \ell(H)\ge r-6k\ge r-c_ht. It has more than k\ge t vertices. Choose distinct tips w_j there and initialize B_j=\{w_j\} and F=W.

Two districts and the first minimizing system. Consider a round with label set I of size s. Deleting its current tips gives

Corollary 5.5 states that if \ell(P)>2D_{K_0}t+2 and h(P)<t, then P contains an induced k-connected district of order at most t^{1.06}.

First obtain such a district J\subseteq H-W. Delete it using Lemma 4.5 with X=V(J) and Y=\varnothing, losing at most c_0t. The remaining list chromatic number is at least

The same district consequence supplies a second district D\subseteq H-W-J. Both J,D are k-connected and have order at most t^{1.06}, and both are disjoint from F. Choose distinct roots R_J=\{u_j:j\in I\} in J, and put

The graph H is a subgraph of G-(F\setminus W), is 2|Z|-connected, and contains the disjoint source and target sets Z,D. Also |D|>k\ge2|Z|. Lemma 6.2 therefore gives a feasible double system. Among all such systems in the full induced graph

choose a minimum-total-length system \mathcal Q_1. Its only intersections with F are its prescribed starts in W. Set

The history ending with this first system satisfies Lemma 7.2, and hence

The next region and the second minimizing system. By (), the right side of (42) is greater than 6(K_0+1)t. Lemma 4.3 gives a (K_0+1)t-connected induced region H'\subseteq G-F^- with

We claim that |V(H')\cap V(H)|\ge k. Otherwise deleting this intersection from H' gives an induced subgraph disjoint from H, of list chromatic number at least

The other graph H has list chromatic number at least r-c_ht\ge r-St. This contradicts the supposition on G.

It follows that the graph induced by V(H)\cup V(H') is k-connected. After deleting fewer than k vertices, each of its two regions is connected and at least one vertex of their intersection survives. This union meets F only in W. Deleting Z=W\cup R_J leaves a graph of connectivity at least

contained in the induced graph

Neither H' nor D meets Z, these two endpoint sets are disjoint, and each has more than 2t vertices. Lemma 6.1 supplies 2t disjoint paths between them.

Choose \mathcal Q_2 of minimum total length among all 2t-path systems from arbitrary distinct vertices of H' to arbitrary distinct vertices of D, in the full graph (44). This is an unpaired minimization. Its paths meet H' and D only at their respective ends. Let T'\subseteq V(H') be their 2t starting vertices, and put

In particular,

This completes another round of the history in Lemma 7.2.

Combining the systems and inserting the district model. The sets Z,V(H'),V(D) are pairwise disjoint. The first system avoids H', since it lies in F^-; the second avoids Z, by its domain (44). Lemma 6.9, with m=t, gives

vertex-disjoint paths to distinct vertices of D, one from each vertex of Z and one from each vertex of a selected set W^+\subseteq T' of size t. They meet D,H' only at their designated ends, use only vertices of the two systems, and meet F only in the W-ends. In particular, they do not visit the unused starts T'\setminus W^+. Assign W^+=\{w_1^+,\ldots,w_t^+\} bijectively to the labels.

By (40) and Lemma 6.7, the district J is (s,3t)-woven. Apply Lemma 6.5 to the q combined paths and the roots R_J. It produces in J a rooted K_s model with bags C_j, j\in I, and reroutes the combined paths without changing their ends. Each root u_j was already the endpoint of its own path. Thus the model meets the paths only at these roots, each on its corresponding path and in its corresponding bag.

The new vertices of the rerouted paths lie in J\subseteq F^+. Since J is disjoint from F,H',D, all the previous endpoint-only intersection statements with these sets persist. All rerouted paths and all bags C_j lie in F^+. We continue to record the original minimizing systems in the history; the rerouted paths are used only to extend the label bags.

Grouping in D and restoring the invariants. For each label j, group the terminals in D belonging to the paths from w_j, from w_j^+, and, if j\in I, from u_j. These groups partition the q distinct terminals. Since

Theorem 2.3 supplies pairwise disjoint connected sets E_1,\ldots,E_t in D containing their respective groups. For the next region put

Figure 1 now shows how these pieces fit into one extended label bag.

Extend B_j by the two or three corresponding paths, by E_j, and by C_j when j\in I. The resulting set B_j^+ is connected: its old bag contains w_j; the paths join every attached piece to E_j; and it contains the new tip w_j^+. The sets B_j^+ are pairwise disjoint. Indeed, the old bags are disjoint and meet the added paths only at their own W-ends; the paths are disjoint; the sets E_j are disjoint and meet paths only at the designated terminals; and the bags C_j are disjoint, lie outside F\cup D, and meet paths only at their own roots. All these sets lie in F^+. Old adjacencies persist because B_j\subseteq B_j^+, and every pair of labels in I gains an adjacency through its bags in the district model.

It remains to check the next-region invariant. Exactly t vertices were deleted from the (K_0+1)t-connected graph H', so H^+ is K_0t-connected. By (43) and (38),

Equation (45) gives

Thus F^+,H^+,W^+, and the bags B_j^+ restore every invariant for the next round.

After all R_t rounds, every pair of labels has an adjacency. The t disjoint connected label bags therefore form a K_t model in G, contradicting h(G)<t. This proves Lemma 7.1.□

Proof. The main inductive step concerns h(P)<64a and sufficiently large a. It separates the paths for prescribed pairs from the clique-model construction. Give each root and each end of a noncoincident pair its own neighboring proxy outside the original terminal set, with all proxies distinct, and delete the original terminals. Choose a minimum-total-length system of two paths per proxy to a small highly connected district D. Deleting the proxies, D, and these paths costs only O(a) in list chromatic number. We can therefore extract a highly connected region H' disjoint from the first path system. Further connections from H' to D and Lemma 6.9 produce disjoint paths from all proxies and from a set W of a vertices of H' to D, meeting H' only at W. It then suffices to build a clique model rooted at W inside H': grouping the path ends in D attaches the model to the root proxies and completes the prescribed pair paths.

For this internal model, divide the labels of W into three blocks. Separability and connectivity extraction supply three disjoint districts for recursive calls, one for each pair of blocks. A call needs at most 2\lceil a/3\rceil roots. Each label receives two bags to be joined to its vertex of W. The 2a joining paths may pass through the recursive districts; wovenness lets us reroute them while constructing the child models, keeping the retained bags disjoint from the paths except at their designated roots. Every pair of labels shares a district and hence receives an adjacency.

We specify the order of the constants first. Fix all constants in the preceding sections, including L,C_*,B_*,K_0,D_{K_0}, the deletion constants c_d, and the separability constant S. Choose an integer K\ge100 such that

Choose an absolute integer a_0\ge24 so large that all sufficiently-large parameter conclusions used below hold with t=64a whenever a>a_0. Enlarge a_0 if necessary so that

and t^{1.06}+7a\le t^{11/10} for t=64a, a>a_0. All these requirements involve only constants already fixed, and none involves Q. Finally choose an integer Q satisfying

We prove the assertion by strong induction on a.

Separating the terminal roles. Fix a distinct roots and at most 3a pairs as in Definition 6.4. Let Z_0 be their union, so |Z_0|\le7a. For each root, and for each end of each noncoincident pair, choose a neighbor outside Z_0 as its proxy. All proxies are distinct, even for different roles of the same original vertex. This is possible greedily because \delta(P)\ge Ka and fewer than 14a vertices are forbidden at any choice. Coincident pairs will ultimately use trivial paths at their original vertices and need no proxies.

Put G=P-Z_0 and let Z be the proxy set. Then

It suffices to find in G a clique model rooted at the root proxies and paths for the other proxy pairs, with all model bags and all these paths pairwise disjoint. Adding the proxy edges and the original vertices then restores precisely the root–path coincidences allowed by wovenness. Different prescribed pairs have no common original endpoint; a coincident pair at a root meets only that root’s expanded bag.

A large minor and the finite base range. Set t=64a. If h(P)\ge t, delete from a K_t model every bag meeting Z_0. This leaves a K_{57a} model in G. Since 57a\ge4|Z| and (K-7)a\ge2|Z|, Lemma 6.3 gives a clique model rooted at all of Z. Retain the root-proxy bags. For each other proxy pair, a path through its two bags and an edge between them joins the pair. These paths and the retained bags are disjoint because all proxies and their bags are distinct. This proves the required conclusion in the large-minor case, for every a.

Suppose h(P)<64a. Lemma 5.1 gives

For 1\le a\le a_0 this is strictly less than Qa by (50). Thus the minor-free case is impossible throughout the base range. We may henceforth assume a>a_0.

A junction district and a fresh region. Every vertex of G-Z has degree at least (K-14)a, which is greater than 2D_{K_0}t by (46). In particular this graph is nonempty and has density greater than D_{K_0}t. Apply Lemma 5.4 to find a K_0t-connected district D\subseteq G-Z with |V(D)|\le t^{1.06}.

The connectivity of G and the order of D permit two paths per proxy from Z to distinct vertices of D, with only the prescribed repeated starts in common, by Lemma 6.2. Choose such a system \mathcal Q_1 of minimum total length in G. It has at most 14a paths. Put

We have |X|\le t^{11/10} by the choice of a_0. Lemma 6.8 gives 28a-degeneracy of G[Y] and at most 42a neighbors in Y for every vertex outside X\cup Y. These bounds are at most 42t, so Lemma 4.5 with parameter 42 gives

By (49) the right-hand side exceeds 6K_0t. Lemma 4.3 therefore supplies a K_0t-connected induced subgraph H'\subseteq G-X-Y such that

In G-Z, the sets H' and D have order greater than K_0t, and the connectivity is at least (K-14)a>2a. Hence there are 2a disjoint H'-to-D paths. Truncate them at their last visit to H' and their first subsequent visit to D, so they have no internal vertex in either set. They avoid Z. Lemma 6.9, applied to these paths and \mathcal Q_1, gives disjoint paths to D from all proxies in Z and from a set W of a distinct vertices of H'. These paths meet H' and D only at their appropriate ends.

It is now enough to construct a clique model rooted at W entirely inside H'. Indeed, in D group the terminal ends of the outside paths as follows: pair each root proxy with a different member of W, and pair the other proxies as prescribed. There are at most |Z|+a\le8a terminals, so Theorem 2.3 applies because K_0t\ge8\gamma a. These disjoint groups and the outside paths attach the rooted model to the root proxies and supply all other required paths. The model inside H' has no unwanted intersection with the outside paths, since their only vertices in H' are precisely W.

Three recursive districts. For each w\in W choose two neighbors in H'-W, all 2a choices distinct. Minimum degree at least K_0t permits this greedy choice. Let N be their set and put H''=H'-W-N. Then

Equation (49) gives r_0>3St. Apply Lemma 7.1 to H'', and then to one of the two resulting subgraphs. The first application is legal because \ell(H'')\ge r_0>2St. Each of its subgraphs has list chromatic number at least r_0-St>2St, making the second application legal as well. We obtain three disjoint subgraphs each of list chromatic number at least r_0-2St.

Take a'=2\lceil a/3\rceil. After the loss of 2St to separability, each subgraph must still pay 6Ka' for connectivity extraction and retain Qa' for the recursive call. If A=10+64(c_{42}+6K_0+2S), then

by (47) and (48). In particular r_0-2St>6Ka', and list extraction in each subgraph produces disjoint Ka'-connected induced districts J_1,J_2,J_3 with list chromatic number at least Qa'. Since a'<a, induction makes each district (a',3a')-woven.

Partition the labels of W into three nonempty blocks B_1,B_2,B_3, each of size at most \lceil a/3\rceil. Assign one district to each pair of blocks, relabeling them J_{12},J_{13},J_{23} accordingly. In its district, designate a distinct root for each label of the corresponding two blocks, and add arbitrary distinct padding roots to bring the total to a'. The districts have enough vertices for this choice. Every label has exactly two designated roots, in different districts; every pair of labels occurs together in at least one district, including two labels in the same block; see Figure 2.

Inside H'-W, join the two chosen neighbors of each w to its two designated roots, respectively, using disjoint paths. This is an application of Theorem 2.3 to 4a distinct terminals: the neighbors lie in N, while the districts were chosen in H'' and hence avoid N. The connectivity is at least K_0t-a\ge4\gamma a. There are 2a paths. Apply Lemma 6.5 successively in the three districts to incorporate their rooted clique models while retaining these path ends. Each district has sufficient weaving capacity, since

Discard all padding bags. Each designated root remains an endpoint of its path; the retained bags meet the rerouted paths only at their own designated roots. Since the districts are disjoint, later rerouting does not introduce an intersection in a previously retained bag.

For each w, unite its two designated bags with their respective paths, the two edges to w, and w itself. The resulting a sets are connected and disjoint, rooted at W. Two labels have an edge between their sets because they occur together in one of the district clique models. This constructs the required rooted K_a model inside H' and completes the induction.□

Proof of Theorem 1.1. Let K,Q be as in Theorem 8.1. We first show that, for every integer t\ge2,

Otherwise Lemma 4.3, with connectivity parameter Kt, gives a Kt-connected induced subgraph P with \ell(P)\ge\ell(G)-6Kt>Qt. Theorem 8.1 makes P (t,3t)-woven. Its order is greater than Kt\ge t, so we may choose t roots and no pairs. Wovenness then supplies a K_t model, contradicting h(G)<t.

For a nonempty graph, h(G)\ge1. Taking t=h(G)+1\le2h(G) in (55) proves

Thus the absolute integer C=2(Q+6K) has all the claimed uniformity. The finite base range was covered before the induction began, so no small-parameter exception remains.□