Let G be a finite simple undirected graph with n vertices. An edge
partition of G writes every edge of G in exactly one part. Different
parts may share vertices; no edge is used twice. A part is either a
simple cycle, meaning a closed walk that visits no vertex twice except
the start and end and has length at least three, or a single edge.
The question is how many parts suffice in the worst case.
THEOREM. There is an absolute constant C > 0 such that every finite
simple undirected graph on n vertices has an edge partition into at
most C n simple cycles and single edges.
"Absolute" means C does not depend on n, on the graph, or on anything
else. The empty partition is allowed for the empty graph, and isolated
vertices need not be covered.
The bound is optimal up to the value of C. A tree on n vertices has
n - 1 edges and no cycles; every edge must be a single-edge part, so
no universal bound below 1 applies to that case. Complete bipartite
graphs give a sharper lower bound of about (3/2) n; this is recorded
by Bucić and Montgomery, Section 6.
The covering version of the question, where cycles and edges may
overlap, is easier: each edge becomes its own part, so about n parts
suffice, and the point is to do better. Erdős, Goodman and Pósa
analysed the covering version in 1966 and posed the edge-disjoint
version as a conjecture.
Erdős, Goodman, Pósa, "The representation of a graph by set
intersections", Canadian Journal of Mathematics 18 (1966), 106-112.
https://users.renyi.hu/~p_erdos/1966-21.pdf
Covering and partitioning are different. In a cover, an edge may
appear in several parts. Deleting the repeats can break cycles into
many paths, so a linear cover does not supply a linear partition.
Pyber settled the covering problem in 1985, proving that n - 1 cycles
and single edges always cover the edge set of an n-vertex graph,
matching what a tree requires.
Pyber, "An Erdős-Gallai conjecture", Combinatorica 5 (1985), 67-79.
https://doi.org/10.1007/BF02579444
Progress on the partition problem came in stages. Conlon, Fox, and
Sudakov improved the elementary O(n log n) bound to O(n log log n),
and proved linear bounds for graphs of linear minimum degree and for
binomial random graphs with high probability.
Conlon, Fox, Sudakov, "Cycle packing", Random Structures and
Algorithms 45 (2014), 608-626.
https://people.math.ethz.ch/~sudakovb/cycle-packing.pdf
Korándi, Krivelevich, and Sudakov obtained asymptotically optimal
counts over a broad range of edge probabilities for random graphs.
Korándi, Krivelevich, Sudakov, "Decomposing random graphs into few
cycles and edges", Combinatorics, Probability and Computing 24
(2015), 857-872.
https://people.math.ethz.ch/~sudakovb/cycle-packing-random-graphs.pdf
Girão, Granet, Kühn, and Osthus proved the sharp bound about (3/2) n
for sufficiently large graphs with linear minimum degree.
Girão, Granet, Kühn, Osthus, "Path and cycle decompositions of dense
graphs", Journal of the London Mathematical Society 104 (2021),
1085-1134.
https://web.mat.bham.ac.uk/D.Osthus/path_cycle_dec_dense.pdf
Akbari, Aloni, Beikmohammadi, and Clow proved the bound n - 1 for
graphs of maximum degree at most four, and sharpened Pyber's covering
bound from n - 1 to n - 2 for graphs with a cycle.
Akbari, Aloni, Beikmohammadi, Clow, "Tight bounds for cycle-edge
decompositions and covers", arXiv:2509.01901 (2025).
https://arxiv.org/abs/2509.01901
Bucić and Montgomery pushed the general partition bound to
O(n log* n), where log* n is the number of logarithm iterations
needed to reach at most one.
Bucić, Montgomery, "Towards the Erdős-Gallai cycle decomposition
conjecture", Advances in Mathematics 437 (2024), 109434.
https://arxiv.org/abs/2211.07689
The proof gives the conjectured linear bound. Its main new idea is to
save vertices across scales: pair vertices in a bounded-degree leftover
so that identifying each pair shrinks the graph to a quotient of
strictly smaller order, apply induction to the quotient, then lift
quotient cycles back to simple cycles using edges that were reserved
for routing. The savings pay for the work outside the recursive calls.
Two consequences for cycle-only partitions follow. A graph is Eulerian
if every degree is even; connectivity is not required. Any edge
partition of an n-vertex graph into cycles uses at least Δ(G)/2
cycles, where Δ(G) is the maximum degree, because each cycle uses at
most two edges incident with a fixed vertex.
COROLLARY 1. Every finite simple Eulerian graph on n vertices has an
edge partition into at most C n cycles, with C from the theorem.
Proof. Suppose the theorem's partition has r cycle parts and s
single-edge parts, with r + s <= Cn. The graph formed by the s edges
has even degrees, since deleting cycles preserves degree parity.
Repeatedly removing a cycle from it preserves that property and ends
with no edges. Cycle removal costs at most s extra cycles, so the
total is at most r + s <= Cn.
COROLLARY 2. Fix δ, p > 0. There exist ε > 0 and n_0 such that every
Eulerian graph G on n >= n_0 vertices has an edge partition into at
most Δ(G)/2 + δ n cycles, provided every partition V(G) = A ∪ B with
|A|, |B| >= ε n has at least p |A| |B| edges between A and B.
Proof. The partition-cut condition is the weakly-(ε, p)-quasirandom
condition of Girão, Granet, Kühn, Osthus, Section 1.2. Their
Proposition 6.3 shows that the stated bound with these quantifiers is
equivalent to their Erdős-Gallai Conjecture 1.4, which the main
theorem supplies.
The lower bound Δ(G)/2 is attained up to the δ n correction, and
cannot be improved: a cycle uses at most two edges at any one vertex,
so a maximum-degree vertex needs at least Δ(G)/2 cycles through it.
Throughout, graphs are finite, simple, and undirected. A path is
simple and has at least one edge. The order of a graph is its number
of vertices, including isolated ones. Temporary quotients formed by
identifying vertices may have loops or parallel edges; these are set
aside before any decomposition theorem is applied.
An indexed family of subgraphs partitions a graph when their assigned
edge sets are pairwise disjoint and have the required union. Each
subgraph carries only its assigned edges, rather than all edges
induced by its vertex set. Different indices may have overlapping, or
even equal, vertex sets. Order sums count those indices separately.
For a vertex set U in a graph H, N_H(U) is the union of open
neighborhoods N_H(v) over v in U, and its external neighbor set is
N_H(U) minus U. A graph has cut expansion at least h when every
vertex set U with 0 < |U| <= |V|/2 has at least h |U| edges between U
and its complement. In a simple graph of order r >= 2 with cut
expansion h, the minimum degree is at least h, so r - 1 >= h.
The whole argument is a strong induction on n. Fix theta = 0.95 and
K = 200, put P0 = 4(K+1) and eta = 1/(100 P0); then
1.02 theta^K < 0.001 and theta^(K+1) < 0.001. All logarithms are
base two.
The induction hypothesis is slightly stronger than the theorem, using
the potential
phi(n) = max{1/2, 1 - 1/sqrt(log n)} for n > 1,
phi(1) = 1/2.
Proposition. There is an absolute constant C such that every finite
simple graph on n >= 1 vertices has an edge partition into at most
C phi(n) n simple cycles and single edges.
Since phi(n) <= 1, the proposition implies the theorem.
The argument proceeds in three moves. First, cut the graph into
overlapping pieces at a sequence of scales D_j = n^(theta^j). At scale
D_j, delete a few long cycles, split the remaining edges into
expanding pieces of order between D_j^0.90 and D_j^1.02, and pass a
residual graph of average degree at most D_j^0.95 to scale D_(j+1).
Second, at one careful scale i, use the pieces of that scale to pay
for the whole prefix 0..i+K, using pair identifications that reduce
the vertex count in the leftover. Third, recurse on the quotients and
on the tiny residuals.
Three external tools are used.
Tool 1 (Lovász path-and-cycle decomposition). Every finite simple
graph on n vertices has an edge partition into at most floor(n/2)
paths and cycles. Lovász proved this in 1968.
Lovász, "On covering of graphs", in Theory of Graphs (P. Erdős,
G. Katona, eds.), Academic Press, 1968, 231-236.
A corollary on path partitions alone is needed: every finite simple
graph on n vertices has an edge partition into at most n positive-
length simple paths, with each vertex an endpoint of at most two.
Corollary. Every finite simple graph on n vertices has an edge
partition into at most n positive-length simple paths, with each
vertex an endpoint of at most two.
Proof. If n = 0 there is nothing to prove. Otherwise add a vertex v0
and join it to exactly the even-degree vertices of the original graph,
isolated vertices included. Each old vertex then has odd degree in
the augmented graph. In any path-and-cycle partition its number of
path-endpoint occurrences is odd and positive. By Tool 1, if p is the
number of path parts, the old vertices force 2p >= n, and the theorem
gives p <= ceil(n/2). Thus every part is a path, and each old vertex
is an endpoint exactly once. Delete v0 from all paths. Delete any
edgeless remnants. Every old vertex is incident to at most one
deleted edge, so it gains at most one new endpoint occurrence. The
remaining paths partition the original edge set with endpoint load at
most two, and each positive-length path has two endpoints, so there
are at most n paths.
Tool 2 (Aharoni-Haxell hypergraph Hall theorem). A hypergraph is a
finite family of nonempty subsets of a finite ground set, and a
matching is a subfamily of pairwise disjoint edges. Let s be a
positive integer, and let (H_i) be a finite indexed family of
hypergraphs on a common ground set. Suppose every edge is nonempty
and of size at most s. If for every nonempty set I of indices, the
union of the H_i with i in I has a matching of size strictly greater
than s (|I| - 1), then there are edges E_i in H_i, one for each index
i, that are pairwise disjoint.
Aharoni, Haxell, "Hall's theorem for hypergraphs", Journal of Graph
Theory 35 (2000), 83-88.
https://doi.org/10.1002/1097-0118(200010)35:2%3C83::AID-JGT2%3E3.0.CO;2-V
Bucić and Montgomery, Theorem 6, give a self-contained proof of the
following bounded-rank form. If the hypergraphs have edges of
different sizes, pad each edge occurrence with private fresh vertices
until every edge has size exactly s.
Tool 3 (Chernoff estimates). If X is binomial with mean mu, then
Pr(X <= mu/2) <= exp(-mu/8),
Pr(X >= 2 mu) <= exp(-mu/3).
The constants are not important; what matters is exponential decay.
Two operations run at each scale. A coarse step deletes a few long
cycles and cuts the graph into overlapping boxes. A fine step extracts
expanding pieces from each box. All lower bounds on D are absolute and
can be imposed in one choice of D_sp.
Lemma (splitting at a scale). There are absolute constants D_sp and
C0 such that, for every real D >= D_sp, every graph G on a nonempty
vertex set of order N and with average degree at most D admits two
successive operations.
(i) Remove a family C of edge-disjoint cycles, each of length at
least D^1.01, with
|C| <= N / (2 D^0.01).
Partition the remaining edges into graphs G_Y on an indexed family Y
of vertex sets, called boxes, with
union of Y over Y = V(G), 1 <= |Y| <= D^1.02,
sum over Y of |Y| <= (1 + C0 / log D) N.
The graphs G_Y carry only their assigned edges; their vertex sets may
overlap.
(ii) Put sigma = D^0.90. For each box Y, partition E(G_Y) into the
edge sets of a family R_Y of graphs R and a graph H_Y on all of Y.
The graphs in R_Y have pairwise disjoint vertex subsets of Y, each
with cut expansion at least sigma and order sigma <= |V(R)| <= D^1.02.
The residual H_Y satisfies 2 |E(H_Y)| / |Y| <= D^0.95. The cycles C,
the pieces R, and the residuals H_Y together partition E(G).
One may take C0 = 2.
The first operation rests on a long-cycle fact. Put eps = 1/32. Call
a graph H of order u locally expanding if every vertex set U with
0 < |U| <= u/2 has at least
alpha |U|, alpha = eps / log^2 u,
external neighbors.
Fact. Let u be large, suppose H has at least one edge and order u, and
suppose some vertex set U with 0 < |U| <= u/2 has fewer than alpha |U|
external neighbors. Then H has a cycle longer than
q(u) = alpha^2 u / 100.
Proof. Run depth-first search from any vertex. Let t be a state at
which unexplored minus finished vanishes; such a state exists because
this quantity starts at u - 1, ends at -u, and decreases by 1 at
every push or pop. Let P be the stack path at that state, with
L = |V(P)| = u - 2t.
If t >= u/3, then 0 < t <= u/2 and every external neighbor of the
unexplored set lies on P. Expansion of the unexplored set is the
hypothesis, so this case cannot occur in a graph where every U with
|U| <= u/2 has at least alpha |U| external neighbors. Suppose instead
that the hypothesis holds and t < u/3. Then L = u - 2t > u/3.
Suppose H is locally expanding. If t >= u/3 the unexplored set is a
set U with |U| = t and its external neighbors lie on P, so
L >= alpha t >= alpha u / 3. If t < u/3 then L = u - 2t > u/3, and
u/3 >= alpha u/3 since alpha <= 1. Either way L >= alpha u / 3 for a
locally expanding H.
Put q = q(u) and j = floor(q). For large u, q >= 1, j >= 1, and
j + 1 <= 2q = alpha^2 u / 50 <= alpha u / 6 <= L / 2.
Partition P into three consecutive vertex segments X, J, Z with
|J| = j and the L - j remaining vertices distributed as evenly as
possible between X and Z. Each outer segment has order at least
floor((L - j) / 2) >= (L - j - 1) / 2 >= L / 4.
Suppose first that H - J has a path from X to Z. Take a shortest such
path, with endpoints x in X and z in Z. A shortest path is simple. Its
interior avoids X and Z (else a shorter path would exist) and avoids J.
Since X, J, Z partition V(P), the path meets P only at x and z. Its
union with the x-to-z subpath of P is a simple cycle. That subpath
carries all j vertices of J and at least j + 1 edges; the connecting
path adds at least one edge. The cycle has at least j + 2 >= 3 edges
and length above q.
Otherwise X and Z lie in distinct components of H - J. Isolate the
component containing X from the union of the other components. Let A
be the smaller of these two sets. The union of the other components
contains Z, so
L / 4 <= |A| <= (u - j) / 2 <= u / 2,
and every external neighbor of A in H lies in J. If H is locally
expanding, expansion gives
j >= alpha |A| >= alpha L / 4 >= alpha^2 u / 12 > alpha^2 u / 100 = q,
contradicting j = floor(q). Therefore a locally expanding graph has a
cycle longer than q(u), proving the contrapositive.
The cycle bound |C| then follows from a maximal choice. Since
|E(G)| <= ND / 2,
|C| D^1.01 <= |E(G)| <= ND / 2,
which is the stated bound. Delete the cycle edges, keeping all
vertices. By maximality the remainder contains no cycle of length at
least D^1.01, and every graph built subsequently inherits the
prohibition.
Uniform threshold. The function x/log^4 x is increasing for ln x > 4,
and
q(T) / D^1.01 = (eps^2 / (100 * 1.02^4)) D^0.01 / (log D)^4
-> infinity (D -> infinity),
where T = D^1.02. Choose D_sp large enough that T > e^4 and q(T) >
D^1.01. Then q(u) > D^1.01 for every u > T, so no graph of order
u > T obtained subsequently can be locally expanding without
contradicting the cycle prohibition. Every such graph therefore has a
vertex set U with |U| <= u/2 and |N_H(U) \ U| < alpha |U|.
The overlapping split. Fix such a set U in a graph H of order u > T,
put B = N_H(U) \ U, and form two children on vertex sets
V_1 = U union B, V_2 = V(H) minus U.
Assign to the first child every edge of H with both endpoints in V_1,
and to the second child every other edge. Every edge incident with U
has both endpoints in V_1, so every edge assigned to the second child
lies entirely inside V_2. This is an edge partition into two simple
subgraphs. Edges inside B go only to the first child. The children
cover V(H) and overlap exactly in B. All vertices of each child are
retained, including isolated ones in the assigned graph.
Writing s = |U|, b = |B|, u_1 = s + b and u_2 = u - s, with 1 <= s <=
u/2 and b < eps s / log^2 u, for sufficiently large D,
1 <= u_1 <= 3u/4, 1 <= u_2 < u,
u_1 + u_2 = u + b <= u + eps u_1 / log^2 u.
The middle bound uses eps / log^2 u <= 1/2, which gives u_1 < 3s/2 <=
3u/4.
Repeat this split whenever the current order exceeds T. Both child
orders are positive integers strictly smaller than the parent, so the
splitting tree is finite. Its leaves give the graphs G_Y on boxes of
order at most T. The cover property gives union of Y over Y = V(G),
and the edge assignments at each split give an edge partition of the
remainder.
Controlling the sum of box orders. The overlap adds edges. A
potential pays for it. For real x >= 1, put
f(x) = 1 + 1 / log(T/2) - 1 / log(max{x, T/2}).
For T >= 4 this is nondecreasing with
1 <= f(x) <= 1 + 1 / log(T/2) <= 2.
At a split of a parent of order u > T, put M = max{u_1, T/2} and note
M <= 3u/4. Both logarithms below are positive, and
f(u) - f(u_1)
= 1 / log M - 1 / log u
= log(u/M) / (log M * log u)
>= log(4/3) / log^2 u.
Monotonicity gives f(u_2) <= f(u). Using the parent-child order
relation,
u_1 f(u_1) + u_2 f(u_2)
<= (u_1 + u_2) f(u) - u_1 log(4/3) / log^2 u
<= u f(u) + (u_1 / log^2 u)(eps f(u) - log(4/3))
<= u f(u).
The last step uses eps f(u) <= 1/16 < log(4/3). Applying this at
every split of the finite tree, together with f >= 1 on leaves, gives
sum over Y of |Y|
<= sum over Y of |Y| f(|Y|)
<= N f(N)
<= N (1 + 1 / log(T/2)).
This holds also when N <= T, when the tree has only its root.
Since T = D^1.02 and D >= 4,
1 / log(T/2) = 1 / (1.02 log D - 1) <= 2 / log D.
That proves the box bound with C0 = 2.
Extracting pieces of cut expansion sigma. This follows the small-side
charging method of Conlon, Fox and Sudakov, Lemma 3.1. Fix a box Y,
write y = |Y|, and start with its assigned graph G_Y. Whenever a
current graph on a vertex set A of order at least two fails to have
cut expansion sigma = D^0.90, choose a partition A = A_1 union A_2
into nonempty sets with fewer than sigma min{|A_1|, |A_2|} crossing
edges. Put those cut edges into the residual H_Y and continue
separately with the edges internal to A_1 and A_2.
Both child orders strictly decrease, so the process terminates. The
terminal graphs are the pieces of R_Y; the terminal vertex sets
partition Y. By the stopping rule every terminal graph has cut
expansion at least sigma. A terminal graph of order r has minimum
degree at least sigma, so r - 1 >= sigma and r >= sigma + 1 > sigma,
and 1 <= r <= D^1.02 by construction.
For the residual average degree, charge each cut edge at its split
equally to the vertices of the smaller side (either side in case of
equality). A charged vertex receives less than sigma at that split.
Whenever a vertex is charged, the current set containing it at least
halves in size, and intervening splits only shrink it further. After
k charges the set has order at most y / 2^k and at least one, so
k <= log y. All cut edges are distinct, because later splits use only
edges internal to earlier children. Hence
|E(H_Y)| <= sigma y log y.
For y <= D^1.02 and D large,
2 |E(H_Y)| / y <= 2 sigma log y <= 2.04 D^0.90 log D <= D^0.95.
Every edge not set aside ends in exactly one terminal graph, and
singleton terminal graphs carry no edges, so H_Y and the pieces of R_Y
partition E(G_Y). Setting V(H_Y) = Y, including all retained vertices,
gives the average degree bound. The lemma is proved.
When the operations are repeated on residuals, the boxes descending
from any fixed box continue to cover every vertex of that box. This
follows from the cover property at each split and from the fact that
H_Y always has the full vertex set Y, regardless of which edges were
removed as cycles or as pieces.
Fix the absolute parameters theta = 0.95, K = 200, P0 = 4(K+1), and
eta = 1/(100 P0). Then 1.02 theta^K < 0.001 and theta^(K+1) < 0.001,
because theta^K <= exp(-10).
Lemma (selection of a prefix). Let (S_j) for j >= 0 be a nonnegative
finitely supported sequence, not identically zero. There is an index i
with S_i > 0 such that
sum from j = 0 to i+K of S_j <= P0 S_i.
Proof. Start at the first positive term and maintain the invariant
sum from j = 0 to i of S_j <= 2(K+1) S_i.
If the desired inequality fails at i, the sum of the next K terms
exceeds 2(K+1) S_i, and their largest value M exceeds 2 S_i. Move to
an index i' in that window with S_i' = M. Then
sum from j = 0 to i' of S_j
<= 2(K+1) S_i + K M
< (2K+1) M
<= 2(K+1) S_i'.
The invariant persists. Each move increases the index and lands at a
positive term, so finite support forces the procedure to stop, at
which point the desired inequality holds.
The layers are now built at every scale. Start with the given graph G.
Perform both operations of the
splitting lemma at each successive scale D_0, D_1, ..., D_(m-1),
where D_j = n^(theta^j) and
m = min { j >= 0 : D_j < D_* },
with D_* an absolute cutoff chosen later. The input at stage j has
average degree at most D_j: for j = 0 the bound is n - 1 < D_0 = n,
and for j >= 1 the residual graph in each box has average degree at
most D_j^0.95 = D_(j+1).
Let Y_j be the indexed family of level-j boxes, R_j the indexed
family of pieces removed inside them, and N_j = sum over Y in Y_j of
|Y|, S_j = sum over R in R_j of |V(R)|, with S_j = 0 for j >= m. The
residual graph passed to the next stage keeps the entire vertex set of
its box, including isolated vertices. Boxes have unique indexed
parents, contained vertex sets, and descend to cover their parent.
Distinct indices remain distinct even when their vertex sets coincide.
These operations define prospective layers. At the end of any finite
prefix, the long cycles removed so far, the pieces removed so far, and
the graphs remaining at the boundary partition E(G). Discarding
prospective operations beyond a chosen prefix means keeping their
input graphs, with all assigned edges, at that boundary.
Increase the constant C0 in the splitting lemma if necessary so that
C0 >= 1, and put C2 = 40 C0. For 0 <= j < m,
sum from l = 0 to j of 1 / log D_l
= (1 / log D_j) * sum from t = 0 to j of theta^t
<= 20 / log D_j.
Since 1 + x <= exp(x) and exp(x) <= 1 + 2x for 0 <= x <= 1/2,
provided log D_* >= C2, every level-j order sum satisfies
n <= N_j
<= n * product from l = 0 to j of (1 + C0 / log D_l)
<= n * (1 + C2 / log D_j)
<= 2n.
The lower bound comes from keeping the vertex cover at every split.
The same product calculation applied to the subproduct from level j
downward shows that the orders of all level-j descendants of a box of
order y sum to at most (1 + C2 / log D_j) y.
For the long cycles, if L_j is the family of cycles removed through
level j, then
|L_j|
<= sum from l = 0 to j of N_(l-1) / (2 D_l^0.01)
<= n * sum from l = 0 to j of 1 / log D_l
<= 20 n / log D_j.
The middle step uses D^0.01 >= log D for D >= D_*. These bounds are
independent of the number of layers. Piece disjointness inside each
box gives S_j <= N_j <= 2n.
At the end of a prefix through level t, the assigned edge sets give
the disjoint union
E(G) =
disjoint union over L in L_t of E(L)
disjoint union
disjoint union over j = 0 to t of
disjoint union over R in R_j of E(R)
disjoint union
the remaining boundary graphs.
This ledger is the bookkeeping spine of the argument. Every later
operation must put every edge into exactly one of these categories, or
move it to a later category without duplicating it.
A demand asks for a path between two distinct vertices. Several
demands may share endpoints. Three requirements arise simultaneously:
each route is short, all routes are edge-disjoint, and routes in the
same team are internally vertex-disjoint. Different teams may share
internal vertices; they compete only for edges.
The proof treats each candidate path as a hyperedge whose resources
are its graph edges plus one token (v, c(p)) for each internal vertex
v. The Aharoni-Haxell theorem then supplies disjoint representatives
for all demands at once. When the theorem's hypothesis fails, the
demands split into a large subfamily with small forbidden
neighborhoods, one endpoint of each in a small ball, and a size-growth
contradiction with expansion. This is the same technique that Bucić
and Montgomery use for route selection in their Proposition 8 and
Lemma 9, applied here to a level-i piece whose router edges are
reserved.
Lemma (routing). Let P be a simple graph of order r and cut expansion
at least h, with 1 <= h <= r/4. Let D be a finite set of demands. Each
demand p has two distinct endpoints x_p and y_p, a team c(p), and a
forbidden vertex set Z_p with |Z_p| <= z. Suppose load bounds hold:
each vertex of P occurs as an endpoint in at most k demands,
each team has at most b demands,
each forbidden set has |Z_p| <= z,
and suppose
h >= 64 (l^2 (k+b) + z)
for a positive integer l. Then there are simple x_p-y_p paths Q_p,
one for each p in D, with
(i) each Q_p has length at most l and no internal vertex in Z_p;
(ii) the paths are pairwise edge-disjoint;
(iii) internal vertex sets of paths in the same team are pairwise
disjoint.
The forbidden set Z_p may contain x_p or y_p; the restriction is only
on internal vertices. The uniform bound
l <= 108 (r/h) (log r)^2
holds.
Proof. If D is empty there is nothing to prove. Assume D is nonempty
and write c(p) for the team of p.
Resource hypergraphs. Make a resource set which is the tagged
disjoint union of E(P) and the tokens (v, c) for v in V(P) and a team
c. For each demand p form a hypergraph H_p on the resource set: its
hyperedges correspond to all simple x_p-y_p paths of length at most l
with internal vertices avoiding Z_p. A path of length t >= 1
contributes 2t - 1 <= 2l resources, so every hyperedge is nonempty
and of size at most 2l.
Aharoni-Haxell with s = 2l. A choice of pairwise disjoint
representatives from the H_p gives exactly the three required
properties. Suppose, for a contradiction, that the hypothesis fails
for some nonempty I subset of D. Let M be a maximum matching in the
union of the H_p for p in I. Then
|M| <= 2l (|I| - 1).
Let F be the set of graph edges used by M, and for each team c let
Y_c be the set of vertices v such that the token (v, c) is used by M.
Each matching member uses at most l graph edges and at most l tokens,
so
|F| <= 2l^2 |I|, sum over c of |Y_c| <= 2l^2 |I|.
For each team c, let m_c be the number of demands p in I with c(p) = c;
then m_c <= b and sum over p in I of |Y_(c(p))| <= 2b l^2 |I|.
Therefore the set
I_1 = { p in I : |Y_(c(p))| <= 4b l^2 }
has size at least |I|/2.
Choose an inclusion-maximal subset I_2 of I_1 whose endpoint pairs are
pairwise vertex-disjoint. Every demand in I_1 shares an endpoint with
a selected pair. The two vertices of a selected pair occur in at most
2k demands total, so
|I_2| >= |I_1| / (2k) >= |I| / (4k).
The endpoint count gives 2 |I| <= k r. Since |S| = |I_2| and selected
endpoints are distinct, |S| <= r / 2.
For each p in I_2 a small ball is chosen. Put
W_p = (Z_p union Y_(c(p))) minus {x_p, y_p},
P_p = (P - F) - W_p.
The first step deletes edges and the second deletes vertices. Both
endpoints survive. The load bounds give
|W_p| <= z + 4b l^2 <= 4(z + (k+b) l^2) <= h/16 <= h/4.
Set g = ceil(9 (r/h) log(2r)) and T = g(1 + ceil(log r)), an integer,
and l = 2T. If the radius-T balls about both x_p and y_p in P_p had
size greater than r/2, they would intersect. Joining their paths to an
intersection vertex gives an x_p-y_p walk of length at most 2T = l,
and deleting closed subwalks gives a simple path of no greater length.
It uses no edge of F and no vertex of W_p; its internal vertices lie
outside Z_p and outside Y_(c(p)). The hyperedge would be disjoint
from M, contradicting maximality.
For every p in I_2, therefore, one endpoint s_p has its radius-T ball
in P_p of size at most r/2. The roots s_p are distinct because the
selected pairs are disjoint. Write p(s) for the unique p with s = s_p.
Then
|{v : dist_(P_(p(s)))(s, v) <= T}| <= r/2 for every s in S.
The deleted-edge budget may be too large to grow a ball from one
root. First grow unions of balls, then alternate halving the root set
with further growth until one root remains. For nonempty A subset of
S and t >= 0, put
B_t(A) = union over s in A of
{v in V(P_(p(s))) : dist_(P_(p(s)))(s, v) <= t}.
Each forbidden set stays with its root. The claim is that
|B_(t+1)(A)| >= (1 + h/(2r)) |B_t(A)|
whenever 0 < |B_t(A)| <= r/2 and |F| <= h |B_t(A)| / 4.
Let B = B_t(A) and assign to each v in B a root s(v) in A that reaches
v within t steps in P_(p(s(v))). For a boundary edge vw of B, with v
in B and w outside B, the edge extends the path of v's assigned root
whenever vw is outside F and w is outside W_(p(s(v))). In that case
w belongs to B_(t+1)(A) minus B. Since P is simple, at most
|W_(p(s(v)))| <= h/4 boundary edges at v fail the second condition.
Cut expansion and the threshold leave at least
h|B| - (h/4)|B| - |F| >= (h/2)|B|
usable boundary edges. Each new vertex receives at most r such edges,
so at least h|B|/(2r) new vertices are reached.
Growth block. For every integer t >= 0,
if |B_t(A)| >= 1 and |F| <= h|B_t(A)|/4,
then |B_(t+g)(A)| > r/2.
If the starting union is already larger than r/2, monotonicity gives
the conclusion. Otherwise, if it were still at most r/2 after g
further steps, all intervening unions would remain at most r/2 and
the edge-deletion threshold would persist. Applying the growth bound
at all g steps,
|B_(t+g)(A)|
>= (1 + h/(2r))^g |B_t(A)|
>= 2^(gh/(4r)) |B_t(A)|
>= (2r)^2 |B_t(A)|
> r/2,
a contradiction. The middle inequality uses
log(1 + h/(2r)) >= h/(4r) and the fact that h <= r/4, and the last
uses g h/(4r) >= 2 log(2r) together with |B_t(A)| >= 1.
The roots are now thinned. Initially B_0(S) = S. The obstruction
budgets, the pair count, and the load condition give
|F| <= 2 l^2 |I| <= 8k l^2 |S| <= h|S|/4,
since h >= 64 k l^2 follows from the lemma hypothesis with b, z >= 0.
The growth block gives |B_g(S)| > r/2.
Suppose a nonempty set A has |B_t(A)| > r/2 and |A| >= 2. Partition A
into two nonempty subsets whose orders differ by at most one. Their
radius-t ball unions cover B_t(A), so one of them, say A', satisfies
|B_t(A')| > r/4. If |B_t(A')| > r/2, monotonicity gives
|B_(t+g)(A')| > r/2. Otherwise |B_t(A')| lies in (r/4, r/2] and the
threshold |F| <= h|B_t(A')|/4 also holds, because
|F| <= 8k l^2 |S| <= 8k l^2 (r/2) <= h r/16 <= h|B_t(A')|/4.
The growth block then gives |B_(t+g)(A')| > r/2.
Repeat with the surviving half of the roots, halving the root count
each round, until one root remains. This takes at most ceil(log r)
rounds. After the last halving, one more growth block brings the
total step count to at most
g * ceil(log r) + g = g(1 + ceil(log r)) = T.
So the last surviving root s has a radius-T ball in P_(p(s)) of size
greater than r/2, contradicting the small-ball property. Therefore
no set I can make the Aharoni-Haxell hypothesis fail, and the theorem
supplies pairwise disjoint representatives, proving the lemma.
Since h <= r/4 and r >= 2, the ceiling in g is absorbed, and
g <= 9 (r/h) log(2r) * (1 + 1/36),
log(2r) <= 2 log r,
1 + ceil(log r) <= 3 log r.
Combining, l = 2 g (1 + ceil(log r)) <= 108 (r/h) (log r)^2.
Three reservoirs of arbitrarily small fixed relative order serve to
close paths. Every edge has both endpoints outside at least one
reservoir. After reserving connecting edges, each remaining edge is
assigned to a complement that excludes one reservoir, the complement
is partitioned into paths, and the paths are closed through that
reservoir. The sampling lemma supplies the internal expansion needed
for these routes. Unused reserved edges go to single-edge parts. The
technique follows Conlon, Fox, and Sudakov, Section 3, and the closing
argument of Bucić and Montgomery, Section 2.2 and Lemma 23, adapted
to make the residuals have arbitrarily small total order.
Throughout the reservoir argument the order r satisfies
sigma <= r <= D^1.02 with sigma = D^0.90 and tau = D^0.74. All
assertions below are uniform over the graphs and orders in this range,
with thresholds that may depend on the fixed positive constants in the
statements.
Lemma (edge splitting). Fix c > 0 and a positive integer l. For all
sufficiently large D, if an r-vertex graph P has cut expansion at
least h_0 >= c D^0.90 and D^0.90 <= r <= D^1.02, then its edges can be
partitioned into l spanning subgraphs, each with cut expansion at least
h_0 / (2l).
Proof. Assign every edge independently and uniformly to one of l
classes. Fix a cut whose smaller side has size u >= 1 and let e be its
edge count in P. In any fixed class its size is binomial with mean
e/l >= h_0 u / l. By the Chernoff estimates, the probability that the
class has fewer than h_0 u / (2l) cut edges is at most
exp(-h_0 u / (8l)). There are at most 2 binom(r, u) <= 2 r^u choices
of cut with smaller side of size u. Thus the probability of any
failure is at most
2 l * sum from u = 1 to floor(r/2) of
(r exp(-h_0 / (8l)))^u = o(1).
Indeed h_0 >= c D^0.90 while log r <= 1.02 log D, so the base of this
geometric series tends to zero uniformly. A successful assignment
gives the required edge partition, each class taken on the full
vertex set of P.
Lemma (vertex sampling). Fix c' > 0 and p in (0,1). Let P have order
D^0.90 <= r <= D^1.02 and cut expansion at least h = c' D^0.90.
Select each vertex independently with probability p to form V'. With
probability 1 - o(1) as D -> infinity, all of the following hold:
|V'| <= 2pr,
|N_P(v) intersect V'| >= ph/2 for every v in V(P),
P[V'] has cut expansion at least tau = D^0.74.
The error term is uniform over the stated graphs and orders, with c'
and p fixed.
Proof. The minimum degree of P is at least h. The order bound and
the sampled-degree bounds fail with total probability at most
exp(-pr/3) + r exp(-ph/8) = o(1),
by the Chernoff estimates. The expansion assertion is proved by first
controlling a deterministic family of cuts, then approximating every
hypothetical failing sampled cut by a member of the family.
Deterministic witness family. In a failing sampled cut, the sampled
degree bound forces most vertices on the smaller side to have many
neighbors on that side. A small selection from that side can hit their
neighborhoods while exposing few vertices across the cut. This is why
unions of a small number of original neighborhoods are enumerated.
Set M = C_p log r with C_p = 16/p, and s = ceil(4rM/h). For
sufficiently large D, M/h < 1 and s <= r. Before sampling V', form
the family
U = { union over v in S of N_P(v) : S subset of V(P), |S| <= s }.
Its members are unions of open neighborhoods, and
|U| <= sum from t = 0 to s of binom(r, t)
<= (s+1) r^s
= exp(O((1 + rM/h) log r)).
Repeated neighborhood unions only decrease this count.
The claim is that, with probability 1 - o(1), for every U in the
family satisfying min{|U|, r - |U|} >= ph/8,
e_P(U intersect V', V' minus U) >= (p^2/4) |boundary_P U|.
Fix such a U and put e = |boundary_P U|. Expansion gives e >= ph^2/8.
Partition its cut edges into at most 2r matchings: greedily color the
cut edges, observing that an edge has fewer than 2r other cut edges
incident with its endpoints. Fix one such coloring for each cut before
sampling. The matching classes of size below e/(4r) contain fewer than
e/2 edges in total. In a remaining matching of size m, the indicators
that both endpoints of an edge lie in V' are independent, because its
edges have disjoint endpoints. Its retained size is binomial with mean
p^2 m. The probability of retaining fewer than p^2 m/2 edges is at most
exp(-p^2 m/8) <= exp(-p^2 e / (32r)) <= exp(-p^3 h^2 / (256r)).
When none of these matching events fails, the large classes retain at
least (p^2/2)(e/2) = p^2 e / 4 edges. Independence between different
matching classes, or between different cuts, is unnecessary: a union
bound controls the failure probability of the witness-cut bound by
2r |U| exp(-p^3 h^2 / (256r)) = o(1).
Uniformity uses the scale restrictions, which give
h^2 / r >= (c')^2 D^0.78,
r / h <= (c')^{-1} D^0.12,
M = O_p(log D).
The positive term in the exponent coming from |U| is
O_(p,c')(D^0.12 (log D)^2), while the negative term in the union
bound has magnitude at least a fixed positive multiple of D^0.78.
Approximating a failing cut. Fix an outcome satisfying the size and
degree bounds and the witness-cut bound. Suppose, for a contradiction,
that some A subset of V' satisfies
0 < a = |A| <= |V'|/2,
e_P(A, V' minus A) < tau a.
Take D large enough that tau < ph/4. If a <= ph/4, every vertex of
A has more than ph/4 neighbors in V' minus A, because its sampled
degree is at least ph/2 and it has at most a - 1 neighbors in A. This
contradicts the assumed bound, so a > ph/4.
Let A_good = {v in A : |N_P(v) intersect A| >= ph/4}. Each vertex
in A minus A_good has more than ph/4 neighbors across the sampled
cut, so
|A minus A_good| <= 4 tau a / (ph).
An auxiliary random choice now gives a set S subset of A. Include
each vertex of A independently with probability q = M/h. For every
v in A_good, the probability that S misses all its neighbors in A is
at most (1-q)^(ph/4) <= exp(-pM/4). The probability of any required
miss is therefore at most r exp(-pM/4) <= r^(-3) < 1/4. Also E|S| =
aM/h. If T(S) denotes the number of vertices of V' minus A with a
neighbor in S, then for each such vertex a union bound gives
E T(S) <= (M/h) sum over v in V' minus A of |N_P(v) intersect A|
= (M/h) e_P(A, V' minus A)
< tau M a / h.
Markov's inequality puts |S| > 4aM/h with probability at most 1/4,
and T(S) > 4 tau M a/h with probability at most 1/4. The sum of the
three failure probabilities is below one, so some S satisfies
|S| <= 4aM/h, T(S) <= 4 tau M a/h,
S intersect N_P(v) nonempty for every v in A_good.
The auxiliary choice is made after V' and A have been fixed; the
witness-cut bound holds for every possible resulting neighborhood
union.
Put U = union over v in S of N_P(v). Since |S| <= 4aM/h <= 4rM/h,
U lies in the family. The vertices of A absent from U are all
exceptional, and the vertices of U intersect V' outside A are counted
by T(S). Hence
delta := |(U intersect V') symmetric-difference A|
<= 4 tau a / (ph) + 4 tau M a / h
= O_p(tau M a / h) = o(a).
The last step uses tau M/h = O_(p,c')(D^-0.16 log D) = o(1).
Both sides of the cut in the original graph are large:
|U| >= |A| - delta = a - delta,
r - |U| >= |V' minus U| >= |V' minus A| - delta >= a - delta.
For large D these are at least a/2 > ph/8. The witness-cut bound
and the expansion of P therefore give
e_P(U intersect V', V' minus U) >= p^2 h a / 8.
On the other hand, changing the side of one vertex changes the size
of a cut in a simple r-vertex graph by at most r - 1. Changing the
delta vertices yields
e_P(U intersect V', V' minus U)
<= e_P(A, V' minus A) + r delta
< tau a + r delta.
The ratio of this upper bound to ha is at most
tau / h + O_p(tau M r / h^2)
= O_(p,c')(D^-0.16) + O_(p,c')(D^-0.04 log D) = o(1),
contradicting the lower bound. Therefore no such bad cut exists. With
the size and degree bounds and the witness-cut bound, the lemma is
proved.
All uses of o(1) above occur after p and c' have been fixed. An
arbitrarily small fixed positive sampling probability changes the
cutoff but not the strict exponent inequalities.
The next lemma starts from one expanding graph and leaves residual
graphs of arbitrarily small total order.
Lemma (small residue). Fix eta > 0 and c > 0. For all sufficiently
large D, let G be an r-vertex graph with D^0.90 <= r <= D^1.02
containing a spanning subgraph of cut expansion at least c D^0.90.
Then E(G) partitions into:
(a) at most 9r completed parts, each a simple cycle or a single edge;
(b) the edge sets of at most three residual simple graphs.
The residual graphs have pairwise disjoint vertex sets contained in
V(G), total order at most eta r, and each order strictly less than r.
Proof. Put c0 = min(c, 1), and fix
p = min{eta/12, 1/12},
h = (c0/6) sigma, sigma = D^0.90.
In particular 3p < 1, 6p <= eta, and 2p < 1.
Split the expanding edges. By the edge-splitting lemma with l = 3, the
edges of the spanning expanding subgraph can be partitioned into three
spanning subgraphs P1, P2, P3, each with cut expansion at least h,
because the original expansion is at least c D^0.90 >= c0 sigma = 6h
> 2 * 3 * h.
Choose the labels. Label each vertex independently as 1, 2, 3, or a
fourth label, with probabilities p for each of 1, 2, 3 and 1 - 3p for
the fourth. Let V_i be the vertices with label i. The three sets are
pairwise disjoint, and each marginal V_i is a Bernoulli-p sample of
the fixed graph P_i. Vertex sampling and a union bound over the three
marginals give a labeling such that, for each i,
|V_i| <= 2pr,
|N_{P_i}(v) intersect V_i| >= ph/2 for every v in V(G),
P_i[V_i] has cut expansion at least tau.
Independence between the three success events is not required. The
neighbor assertion makes V_i nonempty and gives every vertex of V_i
a neighbor in V_i, so |V_i| >= 2.
Reserve the connecting edges. For each i, reserve all edges
E_i^in = E(P_i[V_i]). Also reserve two edges from each v in
V(G) minus V_i to two distinct representatives in V_i. The
representatives can be chosen so that at most
k0 = ceil(8r/(ph))
of these edges are incident with any one vertex of V_i. Indeed,
process the two choices for every outside vertex in turn. At any
point fewer than 2r edges have been chosen, so the number of
representatives already at capacity k0 is at most 2r/k0 <= ph/4.
The sampling properties give at least ph/2 potential representatives
for the next choice. Excluding the saturated ones and, for the second
choice at a vertex, its first representative, leaves at least
ph/4 - 1 > 0 choices for large enough D. This greedy procedure
proves the claim. Write E_i^out for the selected
outside-to-representative edges.
For each i, the internal and outside reservations are disjoint.
Reservations for different i are also disjoint, because they belong to
the edge-disjoint graphs P_i. Let
E_res = union over i = 1, 2, 3 of (E_i^in union E_i^out).
Complementary path partitions. Every edge of E(G) minus E_res has
both endpoints outside at least one V_i, since its two endpoints meet
at most two of the three disjoint reservoirs. Assign each such edge
to one such index i, choosing just one index if several are
available. This gives edge-disjoint graphs G_i on V(G) minus V_i whose
edge sets partition all the nonreserved edges.
By the endpoint corollary, each G_i has an edge partition into
positive-length simple paths, with each vertex an endpoint at most
twice. Since each path has two endpoints, its path family P_i has size
at most |V(G) minus V_i| <= r. An empty edge set contributes no paths.
For each endpoint occurrence of v in P_i, assign one of its two
reserved edges in E_i^out, using different edges for different
occurrences. This is possible by the endpoint load bound. For a path Q
in P_i with distinct endpoints x and y, let x' and y' be their
assigned representatives in V_i. When x' is different from y', issue
one demand between them in P_i[V_i]. When x' = y', no routing demand
is necessary. Every demand-end occurrence uses a different reserved
edge at its representative, so the demand load at each vertex of V_i
is at most k0.
Routing and simple cycles. Apply the routing lemma separately in
each P_i[V_i], with expansion parameter tau, endpoint load k = k0,
singleton teams (b = 1), and empty forbidden set (z = 0). Verify the
numerical hypothesis using r_i = |V_i|. This graph has order at
least two and cut expansion at least tau, so tau <= r_i - 1. The
length l_i of the routing lemma satisfies
l_i = O((r/tau) (log r)^2),
k0 = O_(p,c)(r/h),
where the ceiling in k0 is absorbed because r/h >= 6. Hence
l_i^2 (k0 + 1)
= O_(p,c)((r^3/(tau^2 h)) (log r)^4)
= O_(p,c)(D^0.68 (log D)^4)
= o(D^0.74) = o(tau).
The routing condition therefore holds for large D, and the lemma
supplies pairwise edge-disjoint routing paths for the
distinct-representative demands in this reservoir. All their edges
lie in E_i^in.
For a path Q with x' different from y', join its endpoints by the
edge xx', the routing path from x' to y', and the edge y'y. Every new
internal vertex lies in V_i, while Q lies entirely outside V_i. The
resulting closed walk is a simple cycle. When x' = y', the two
reserved edges themselves form a simple two-edge connection from x to
y through that representative, closing Q to a simple cycle. The two
reserved edges are distinct because x is different from y. In this
case even a one-edge Q produces a triangle; with different
representatives the cycle has at least four edges. Every completed
cycle therefore has length at least three.
The cycles are edge-disjoint. Their original path edges partition the
nonreserved edges; each assigned representative edge is used once; and
the routing paths are edge-disjoint within each P_i[V_i]. These three
edge classes are disjoint by reservation, and reservations in
different P_i are edge-disjoint even when their cycles share vertices.
Counting and exact residuals. At most sum over i of |P_i| <= 3r
cycles have been produced. Take every unused edge of the union of
E_i^out as a single-edge part, using at most
sum over i of 2 |V(G) minus V_i| <= 6r
further parts. The completed parts total at most 9r.
For each i, let H_i be the graph on V_i consisting exactly of the
unused edges of E_i^in. These are the only remaining edges: every
nonreserved edge lies in a path, every reserved outside edge was
used in a cycle or taken singly, and every reserved internal edge was
used by a routing path or placed in H_i. In particular H_i is not the
graph of all remaining edges of the original induced graph G[V_i];
nonreserved edges with both endpoints in a reservoir were assigned to
the appropriate complementary graphs. This accounts for every
original edge exactly once.
The graphs H_i are simple, have pairwise disjoint vertex sets V_i,
and satisfy
sum over i of |V(H_i)| = sum over i of |V_i| <= 6pr <= eta r,
|V(H_i)| <= 2pr <= r/6 < r.
Isolated vertices may be retained; a residual graph with no edges may
be omitted. Only eta, c, and the constants determined from them were
fixed before increasing D.
Identifying pairs of vertices reduces the order of the graph to which
induction is applied. After setting aside loops and all but one edge
in each parallel class, each quotient edge has a unique original
representative. A quotient cycle may enter a pair at one member and
leave through the other; a reserved path joins them. Each such path
must avoid every representative endpoint internally and the paths of
one cycle must be pairwise disjoint. The next lemma bounds the edges
thrown away during the folding.
A degree bound at the paired vertices alone is insufficient. For
positive integers a and m with m even, pairing the m-vertex side of
K_(m,a) forces am/2 edges to be set aside, although each paired vertex
has degree a. The lemma therefore also bounds the number of neighbors
in each folding set at every vertex, including vertices outside those
sets.
Lemma (pair folding). Let J be a finite simple graph and X_1, ..., X_t
pairwise disjoint subsets of its vertex set. Suppose a >= 1, m_i =
|X_i| >= max{8, a^2} for every i, and
d_J(x) <= a for every x in the union of X_i,
d_i(v) = |N_J(v) intersect X_i| <= a
for every v in V(J) and every i.
Then there are pairings within the X_i, each leaving exactly m_i mod 2
vertices unpaired, and a set E_err of at most 2 sum over i of m_i edges
of J, such that identifying each pair in J - E_err gives a simple
graph Q. Every edge of Q has exactly one retained original edge as
its representative. Retaining all quotient vertices, including
isolated ones,
|V(Q)| = |V(J)| - sum over i of floor(m_i / 2).
The assertion also holds when the family of folding sets is empty.
Proof. When m_i is even, choose a uniform perfect pairing. When m_i
is odd, adjoin a dummy vertex, choose a uniform perfect pairing on the
m_i + 1 vertices, and delete the dummy and its pairing edge, leaving
its original partner unpaired. Each pairing with one unpaired original
vertex has exactly one extension of this kind, so the resulting
distribution is uniform. Make the choices for different i
independently.
For distinct specified vertices u, v of a set of order m, symmetry of
the partner of u gives the following exact probabilities. For two
prescribed disjoint pairs, conditioning on the first pair leaves a
uniform perfect pairing on the remaining vertices, including the
dummy when present. Hence
Pr({u,v} is a pair) = 1/(m-1) (m even)
= 1/m (m odd)
Pr(two prescribed disjoint pairs) = 1/((m-1)(m-3)) (m even)
= 1/(m(m-2)) (m odd).
The even-column expressions are valid upper bounds for both parities.
Let pi send each vertex to its fiber after the identifications. Each
fiber has size one or two. Before removing edges, let Z count the
original edges that become loops, plus the number of unordered pairs
of distinct original edges that become the same nonloop edge. The
expectation E Z is bounded by classifying all possible errors.
Loops and collisions with a common original endpoint. An original
edge becomes a loop exactly when its endpoints form a pair in some X_i.
There are at most a m_i/2 original edges inside X_i, so its expected
loop contribution is at most a m_i / (2(m_i - 1)).
Two distinct edges sharing an original endpoint have the form vu, vw
with u different from w. If they become the same nonloop edge, then
pi(u) = pi(w) is different from pi(v), so u, w are paired in some X_i.
No other identification is possible: identifying all three original
vertices would require a fiber of size at least three. The contribution
charged to X_i is at most
(1/(m_i - 1)) sum over v in V(J) of binom(d_i(v), 2)
<= a(a-1) m_i / (2(m_i - 1)).
The first step uses binom(d, 2) <= (a-1) d/2 for integers 0 <= d <= a,
and the second is the identity
sum over v in V(J) of d_i(v) = sum over x in X_i of d_J(x) <= a m_i,
which counts both incidences of every internal edge. Combining the
loop and common-endpoint bounds,
E Z_1 <= sum over i of a^2 m_i / (2(m_i - 1)) <= (4/7) sum over i of a^2,
since m_i >= 8.
Collisions with four distinct original endpoints. Write the two edges
as uv and xy with four different vertices. For them to become the same
nonloop edge, the two fibers are either {u,x}, {v,y} or {u,y}, {v,x}.
All four vertices lie in folding sets: a singleton fiber cannot contain
two distinct original endpoints. If both paired fibers lie in one X_i,
both original edges are internal to X_i. Writing e_i = |E(J[X_i])|,
there are at most binom(e_i, 2) <= e_i^2 / 2 vertex-disjoint edge pairs,
and the two possible pairing patterns give probability at most
2 / ((m_i - 1)(m_i - 3)). Since e_i <= a m_i / 2, the total contribution
is at most
sum over i of a^2 m_i^2 / (4(m_i - 1)(m_i - 3))
<= (16/35) sum over i of a^2.
The final inequality uses m_i / (m_i - 1) <= 8/7 and
m_i / (m_i - 3) <= 8/5.
If the two paired fibers lie in different sets X_i and X_j, both
original edges run between those sets. There is only one pairing
pattern, since each pair must remain within its own set. Put
e_ij = e_J(X_i, X_j); there are at most binom(e_ij, 2) <= e_ij^2 / 2
vertex-disjoint edge pairs. Independence between the two pairings and
the probability table bound this contribution by
sum over i < j of e_ij^2 / (2(m_i - 1)(m_j - 1))
<= (32/49) sum over i < j of e_ij^2 / (m_i m_j)
<= (16/49) sum over i of a^2.
The first step uses (m_i - 1)(m_j - 1) >= (49/64) m_i m_j; the second
step is the following. For fixed i,
sum over j not i of e_ij^2 / (m_i m_j)
<= (a / m_i) sum over j not i of e_ij <= a^2,
because e_ij <= a m_j and every x in X_i has total degree at most a.
Summing over i counts each unordered pair {i, j} twice. The three
cases exhaust the possible collisions between distinct original
edges, which either share an endpoint or have four distinct endpoints
in a simple graph.
Combining the three bounds,
E Z <= (4/7 + 16/35 + 16/49) sum over i of a^2
= (332/245) sum over i of a^2
<= (332/245) sum over i of m_i
< 2 sum over i of m_i,
when t > 0. Some choice of pairings has no greater error count than
its expectation. For this choice delete every original loop edge and,
in each nonloop parallel class of size s, delete all but one original
edge. The latter takes s - 1 <= binom(s, 2) deletions, so the number of
deleted edges is at most Z. The remaining graph is simple after
identification, and the retained representative in each class is
unique. Deletions do not remove vertices, giving the order formula. If
t = 0, use the identity map and delete no edges.
The next lemma resolves all batches inside a single earlier box. Its
hypotheses keep the degree bound global over all those batches.
Different batches may contain the same vertex and may pair it
differently; their original edge sets are disjoint.
Lemma (batch resolution). For every sufficiently large real D, set
a = D^0.01, L_0 = D^0.03, B_0 = D^0.30, sigma = D^0.90.
Let Y be a finite vertex set, W a finite indexed family of subsets
W of Y with |W| <= B_0, and J_W a simple graph on W for each index.
Suppose these graphs have pairwise disjoint edge sets, and let
F = F(Y) be their union, taken on Y.
Let R be a family of simple graphs on pairwise disjoint vertex
subsets of Y. Each R in R has order sigma <= r_R <= D^1.02, satisfies
E(R) intersect E(F) = empty, and has its edges partitioned into two
spanning graphs P_R and T_R, each of cut expansion at least sigma/4.
Call P_R the router.
For some pairs (W, R) let an active set X_{W,R} subset of W intersect
V(R) be specified, satisfying
|X_{W,R}| >= L_0, d_F(x) <= a for every x in X_{W,R}.
Sums over (W, R) below include only active sets; write
Sigma_Y = sum over (W, R) of |X_{W,R}|.
Then there are finite simple quotient graphs Q_W, with all quotient
vertices retained, whose orders satisfy
q_W = |W| - sum over active R of floor(|X_{W,R}|/2)
<= |W| - (1/3) sum over active R of |X_{W,R}| <= B_0,
sum over W of q_W <= sum over W of |W| - Sigma_Y/3.
For every choice of cycle-and-edge partitions of these Q_W, having
t_W parts, there are sets U_R subset of E(P_R) and a cycle-and-edge
partition of
E(F) union (disjoint union over R in R of U_R)
with at most
sum over W of t_W + 8 Sigma_Y
parts. The graphs R' = R - U_R, kept on V(R), contain the untouched
spanning graphs T_R, so each still has a spanning subgraph of cut
expansion at least sigma/4. The completed parts and these remaining
graphs partition E(F) union (disjoint union over R of E(R)). All
thresholds in the lemma are absolute.
Proof. The quotient graphs are chosen and some paths prepared before
any router edge is used. No router edge is used until all quotient
partitions have also been specified.
Removing edges to heavy neighbors. The path trimming below is the
elementary operation used by Conlon, Fox, and Sudakov, Lemma 6.3:
decompose a bipartite graph into paths and remove terminal edges so
that the remaining endpoints lie on one prescribed side. The endpoint
loads here are kept under a single degree bound on the union of all
batches.
Fix a batch W. Its active sets are pairwise disjoint because the
pieces R have disjoint vertex sets. For an active set X = X_{W,R}, put
H_X = {v in W : |N_(J_W)(v) intersect X| > a},
E_X = E_(J_W)(X, H_X).
Every vertex in any active set has degree at most a in J_W, since
J_W is a subgraph of F. Thus H_X is disjoint from every active set in
this batch, including X. If H_X is nonempty, counting edges gives
a |H_X| < |E_X| <= sum over x in X of d_(J_W)(x) <= a |X|;
in all cases |H_X| <= |X|. The sets E_X for different active X are
disjoint: each edge has one endpoint in its own active set and its
other endpoint outside every active set, so it cannot belong to the
set specified by a different active set.
By the endpoint corollary, the bipartite graph with parts X and H_X
and edge set E_X has a partition into at most |X| + |H_X| <= 2 |X|
positive-length simple paths, since their total number of endpoint
occurrences is at most 2(|X| + |H_X|). From each path delete its
terminal edge at each endpoint lying in H_X, counting those deleted
edges singly. At most two distinct edges are deleted. A one-edge
path has only one endpoint in H_X, and if both endpoints lie in H_X,
the path has at least two edges with distinct terminal edges.
Discard any remnant with no edges. Every other remnant is a simple
path with both endpoints in X: this follows by removing the H_X
endpoints from the alternating bipartite path. Its length is even and
at least two, so its endpoints are distinct. For each such remnant L,
record a demand between its endpoints in P_R, forbid the set
V(L) intersect V(R) internally, and give this demand its own team.
Once routed, the demand closes L into a cycle. Each original path
contributes at most two single edges and one cycle, at most 6 |X|
parts in total. The trimmed paths do not carry an endpoint-load-two
bound; their loads are later bounded through their incident original
edges in the global load argument.
Choosing the quotients. Remove all the sets E_X from J_W, retaining
the vertex set W, and call the resulting graph J_W^0. Each active
vertex still has degree at most a. For an active X and v in W, either
v lay in H_X, in which case all edges from v into X were removed, or v
originally had at most a neighbors in X. Either way,
|N_(J_W^0)(v) intersect X| <= a.
For large D, L_0 >= max{8, a^2}. Apply the pair folding lemma to J_W^0
and its active sets. Count its error edges singly in their original
form, and call the resulting simple quotient Q_W. Denote its quotient
map by pi_W; every edge e of Q_W has a unique retained original
representative e-hat. The number of these single-edge parts is at most
2 sum over R of |X_{W,R}|.
Every identified pair removes exactly one vertex. Since
floor(m/2) >= m/3 for every integer m >= 2, the exact order formula
from the folding lemma gives
q_W <= |W| - (1/3) sum over active R of |X_{W,R}| <= B_0,
and summing gives the total quotient bound. The construction of all
Q_W is independent of their subsequent partitions.
Switch demands of a quotient cycle. Now fix arbitrary
cycle-and-edge partitions of all the Q_W. Restore each single-edge
part as its unique original representative. For a cycle C in Q_W,
list its distinct vertices in cyclic order as z_1, ..., z_s with
s >= 3, and write e_j = z_j z_{j+1} with indices taken cyclically. At
z_j let u_j be the endpoint of the representative of e_{j-1} in the
fiber of pi_W over z_j, and let v_j be the endpoint of the
representative of e_j in that fiber. If u_j = v_j, the two edges join
without any added path. Otherwise the fiber is a folded pair
{u_j, v_j} inside one active set X_{W,R}; record a demand from u_j to
v_j in P_R.
For every demand from this cycle, forbid internally
Z_C intersect V(R), Z_C = union over j of V(representative of e_j).
Every original endpoint on the entire cycle, including the endpoints
of all its other switches, is therefore forbidden internally. The
demands in this cycle and this router form one team. Teams for
different cycles, including cycles from different batch indices, are
distinct. The single-demand teams from the heavy-neighbor construction
are also distinct from these teams.
Load bound over all batches. Fix one piece R. Gather every demand for
P_R from all batches and both constructions. Each endpoint lies in an
active set, and hence has degree at most a in the single graph F(Y).
Each occurrence of an endpoint x is associated with an incident edge
of F(Y) as follows. For the demand closing a remnant L, use the
terminal edge of L at x. At a switch u_j different from v_j, associate
the occurrence of u_j with the representative of e_{j-1}, and that of
v_j with the representative of e_j.
At a fixed vertex these associated incident edges are distinct. For
the first construction this follows from the edge-disjoint path
partition and from the disjointness of the designated edge sets. For
the second construction a quotient edge belongs to exactly one part,
has exactly one original representative, and its incidence at a given
original vertex can occur only at the unique visit to its quotient
fiber in that cycle. Cycles are simple, and a switch uses different
original vertices for its two incidences. The two constructions use
disjoint edges because all designated edges were removed before
folding. Edges from different batches are distinct by hypothesis,
regardless of overlap among their vertex sets or differences in their
pairings. This injection into incident edges of F(Y) proves
number of demand-end occurrences at x <= d_(F(Y))(x) <= a.
Vertices that are never endpoints have load zero.
Supplying the connections. A team from a cycle C has at most
s <= q_W <= B_0 demands, and |Z_C| <= 2s <= 2B_0. A heavy-neighbor
remnant has at most |W| <= B_0 vertices; its team has size one. Thus
in the routing lemma use
r = r_R, h = sigma/4, k = a, b = B_0, z = 2B_0.
With the routing lemma's definition of l, the range
sigma <= r_R <= D^1.02 gives, uniformly in R,
l = O(D^0.12 log^2 D),
l^2 (a + B_0) + 2B_0 = O(D^0.54 log^4 D) = o(D^0.90).
For all sufficiently large D this is at most sigma/256 = h/64, which
is exactly enough for the routing condition. Apply the routing lemma
once to this full collection in P_R; if the collection is empty, use
no edges. The paths supplied are pairwise edge-disjoint over all teams
and all batches for this R, and their internal vertex sets are
pairwise disjoint within each team. This is done for every piece R.
The constants are absolute, independent of the number of batches or
demands.
Simplicity of completed cycles. For a heavy-neighbor remnant L, its
supplied path is simple with distinct endpoints equal to those of L.
Its internal vertices avoid V(L): the forbidden set contains
V(L) intersect V(R), and supplied path vertices lie in V(R). The union
is therefore a simple cycle. It has at least two remnant edges and at
least one supplying edge, so its length is at least three.
For a quotient cycle C, the fibers of z_1, ..., z_s are mutually
disjoint. At a visit with u_j = v_j, the original representative edges
use one vertex. At a switch, they use the two different vertices of
that fiber, and the supplied simple path joins them. Thus before
adding path interiors, vertices at different visits are distinct.
Every supplying path interior avoids Z_C, which contains all these
original vertices. Two supplying paths for this cycle in the same
router have disjoint interiors by their common team; paths in
different routers lie in the disjoint vertex sets of different pieces
R. Consequently interiors of any two switches are disjoint, and none
contains an endpoint of another switch or any other original vertex
used by the cycle. Traversing the representatives and these
connections in cyclic order therefore visits no vertex twice, except
the start when closing the cycle.
An unused twin needs explicit mention. If a visited fiber is a pair
but u_j = v_j, its other vertex need not lie in Z_C and may occur
inside a supplying path. It is absent from all original representative
edges of the cycle, since those edges use distinct fibers. If it is
used internally, no second supplying path of this cycle can use it:
the team condition forbids this in its router, and other routers have
disjoint vertex sets. This creates no repeated vertex. The same
reasoning covers vertices in fibers not visited by the cycle.
The resulting cycle contains its s distinct original representative
edges and possibly additional edges, so its length is at least
s >= 3. A quotient cycle with no switches is already a simple cycle
of original edges. Each quotient part therefore yields exactly one
permitted part.
Edge accounting and cost. For each batch, its original edges have
exactly four destinations: designated edges trimmed from paths are
single-edge parts; designated edges in positive-length remnants occur
in their closed cycles; folding error edges are single-edge parts,
taken before identification; retained edges have unique
representatives in Q_W and occur once in the restored quotient parts.
These classes partition E(J_W). Empty remnants leave no unaccounted
edge, and the deletion rule for parallel classes retains exactly one
representative for each quotient edge. Since the J_W have disjoint
edge sets, every edge of F occurs once in this list over all batches.
Let U_R be the set of edges used by all supplying paths in P_R. Each
is used once by the routing lemma. These edges are disjoint from E(F)
by hypothesis, and different routers have disjoint edge sets. Thus
all completed parts form an edge partition of the stated edge set.
The heavy-neighbor work contributes at most 6 Sigma_Y parts, folding
errors at most 2 Sigma_Y, and the quotient partitions contribute
exactly sum over W of t_W. Adding a supplying path changes no part
count. This proves the bound.
No edge of T_R is used: U_R is a subset of E(P_R), and E(P_R) is
disjoint from E(T_R). Therefore R' = R - U_R contains the entire
spanning graph T_R on its original vertex set. The edges of R' are
precisely the edges of this piece not already used in a completed
part. This proves both the remaining expansion assertion and the
final edge partition.
The base case is immediate. Edgeless graphs have the empty partition.
For 1 <= n < D_*, put every edge in its own part, using at most
n - 1 <= D_* n parts; since phi(n) >= 1/2, a constant C >= D_*
covers this. Now let n >= D_*, assume the proposition for every
smaller positive order, and put D_j = n^(theta^j) and
m = min{j >= 0 : D_j < D_*}. Take D_* > 2. Then m is finite and
positive, and the scales D_0, ..., D_(m-1) all exceed the cutoff.
Terminal cases. If every S_j vanishes, keep every prospective stage.
Use the long cycles as completed parts and take all remaining edges
singly. The remaining graphs lie on the level-(m-1) boxes and have
average degree at most D_m < D_*, so their total number of edges is
at most N_(m-1) D_m / 2 < D_* n. The number of long cycles removed
through all levels is at most 20n/log D_(m-1) <= 20n. This case costs
at most (20 + D_*) n parts.
Otherwise choose i by the prefix-selection lemma. If i + K >= m - 1,
keep every stage again. Retain all long cycles as completed parts and
take every edge of the final boundary graphs singly, at the same cost
(20 + D_*) n. The zero extension of (S_j) ensures
sum over j = 0 to m-1 of S_j <= P0 S_i.
Apply the small-residue lemma to each piece at its own scale, with
c = 1 and the fixed eta. This completes at most 9 P0 S_i parts and
leaves graphs of total order at most
eta P0 S_i = S_i/100 <= n/50 < n/4.
Each individual residual graph has order at most eta r < n, where r is
the order of its parent piece: the piece lies in V(G), so r <= n, and
eta < 1. By induction, the total additional cost is at most C n/4,
using phi <= 1.
Both terminal cases are therefore covered by
T(D_*) n + C n / 4, T(D_*) = 20 + D_* + 18 P0.
For C >= 4 T(D_*), this is at most C n/2 <= C phi(n) n, and the same
choice covers the base cases.
A prefix with a scale gap. It remains to consider i + K < m - 1.
Keep the stages through t = i + K, and put
D = D_i, w = log D, H = C2 theta^(-K),
B0 = D^0.30, a = D^0.01, L0 = D^0.03, sigma = D^0.90.
Since log D_t = theta^K w, the layer bounds give
N_t <= (1 + H/w) n, |L_t| <= H n / w.
The second uses C2 >= 40 > 20.
Fix a level-i box Y of order y <= D^1.02. Let T_Y be the sum of the
orders of its level-t descendants. Each such descendant carries its
remaining graph after stage t; it has order at most
D^(1.02 theta^K) < D^0.001 and that graph has average degree at most
D^(theta^(K+1)). Also
y <= T_Y <= (1 + H/w) y <= 2y,
since H/w = C2 / log D_t <= 1.
Let F(Y) be the graph on Y whose edges are exactly the remaining
edges in these descendants. Their assigned edge sets are disjoint, so
F(Y) is simple and
2 |E(F(Y))| <= T_Y D^(theta^(K+1)) <= 2y D^(theta^(K+1)).
Batches. Each descendant has fewer than L0 vertices, so descendants
are first grouped into larger folding sets. The number of batches
bounds the loss when an intersection of a batch with a selected piece
contains fewer than L0 vertices of degree at most a in F(Y). The batch
order cap B0 keeps quotient cycles within the routing team bound.
Partition the indexed descendants into batches whose order sums are
at most B0. This takes at most 1 + 4y/B0 batches. Require the cutoff
to ensure D^0.001 <= B0/2, fill a batch until the next descendant
would exceed B0, then start a new one. Every batch except possibly
the last has order sum above B0/2, so their number is at most
1 + 2 T_Y / B0.
For each batch let W be the union of its vertex sets, and let J_W
contain exactly its remaining assigned edges. The batch index is
retained. Denote the family by W(Y). Thus the J_W partition E(F(Y)),
the sets W cover Y, and
|W| <= B0, sum over W of |W| <= T_Y,
sum over Y and W of |W| <= N_t.
The order sums used in forming batches include all descendant
multiplicities; passing to a union within a batch can only decrease
them.
Since each level-t box has a unique indexed level-i ancestor, the
batch edge sets over all Y partition the boundary remainder. At the
boundary of the committed prefix, the assigned edge sets give the
disjoint union
E(G) =
disjoint union over L in L_t of E(L)
disjoint union
disjoint union over j = 0 to t of
disjoint union over R in R_j of E(R)
disjoint union
disjoint union over Y and W of E(J_W).
Active sets. Call a vertex of Y good if its degree in F(Y) is at most
a. By the degree bound on F(Y) and the scale window, the number of
other vertices is at most
2 y D^(theta^(K+1) - 0.01) <= 2y D^-0.009 <= y/w,
where the final inequality is another uniform large-scale requirement.
For each W in W(Y) and each level-i piece R belonging to Y, take all
good vertices of W intersect V(R). If their number is at least L0,
keep this set as X_{W,R} and call it active; otherwise skip it. Active
sets in a fixed batch are disjoint, since the pieces in Y are
vertex-disjoint.
There are at most y/sigma pieces. The total size of all skipped sets
in Y, counting occurrences in different batches separately, is at
most
L0 (1 + 4y/B0) y/sigma <= y (D^-0.87 + 4 D^-0.15) <= y/w.
The exponent -0.15 uses y <= D^1.02, and the last inequality is
imposed for every scale above the cutoff.
Let s(Y) be the sum of the orders of the level-i pieces in Y, and
define
Sigma_Y = sum over active (W, R) with W in W(Y) and R in Y
of |X_{W,R}|,
Sigma = sum over Y of Sigma_Y.
Every good piece vertex occurs in at least one batch, since the
batches cover Y. Choose one such occurrence per vertex. At most y/w
piece vertices are not good, and at most y/w chosen occurrences lie in
skipped sets, so Sigma_Y >= s(Y) - 2y/w.
For the upper bound, let u_Y(v) >= 1 be the number of batches in Y
containing v. Then
sum over v in Y of (u_Y(v) - 1) = sum over W of |W| - y.
Since the pieces in Y are vertex-disjoint, their excess occurrences
are bounded by this full excess, giving
Sigma_Y <= s(Y) + sum over W of |W| - y. Summing the two bounds,
using N_i <= 2n, N_i >= n, and the gap and batch bounds,
S_i - 4n/w <= Sigma <= S_i + N_t - N_i <= S_i + H n/w.
A nongood vertex is counted only once per indexed box in the lower
bound; overlaps between boxes are already inside both S_i and N_i.
Resolving batches and pieces. In every level-i piece R, apply the
edge-splitting lemma with two classes to partition its assigned edges
into spanning graphs P_R and T_R, each with cut expansion at least
sigma/4. Reserve P_R as a router; leave T_R untouched during the batch
work.
All hypotheses of the batch-resolution lemma now hold in each Y. The
J_W have order at most B0 and disjoint assigned edges; their union is
F(Y). The pieces have orders between sigma and D^1.02, disjoint vertex
sets inside Y, and edges disjoint from F(Y). Every vertex of an active
X_{W,R} has degree at most a in the whole F(Y), and its active set has
order at least L0. The degree bound is shared across all batches.
The lemma produces simple quotient graphs Q_W with orders
q_W = |W| - sum over active R of floor(|X_{W,R}|/2)
<= |W| - (1/3) sum over active R of |X_{W,R}|.
Every batch has positive order and pair identifications leave at least
one vertex, so 1 <= q_W <= B0. Also B0 = D^0.30 <= n^0.30 < n. Apply
the induction hypothesis to the quotients, retaining isolated
quotient vertices in their order counts. The batch lemma lifts all the
resulting quotient parts simultaneously. In each Y, the additional
number of completed parts is at most 8 Sigma_Y, and the remaining
graph on each R still contains T_R. In particular, lifting a quotient
cycle produces one simple cycle and has no additional part charge.
Apply the small-residue lemma, with the fixed eta, to the remaining
graph of every level-i piece using c = 1/4. Apply it to every other
piece of the committed prefix at its own scale using c = 1. The total
number of parts supplied by these applications is at most 9 P0 S_i.
If H is their family of residual graphs, then
sum over H in H of |V(H)| <= eta sum over j = 0 to t of S_j
<= eta P0 S_i.
Every nonempty member has order at most eta r < n, for the same reason
as in the terminal case, and induction applies to all of them.
Within each Y, the batch-resolution lemma resolves exactly the batch
category of the ledger together with the router edges it consumes.
Every consumed router edge comes from exactly one level-i piece and is
used once. The piece lemmas are applied only after those edges have
been removed, and partition all the remaining piece edges into
completed parts and members of H. Distinct indexed boxes have disjoint
assigned edge sets even when their vertex sets overlap. The only
unresolved original edges after lifting the quotient partitions are
the assigned edges of H, each appearing once. Partitioning them
recursively completes an edge partition of G.
Order savings and the final estimate. Define the absolute constants
A1 = H + 4/3, A2 = max{9 P0 + 8, 9H}.
By the quotient order formula, the batch order bound, and the active
order bound,
sum over Y and W of q_W
<= N_t - Sigma/3
<= n - S_i/3 + A1 n/w.
The parts completed apart from the quotient partitions and the
recursive work on H number at most
|L_t| + 8 Sigma + 9 P0 S_i
<= (9 P0 + 8) S_i + 9H n/w
<= A2 (S_i + n/w).
Monotonicity of phi, q_W <= B0, and the piece-residual order bound
therefore bound the complete partition size by
A2 (S_i + n/w) + C eta P0 S_i
+ C phi(B0) (n - S_i/3 + A1 n/w).
The coefficient of S_i in this expression is at most
A2 + C/100 - C/6 = A2 - 47C/300 <= 0
when C >= 7 A2, since 47 * 7 / 300 = 329/300 > 1.
Paying for the overlap. Set delta = 1/sqrt(0.30) - 1 > 0. For
w >= 40/3, both phi(n) and phi(B0) take their nonconstant values, and
log n >= w gives
phi(n) - phi(B0)
= 1/sqrt(0.30 w) - 1/sqrt(log n)
>= delta / sqrt(w).
For C >= 7 A2, the remaining overhead beyond C phi(B0) n is at most
C (A1 + 1) n/w. This is absorbed by the potential gain whenever
log D_* >= ((A1 + 1) / delta)^2.
No step requires the total quotient order to be at most n; the
potential gain pays for any excess.
Order of constant choices. The parameters theta, K, P0, eta, the
scale-split constant C0 >= 1, and hence C2, H, A1, A2, delta, are
already absolute and fixed. Choose D_* large enough for the
splitting, batch-resolution, and edge-splitting lemmas with two
classes at expansion D^0.90, and for the small-residue lemma with the
fixed eta and c in {1, 1/4}. Also impose log D_* >= max{C2, 40/3},
the absorption inequality written above, and, for every D >= D_*,
D^-0.01 <= 1/log D,
D^0.001 <= B0/2 = (1/2) D^0.30,
2 D^-0.009 <= 1/log D,
D^-0.87 + 4 D^-0.15 <= 1/log D.
These are uniform eventual inequalities between fixed powers and
logarithms, so such a cutoff exists independently of C. After fixing
it, choose
C >= max{7 A2, 4 T(D_*)}.
The base and terminal cases then hold, and the cost expression gives
at most C phi(n) n parts in the remaining case. This closes the strong
induction.
Since phi(n) <= 1, the proposition proves the theorem for positive
order, and the zero-vertex graph has the empty partition. This
completes the proof.