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 \[\mathbb E\bigl(1+|I|/M\bigr) =1+|V(P)|/(rM)\le2.\] 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 \[qN\le A_0ty\log(2y),\qquad M\le2t^{1/10}y.\] Lemma 7 therefore gives \[\begin{align*} \Pr\bigl(|Z-\mathbb EZ|\ge\delta r\bigr) &\le2\exp\left(-\frac{\delta^2r^2}{2(qN)(2M)^2}\right)\\ &\le2\exp\left( -\frac{\delta^2t^{4/5}}{32A_0y^5\log(2y)}\right). \end{align*}\] 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 11 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 \[ \chi(F^{(m)})\ge mf(F)>mr/2. \tag{13}\]

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 4 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 \[\chi(J)\ge\chi(F^{(m)})-6k' >\frac{19mr}{50}-6 >\frac{31mr}{100}.\] 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 11, the events \[\mathcal A_i=\{f(H[W_i\cap V(H)])>r/5\}\] 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 3 now gives \[h(H[T_i])>r/32>2\lfloor r/200\rfloor=2x,\] 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 11 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 8 for the fixed graph \(H\), with order bound \(n\) and connectivity parameter \(k\). Fix this family before sampling the fresh copies, and set \[s=\left\lceil10\frac nk\log(2n)\right\rceil.\] The number of tests is at most \[\begin{align*} (n+1)^{s+1} &=\exp\bigl(O((1+n/k)\log^2(2n))\bigr)\\ &\le\exp\bigl(O(t^{1/10}\log^2t)\bigr). \end{align*}\] Here the constants are absolute, since \(D_0\) is fixed.

The endpoint set of each test matching is a fixed set to which Lemma 11 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 11 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 8, which gives the claimed connectivity. ◻

Proof of Lemma 10. 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 12 supplies a fixed \(H\). By (10), the failure probability in Lemma 13 is at most \(4\cdot10^{-4}+o(1)\). Thus Lemmas 13 and 14 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 \[\left\lfloor\frac{k}{32}\right\rfloor \ge\gamma(2xq)\ge\gamma m,\] so Theorem 5 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 9. 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 \[r_j=4t2^{-j},\qquad y_j=\max\{1,t/r_j\},\] 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 \[N_j=\lceil Br_j\log(2y_j)\rceil\] 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 \[\begin{align*} n_{\mathrm{bin}} &\le4Bt\log2\sum_{j\ge0}(j+1)2^{-j}+(J+1)+16t\\ &=16B(\log2)t+(J+1)+16t. \end{align*}\] Also \(J+1=O(\log\log t)\), since \(2^J\le4\log t\). Choose an integer \[D_{\mathrm{bin}}\ge16B\log2+18.\] For all sufficiently large \(t\), we have \(n_{\mathrm{bin}}\le D_{\mathrm{bin}}t\). Finally choose a positive integer \(L\) such that \[ \frac{L}{2D_{\mathrm{bin}}}>\log2+1. \tag{14}\]

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 \[\left(1-\frac{u}{2n_{\mathrm{bin}}}\right)^{|\mathcal L(v)|} \le\exp\left(-\frac{Lt\,u}{2n_{\mathrm{bin}}}\right) \le\exp\left(-\frac{Lu}{2D_{\mathrm{bin}}}\right).\] 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 \[(J+2)t^{11/10}\exp\left(-\frac{c_Bt}{\log t}\right)=o(1).\] 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 3 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 10, 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 \[(1-1/\rho)^{8t}\le\exp(-8t/\rho)=t^{-8}.\] 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. 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 25 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 25 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 26, 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 25 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 28: 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: \[\begin{align*} |N_J(v)\cap A|&\ge k'/2000, &|N_J(v)\cap B'|&\ge k'/2 &&(v\in V(J)), \tag{31}\\ J[B']&\text{ is }\lfloor k'/32\rfloor\text{-connected}. \tag{32}\end{align*}\] 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 7, 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 8 for \(J-Z\), with connectivity parameter \(k'\) and order bound \(n=t^{1.06}\). The number of tests is at most \[\exp\!\bigl(O(t^{0.06}(\log t)^2)\bigr).\] 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 7, 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 8 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\), \[s\log(2s)=O\!\left(\frac{t}{\log t}\right)=o(t).\] Lemma 20 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\), \[\left\lfloor\frac{k'}{32}\right\rfloor\ge \gamma(2s+6t).\] Theorem 5 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 \[M_j=M_j^0\cup C_j\cup\{r_j\}\] 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 28. ◻

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 25, 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. ◻