A linear cycle-and-edge decomposition of every graph

Proof. For the first claim, let the partition from Theorem 1.1 have r cycle parts and s single-edge parts, with r+s\le Cn. The graph formed by the latter edges has even degrees, since deleting cycles preserves degree parity. Repeatedly removing a cycle preserves this property and ends with no edges: every even graph with an edge contains a cycle. This uses at most s cycles, for a total of at most r+s\le Cn. The equivalence of this O(n) Eulerian cycle bound with the Erdős–Gallai conjecture is recorded in [7, Section 1.1].

The partition-cut condition in the second claim is exactly the weakly-(\eps,p)-quasirandom condition of [7, Section 1.2]. Their Proposition 6.3 proves that Conjecture 1.14, the stated bound with these quantifiers, is equivalent to their Erdős–Gallai Conjecture 1.4, supplied by Theorem 1.1.□

Proof. For n=0 there is nothing to prove. Otherwise add a vertex v_0 and join it to precisely the even-degree vertices of the original graph, including the isolated vertices. Every old vertex now has odd degree. In a path-and-cycle partition its number of path-endpoint occurrences must therefore be odd and positive.

Apply Theorem 2.1 to the augmented graph, and let p be the number of path parts. The old vertices force 2p\ge n, whereas the theorem gives

Thus every part is a path. Each old vertex is an endpoint exactly once: an old vertex with at least three endpoint occurrences, together with the other old vertices, would force at least n+2 occurrences, although 2p\le n+1.

Delete v_0 from these paths and discard 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 and have endpoint load at most two. Each positive-length path contributes two endpoint occurrences, proving the final count.□

Proof. For X a sum of independent Bernoulli variables, \E e^{tX}\le\exp(\mu(e^t-1)). Apply Markov’s inequality with t=-\ln2 for the lower tail and t=\ln2 for the upper tail. The resulting exponents are -\mu(1-\ln2)/2 and -\mu(2\ln2-1), respectively. They are at most -\mu/8 and -\mu/3.□

Proof. There is nothing to prove when \mathcal D is empty. Suppose it is nonempty, and write c(p) for the team of demand p.

A hypergraph obstruction. Take a resource set that is the tagged disjoint union of E(P) and the tokens (v,c), where v\in V(P) and c is a team. For each demand p, form a hypergraph \mathcal H_p on this resource set. Its hyperedges correspond to all simple x_p–y_p paths of length at most \ell whose internal vertices avoid Z_p. A candidate path contributes its graph edges and the token (v,c(p)) for each of its internal vertices. A path of length t\ge 1 therefore contributes 2t-1\le 2\ell resources. In particular all hyperedges are nonempty, and all the hypergraphs are finite. A choice of pairwise disjoint representatives from the \mathcal H_p gives exactly the three required properties.

We verify the sufficient condition of Theorem 2.3 with s=2\ell. Suppose, for a contradiction, that it fails for a nonempty I\subseteq\mathcal D. Let \mathcal M be a maximum matching in \bigcup_{p\in I}\mathcal H_p. Then \abs{\mathcal M}\le 2\ell(\abs I-1). Let F\subseteq E(P) be the graph-edge resources used by \mathcal M, and put

Each matching member uses at most \ell graph edges and at most \ell tokens, so

These estimates allow several matching members to come from one demand; no restriction on their demand indices is being imposed.

For each team let m_c=\abs{\{p\in I:c(p)=c\}}\le b. Thus

Consequently the set I_1=\{p\in I:\abs{Y_{c(p)}}\le 4b\ell^2\} has size at least \abs I/2. Choose an inclusion-maximal set I_2\subseteq I_1 whose endpoint pairs are pairwise vertex-disjoint. Every demand in I_1 meets one of these selected pairs. The two vertices of any selected pair occur in at most 2k demands in total, so

We will also use the global endpoint count

A small ball for each selected demand. For p\in I_2, define

Here the first deletion removes edges and the second removes vertices. Both endpoints remain in P_p. By (3.2),

Set T=\ell/2=g(1+\ceil{\log r}), an integer. If the balls of radius T 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=\ell; 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 are also different from x_p,y_p, and hence avoid both Z_p and Y_{c(p)}. Its hyperedge in \mathcal H_p is therefore disjoint from \mathcal M, contrary to maximality of that matching.

For every p\in I_2 we may consequently choose an endpoint s_p whose radius-T ball in P_p has size at most r/2. Let S=\{s_p:p\in I_2\}. These roots are distinct because the selected endpoint pairs are disjoint. Each root retains its demand label: write p(s) for the unique p\in I_2 with s=s_p. In particular,

Growth with different forbidden sets. The deleted-edge budget may be too large to grow a ball from one root. We first grow unions of balls, retaining each root’s graph, and then alternate halving the root set with further growth until one root remains. For a nonempty A\subseteq S and an integer t\ge 0, put

These are unions of balls in their respective graphs; the forbidden set is kept with its root throughout. We claim that

whenever

To prove this, let B=B_t(A) and assign to each v\in B one root s(v)\in A that reaches v within t steps in P_{p(s(v))}. Consider a boundary edge vw of B, with v\in B and w\notin B. It extends this particular root’s path whenever vw\notin F and w\notin W_{p(s(v))}. In that event w\in B_{t+1}(A)\setminus B. Because P is simple, at most \abs{W_{p(s(v))}}\le h/4 boundary edges at v fail the latter condition. Cut expansion and (3.9) therefore leave at least

usable boundary edges. Each new vertex receives at most r such edges. Thus at least h\abs B/(2r) new vertices are reached, proving (3.8).

It follows that, for every integer t\ge 0,

Indeed, the conclusion is immediate by monotonicity if the starting union already has size greater than r/2. Otherwise, if it still had size at most r/2 after g more steps, all intervening unions would have size at most r/2, while their monotonicity would preserve the edge-deletion threshold. We could apply (3.8) at all g steps. Singleton cuts in the simple graph P give 0<h\le r-1<r, and the elementary inequality \log(1+h/(2r))\ge h/(4r) then yields

a contradiction. This also verifies the growth time with the ceiling in the definition of g.

Restarting after halving the roots. Initially B_0(S)=S. By (3.3), (3.4), and (3.2),

The growth block (3.10) gives \abs{B_g(S)}>r/2.

Suppose now that a nonempty root set A has \abs{B_t(A)}>r/2 and \abs A\ge 2. Partition A into two nonempty sets whose sizes differ by at most one. Their radius-t ball unions together cover B_t(A), so one of them, say A', satisfies

The original matching has a bound independent of the number of retained roots: by (3.3), (3.5), and (3.2),

Thus another growth block gives \abs{B_{t+g}(A')}>r/2.

Start with A=S at radius g and repeat this operation until only one root remains. After j halvings the number of roots is at most \ceil{\abs S/2^j}; this follows inductively from rounding each half upward. Hence at most \ceil{\log\abs S} halvings are needed, including zero if \abs S=1. At termination a single root has a ball larger than r/2 at an integer radius at most

This contradicts (3.7) and monotonicity of that root’s balls.

There is therefore no set I for which the matching condition fails. Applying Theorem 2.3 gives disjoint hypergraph representatives, and their paths prove the lemma.□

Proof. Assign each edge independently and uniformly to one of l classes. Fix a cut whose smaller side has size u\ge1, and let e be its number of edges in P. In any fixed class its size is binomial with mean e/l\ge h_0u/l. By Lemma 2.4, the probability that this class has fewer than h_0u/(2l) cut edges is at most

There are at most 2\binom ru\le2r^u choices of a cut with smaller side of size u. Thus the probability of any failure is at most

Indeed, h_0\ge cD^{0.90} while \log r\le1.02\log D, so the base of this geometric sum tends to zero uniformly. A successful assignment gives the required edge partition. Each class is taken on the full vertex set of P.□

Proof. The minimum degree of P is at least h. The order bound and all the sampled-degree bounds fail with total probability at most

by Lemma 2.4. We prove the expansion assertion by first controlling a deterministic family of cuts and then approximating any hypothetical failing sampled cut by a member of that family.

A 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 we enumerate unions of a small number of original neighborhoods. Set

For sufficiently large D, we have M/h<1 and s\le r. Before sampling V', form the family

Its members are unions of open neighborhoods in the original graph, and its size satisfies

Repeated neighborhood unions only decrease this count.

We claim that, with probability 1-o(1), simultaneously for every U\in\mathcal U satisfying \min\{|U|,r-|U|\}\ge ph/8, one has

Fix such a U, and put e=|\partial_P U|. Expansion gives e\ge 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 edges incident with its endpoints. Fix one such coloring for each cut before sampling. The matching classes of size less than 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 belong to V' are independent, since its edges have disjoint endpoints. Its retained size is therefore binomial with mean p^2m. The probability of retaining fewer than p^2m/2 edges is at most

When none of these matching events fails, the large classes retain at least (p^2/2)(e/2)=p^2e/4 edges. Independence between different matching classes or between different cuts is unnecessary: a union bound bounds the probability of any failure of (4.4) by

To verify this uniformly, the scale restrictions give

Consequently the positive term in the exponent coming from (4.3) is O_{p,c'}(D^{0.12}(\log D)^2), while the negative term in (4.5) 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 all of (4.4). Suppose, for a contradiction, that some A\subseteq V' satisfies

We may assume D is large enough that \tau<ph/4. If a\le ph/4, every vertex of A has more than ph/4 neighbors in V'\setminus A, because its sampled degree is at least ph/2 and it has at most a-1 neighbors in A. This contradicts (4.6). Thus

Let

Each vertex in A\setminus A_{\mathrm{good}} has more than ph/4 neighbors across the sampled cut. Hence

We now make a separate auxiliary random choice solely to prove the existence of a suitable set S\subseteq A. Include each vertex of A independently with probability q=M/h. For every v\in A_{\mathrm{good}}, the probability that S misses all its neighbors in A is at most

Thus the probability of any required miss is at most r\exp(-pM/4)\le r^{-3}<1/4. Here the chosen value of C_p is more than sufficient, since all logarithms are base two. Also \E|S|=aM/h. If T(S) denotes the number of vertices of V'\setminus A with a neighbor in S, then a union bound for each such vertex gives

Markov’s inequality shows that each of the events |S|>4aM/h and T(S)>4\tau Ma/h has probability at most 1/4. The sum of these three failure probabilities is less than one. We can therefore choose S satisfying all three desired properties:

The auxiliary choice is made after V' and A have been fixed; the uniform event (4.4) was already established for every possible resulting neighborhood union.

Put U=\bigcup_{v\in S}N_P(v). Since |S|\le4aM/h\le4rM/h, we have U\in\mathcal U. The vertices of A absent from U are all exceptional in (4.8), and the vertices of U\cap V' outside A are counted by T(S). Consequently

In the last step we used \tau M/h=O_{p,c'}(D^{-0.16}\log D)=o(1). Both sides of the cut in the original graph are large:

For sufficiently large D, these are at least a/2>ph/8. Applying (4.4) and the expansion of P therefore gives

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 in (4.10) yields

The ratio of this upper bound to ha is at most

contradicting (4.11). Thus no cut (4.6) exists. Together with (4.2) and (4.5), this proves the lemma.

All uses of o(1) above occur after p and c' have been fixed. In particular, an arbitrarily small fixed positive sampling probability changes the cutoff but does not change any of the strict exponent inequalities.□

Proof. Write c_0=\min\{c,1\}, and fix

In particular, 3p<1, 6p\le\eta, and 2p<1. By Lemma 4.1, the edges of the given spanning expanding subgraph can be partitioned into three spanning subgraphs P_1,P_2,P_3, each of cut expansion at least h.

Disjoint reservoirs and bounded representative loads. Label the vertices independently, using each label i\in\{1,2,3\} with probability p and a fourth label with probability 1-3p. Let V_i be the vertices with label i. These three sets are pairwise disjoint, and each marginal V_i is a Bernoulli-p sample for the fixed graph P_i. By Lemma 4.2 and a union bound over the three marginal failure probabilities, we can choose the labels so that, for each i,

Independence between these 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|\ge2.

For each i, reserve all edges E_i^{\mathrm{in}}=E(P_i[V_i]). Also reserve two edges from each v\in V(G)\setminus V_i to two distinct representatives in V_i. The representatives can be chosen so that at most

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 k_0 is at most 2r/k_0\le ph/4. There are at least ph/2 potential representatives for the next choice by (4.13). Excluding the saturated ones and, for the second choice at a vertex, its first representative, leaves at least ph/4-1>0 choices for sufficiently large D. This greedy procedure proves the claim. Denote the selected outside-to-representative edges by E_i^{\mathrm{out}}.

For a fixed i, the internal and outside reservations are disjoint. Reservations for different values of i also have disjoint edge sets, because they belong to the edge-disjoint graphs P_i. Let

be the entire reserved edge set.

The complementary path partitions. Every edge in E(G)\setminus E_{\mathrm{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)\setminus V_i whose edge sets partition all nonreserved edges. By Corollary 2.2, each G_i has a partition into positive-length simple paths, with each vertex an endpoint at most twice. Since each path has two endpoint occurrences, its path family \mathcal P_i has size at most |V(G)\setminus V_i|\le r. An empty edge set contributes no paths.

For each endpoint occurrence of v in \mathcal P_i, assign one of its two reserved edges in E_i^{\mathrm{out}}, using different edges for different occurrences. This is possible by the endpoint load bound. For a path Q\in\mathcal P_i with distinct endpoints x,y, let x',y'\in V_i be their assigned representatives. When x'\ne 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. Hence the total demand load at each vertex of V_i is at most k_0.

Routing and simple cycles. Apply Lemma 3.1 separately in each P_i[V_i], with expansion parameter \tau, endpoint load k=k_0, singleton teams (b=1), and no forbidden vertices (z=0). We check its numerical hypothesis using the actual order r_i=|V_i|. This graph has order at least two and cut expansion at least \tau, and therefore \tau\le r_i-1. The value \ell_i in Lemma 3.1 satisfies

Here the ceiling in (4.14) is absorbed because r/h\ge6. Consequently

Thus (3.2) holds for all sufficiently large D. The lemma supplies pairwise edge-disjoint simple routing paths for all the distinct-representative demands in this reservoir. All their edges are in the reserved set E_i^{\mathrm{in}}.

For Q as above with x'\ne 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 is entirely outside V_i. The resulting closed walk is therefore a simple cycle. When x'=y', the two reserved edges themselves form a simple two-edge connection from x to y through that representative, and again close Q to a simple cycle. Its two reserved edges are distinct because x\ne y. In this case even a one-edge path Q produces a triangle; with different representatives the resulting cycle has at least four edges. Thus every completed cycle 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 types of edges are disjoint by reservation. The reservations in different P_i are also edge-disjoint, regardless of vertex overlaps among different cycles.

Counting and the exact remaining edge sets. We have produced at most \sum_i|\mathcal P_i|\le3r cycles. Take every unused edge in \bigcup_iE_i^{\mathrm{out}} as a single-edge part, using at most

further parts. The number of completed parts is therefore at most 9r.

For each i, let H_i be the graph on V_i consisting of exactly the unused edges of E_i^{\mathrm{in}}. These are the only remaining edges: every nonreserved edge was placed 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 defined by taking all remaining edges of the original induced graph G[V_i]; nonreserved edges, including ones with both endpoints in a reservoir, were already assigned to the appropriate complementary graphs. This accounts for every original edge exactly once.

The graphs H_i are simple, have the pairwise disjoint vertex sets V_i, and satisfy

Isolated vertices may be retained; a residual graph with no edges may alternatively be omitted. The only parameters fixed before increasing D were \eta,c and the constants determined from them. This completes the proof.□

Proof. The expansion condition implies that H is connected: in a disconnected graph some component has order between 1 and u/2 and has no external neighbors.

Run a depth first search. Its state consists of the unexplored vertices, a stack whose vertices in stack order form a simple path, and the finished vertices. Initially the stack consists of one vertex, all other vertices are unexplored, and none are finished. If the top vertex of the stack has an unexplored neighbor, push such a neighbor onto the stack. Otherwise pop the top vertex and mark it finished. At all times there are no edges between finished and unexplored vertices: when a vertex is finished it has no unexplored neighbor, and the unexplored set subsequently only shrinks. Connectivity ensures that the stack cannot become empty while an unexplored vertex remains, so this search finishes all vertices.

The number of unexplored vertices minus the number of finished vertices starts at u-1, ends at -u, and decreases by exactly one at every push or pop. Consequently there is a state at which these two numbers are exactly equal, say to t. Let P be the stack path at that state, and let L=\abs{V(P)}=u-2t. If t\ge u/3, then 0<t\le u/2, and all external neighbors of the unexplored set lie on P. Applying (5.5) gives L\ge\alpha t\ge\alpha u/3. If t<u/3, then L>u/3\ge\alpha u/3, since \alpha\le1 for the values of u under consideration. Thus in either case

Write q=q(u) and j=\floor q. We may assume q\ge1, since u/\log^4u tends to infinity. In particular j\ge1, and

Partition P into three consecutive vertex segments X,J,Z, with \abs J=j, distributing the other L-j vertices as evenly as possible between X and Z. Both outer segments have order at least

These inequalities include the integer rounding needed to make the three segments nonempty.

Suppose first that H-J has a path from X to Z. Choose one of minimum length among all such paths, with endpoints x\in X and z\in Z. A shortest path is simple. Its interior contains no vertex of X or Z, because encountering either set internally would give a shorter path between the two sets. It also avoids J. Since X,J,Z partition V(P), the chosen path meets P only at x,z. Its union with the x–z subpath of P is therefore a simple cycle. That subpath contains all j vertices of J and has at least j+1 edges; the new path has at least one edge. The cycle consequently has at least j+2\ge3 edges, and its length is greater than q.

It remains to show that such a path must exist. Otherwise X and Z, each connected by its segment of P, lie in distinct components of H-J. Separate the component containing X from the union of all other components, which contains Z, and let A be the smaller of these two sets. Then

Expansion and (5.7) imply

contrary to j=\floor q. This proves the lemma.□

Proof of Lemma 5.1. We prove the two operations in order. All lower bounds imposed on D in this proof are absolute and hold simultaneously for every D\ge D_{\mathrm{sp}} after one choice of D_{\mathrm{sp}}.

Removing long cycles. Choose a maximal family \mathcal C of edge-disjoint cycles in G whose lengths are at least D^{1.01}. Since \abs{E(G)}\le ND/2, we have

which proves (5.1). Integral cycle lengths are compared with the real threshold as stated, equivalently with \ceil{D^{1.01}}. Delete these cycle edges and retain the entire vertex set. By maximality the remaining graph has no cycle of length at least D^{1.01}. Every graph subsequently formed in the first operation is a subgraph of this remainder, so it inherits this prohibition.

A sparse external neighborhood. Put T=D^{1.02} and \eps=1/32. We claim that every current graph H of order u>T has a nonempty vertex set U such that

Otherwise Lemma 5.2 supplies a cycle longer than q(u) as defined in (5.6). To obtain a contradiction uniformly for every u>T, including u arbitrarily large relative to D, observe that x/\log^4x is increasing for \ln x>4, as follows by differentiating. Moreover,

Choose D_{\mathrm{sp}} large enough that T is in the range of Lemma 5.2, that T>e^4, and that q(T)>D^{1.01}. Then q(u)>D^{1.01} for every u>T, contradicting the inherited cycle prohibition. This proves (5.8).

The overlapping split and its edge assignment. For such a set U, put B=N_H(U)\setminus U and form two children on vertex sets

Assign to the first child every edge of H with both endpoints in V_1, and assign to the second child every other edge of H. Every edge incident with U has both endpoints in U\cup B. Consequently every edge assigned to the second child has both endpoints in V_2. This is an edge partition into two simple subgraphs; in particular, edges with both endpoints in the overlap B are assigned only to the first child. The child vertex sets cover the parent and have intersection exactly B. All vertices of each specified child set are retained, even when isolated in its assigned graph.

Writing s=\abs U, b=\abs B, u_1=s+b and u_2=u-s, we have 1\le s\le u/2 and b<\eps s/\log^2u. For sufficiently large D, therefore,

Indeed \eps/\log^2u\le1/2 gives u_1<(3/2)s\le3u/4, and u_2<u follows from s\ge1. Repeat this split whenever the current order exceeds T. Both child orders are positive integers strictly smaller than their parent order, so the resulting binary splitting tree is finite. Its leaves give the graphs G_Y on boxes of order at most T. The child cover property gives \bigcup_Y Y=V(G), and the edge assignments at each split show that the leaf graphs partition exactly the edges left after the cycle removal.

Controlling the sum of box orders. The sum of child orders can exceed the parent order by b. The following potential pays for this overlap. For every real x\ge1 define

For T\ge4, this is nondecreasing and

At a split of a graph of order u>T, put M=\max\{u_1,T/2\}. By (5.10) and u>T, we have M\le3u/4. Both logarithms below are positive, and

Monotonicity also gives f(u_2)\le f(u). Hence, using (5.10),

For the last step, (5.12) gives \eps f(u)\le1/16<\log(4/3). Repeatedly applying (5.14) in the finite splitting tree, and using f\ge1 on its leaves, proves

This argument also applies if N\le T, when the tree has just its root. Since T=D^{1.02} and D\ge4,

This proves (5.2) with C_0=2 and finishes operation (i).

Extracting pieces of cut expansion \sigma. This repeated removal of sparse cuts follows the small-side charging method used by Conlon, Fox and Sudakov [5, Lemma 3.1]. We give the accounting for the precise cut expansion and residual average degree required here. Fix a box Y, write y=\abs 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\mathbin{\dot\cup}A_2 into nonempty sets such that its cut has fewer than \sigma\min\{\abs{A_1},\abs{A_2}\} edges. Put those cut edges into the residual graph H_Y, and continue separately with the edges internal to each of A_1,A_2. Both child orders strictly decrease, so this procedure terminates. Its terminal vertex sets partition Y. The nonsingleton terminal graphs form \mathcal R_Y; by the stopping rule each has cut expansion at least \sigma. If such a graph has order r, its singleton cuts show that its minimum degree is at least \sigma. Simplicity then gives r-1\ge\sigma, and in particular (5.3). Terminal singletons carry no edges and are omitted from \mathcal R_Y.

To bound the edges put into H_Y, at each split charge their number equally to the vertices in a smaller side, choosing either side in case of equality. Each charged vertex receives less than \sigma at that split. Whenever a given vertex is charged, the current set containing it decreases in size by a factor of at least two; any intervening splits can only decrease its size further. If the vertex is charged k times, after its last charge its set has order at most y/2^k and at least one. Thus k\le\log y.

All residual cut edges are distinct, because each subsequent split uses only edges internal to a previous child. Summing the charges therefore gives

Every edge not set aside ends in exactly one terminal graph, and singleton terminal graphs contain no edges. Thus H_Y and the graphs in \mathcal R_Y partition E(G_Y) exactly. Define V(H_Y)=Y, retaining also the vertices of all terminal graphs. For y=1 the residual has no edges. For every 1\le y\le D^{1.02}, (5.15) yields

where the last inequality holds for all sufficiently large D. This proves operation (ii) and the lemma.□

Proof. Choose a uniform perfect pairing when m_i is even. When m_i is odd, adjoin a dummy vertex, choose a uniform perfect pairing on the m_i+1 vertices, and delete the dummy vertex and its incident 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. Thus

In particular the even-column expressions are valid upper bounds for both parities.

Let \pi send each vertex to its fiber after the identifications. Every fiber has size one or two. Before removing any edges, let Z count the original edges that become loops, plus the unordered pairs of distinct original edges that become the same nonloop edge. We bound \E Z by classifying all possible errors.

Loops and collisions with a common original endpoint. An original edge becomes a loop precisely 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\ne w. If they become the same nonloop edge, then \pi(u)=\pi(w)\ne\pi(v), so u,w must be paired in some X_i. No other identification is possible: identifying all three original vertices would require a fiber of size at least three. Consequently the contribution charged to X_i is at most

Here \binom d2\le(a-1)d/2 for every integer 0\le d\le a, and

The equality counts both incidences of every internal edge on both sides. Combining the loop and common-endpoint bounds, the expectation is at most

since m_i\ge8.

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 must be either \{u,x\},\{v,y\} or \{u,y\},\{v,x\}. All four vertices therefore belong to folding sets: a singleton fiber cannot contain two distinct original endpoints. If the two paired fibers lie in one X_i, then both original edges are internal to X_i. Writing e_i=\abs{E(J[X_i])}, there are at most \binom{e_i}2\le e_i^2/2 possible vertex-disjoint edge pairs, and the two possible pairing patterns give probability at most 2/((m_i-1)(m_i-3)). As e_i\le a m_i/2, their total contribution is at most

For the last inequality use m_i/(m_i-1)\le8/7 and m_i/(m_i-3)\le8/5.

If the two paired fibers instead lie in different sets X_i,X_j, then both original edges run between those sets. There is just one possible 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\le e_{ij}^2/2 vertex-disjoint edge pairs. Independence between the two pairings and (6.4) bound this contribution by

Indeed, for each fixed i,

the first inequality uses e_{ij}\le a m_j, and the second follows from the total degree bound on X_i. Summing over i counts each unordered pair of sets twice. The preceding cases exhaust distinct original edges, which either have one common endpoint or have four distinct endpoints in a simple graph.

Equations (6.5)–(6.7) give

when t>0. Some choice of pairings has no greater error count than its expectation. For this choice delete each original loop edge and, in each nonloop parallel class of size s, delete all but one original edge. The latter requires s-1\le\binom s2 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 (6.3). If t=0, use the identity map and delete no edges.□

Proof. We first choose the quotient graphs and prepare some paths to be closed. No router edges are 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 [5, Lemma 6.3]: decompose a bipartite graph into paths and remove terminal edges so that the remaining endpoints lie on one prescribed side. We keep the endpoint loads under the 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

Every vertex in any active set has degree at most a in J_W, since J_W\subseteq F. Thus H_X is disjoint from every active set in this batch, including X. If H_X is nonempty, counting edges gives

in all cases \abs{H_X}\le\abs X. The sets E_X for different active X are disjoint. In fact each of their edges has one endpoint in its specified active set and its other endpoint outside every active set, so it cannot belong to the set specified by a different active set.

Apply Corollary 2.2 to the bipartite graph with parts X,H_X and edge set E_X. It gives at most \abs X+\abs{H_X}\le2\abs X positive-length simple paths, since their total number of endpoint occurrences is at most 2(\abs X+\abs{H_X}). From each path delete its terminal edge at each endpoint belonging to 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.

Ignore any remnant with no edges. Every other remnant is a simple path with both endpoints in X: this follows directly 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 internally the set V(L)\cap V(R), and give this demand its own team. Once this demand is routed, its remnant will form one cycle. Each original path therefore accounts for at most two single edges and one cycle, for a total of at most 6\abs X parts. We do not require an endpoint-load-two bound for the trimmed paths; their endpoint loads will be bounded using their incident original edges in the global load argument below.

Choosing the quotients. Remove all the sets E_X from J_W and call the resulting graph J_W^0, retaining the vertex set W. Each active vertex still has degree at most a. For each active X and every v\in W, either v was in H_X, in which case all its edges into X were removed, or it originally had at most a neighbors in X. Hence \abs{N_{J_W^0}(v)\cap X}\le a in both cases. For large D we have L_0\ge\max\{8,a^2\}. Apply Lemma 6.1 to J_W^0 and its active sets. Count its error edges singly in their original form and call the simple resulting quotient Q_W. Denote its quotient map by \pi_W; each edge e of Q_W has a unique retained original representative \widehat e. The number of these single-edge parts is at most 2\sum_R\abs{X_{W,R}}.

Every identified pair removes exactly one vertex. Since \floor{m/2}\ge m/3 for every integer m\ge2, the exact order formula from Lemma 6.1 yields (6.9), and summing yields (6.10). This construction of all Q_W is independent of their subsequent partitions.

The 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,\ldots,z_s, where s\ge3, and write e_j=z_jz_{j+1}, with indices interpreted cyclically. At z_j let u_j be the endpoint of \widehat e_{j-1} in the fiber \pi_W^{-1}(z_j), and let v_j be the endpoint of \widehat e_j in that fiber. If u_j=v_j, the two edges join without any added path. Otherwise that fiber is a folded pair \{u_j,v_j\} in 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

Thus every original endpoint on the entire cycle, including the endpoints of all its other switches, is forbidden internally. The demands belonging to this cycle and this router form one team. Teams for different cycles, including cycles from different batch indices, are distinct. The single-demand teams recorded during the heavy-neighbor work are also distinct from these teams. Figure 1 shows the switch construction. The next two steps verify that all these requested paths can be chosen simultaneously and that the resulting closed walks are simple.

The load bound over all batches. Fix one piece R. Gather every demand for P_R from all batches and both constructions. Each endpoint is in an active set, hence has degree at most a in the one graph F(Y). To bound its total demand load, associate each occurrence of an endpoint x 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\ne v_j, associate the occurrence of u_j with \widehat e_{j-1} and that of v_j with \widehat 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 be used only at the unique visit to its quotient fiber in that cycle. The 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. Finally, edges from different batches are distinct by hypothesis, regardless of overlap of their vertex sets or differences in their pairings. This proves the injection into incident edges of F(Y) and hence

Vertices that are never endpoints have load zero.

Supplying all the connections. A team from a cycle C has at most s\le q_W\le B_0 demands, and \abs{Z_C}\le2s\le2B_0. A heavy-neighbor remnant has at most \abs W\le B_0 vertices; its team has size one. Thus in Lemma 3.1 we may use

With that lemma’s definitions of g and \ell, the range \sigma\le r_R\le D^{1.02} gives, uniformly in R,

For all sufficiently large D this is at most \sigma/256=h/64, which is exactly enough for (3.2). 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. Do this for every piece R. The constants are absolute, and do not depend on the number of batches or demands.

Simplicity of the completed cycles. For a heavy-neighbor remnant L, its supplied path is simple and has distinct endpoints equal to those of L. Its internal vertices avoid V(L): the forbidden set contains V(L)\cap V(R), and all 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,\ldots,z_s are mutually disjoint. At a visit with u_j=v_j, its 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, the vertices at different visits are distinct. Every supplying path interior avoids Z_C, which includes 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 deserves explicit mention. If a visited fiber is a pair but u_j=v_j, its other vertex need not belong to Z_C and may occur inside a supplying path. It is absent from all original representative edges of this 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 excludes this in its router, and the other routers have disjoint vertex sets. This therefore 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\ge3. A quotient cycle with no switches is already a simple cycle of original edges. Each quotient part thus yields exactly one permitted part.

Edge accounting and cost. For each batch, its original edges have exactly four destinations:

1. 1.

   designated edges trimmed from paths are single-edge parts;

2. 2.

   designated edges in positive-length remnants occur in their closed cycles;

3. 3.

   folding error edges are single-edge parts, taken before identification;

4. 4.

   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 edge set in the statement. 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_W t_W. Adding a supplying path changes no part count. This proves (6.11).

No edge of T_R was used: U_R\subseteq 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 assigned piece not already used in a completed part. This proves both the remaining expansion assertion and the final edge partition.□

Proof. Start at the first positive term and maintain \sum_{j=0}^iS_j\le2(K+1)S_i. If (7.3) fails, the sum of the next K terms is greater than 2(K+1)S_i. Their largest value M is therefore greater than 2S_i. Move to an index i' in that window with S_{i'}=M. Then

The invariant persists. Each move increases the index and lands at a positive term. Finite support therefore forces the procedure to stop, at which point (7.3) holds.□

Proof. We use strong induction on n. The lower scale cutoff D_* is an absolute constant, chosen to satisfy the uniform requirements below. Only after fixing it will we choose C. All auxiliary constants introduced before that final choice are independent of C and remain valid if the cutoff is increased.

Edgeless graphs have the empty partition. For 1\le n<D_*, using every edge singly proves the assertion when C\ge D_*, since \phi(n)\ge1/2. Now let n\ge D_*, assume the assertion for every smaller positive order, and put

Take D_*>2. Then m is finite and positive, and the scales D_0,\ldots,D_{m-1} all satisfy the cutoff.

Prospective layers. Starting with the given graph G, perform both operations of Lemma 5.1 at each successive scale D_0,\ldots,D_{m-1}. The inputs at stage j have average degree at most D_j: this holds initially because \overline d(G)\le n-1<D_0, and the residual graph in each new box has average degree at most D_j^{0.95}=D_{j+1}.

Let \mathcal Y_j be the indexed family of level-j boxes and \mathcal R_j the indexed family of pieces removed inside them. The residual graph passed to the next stage retains the entire vertex set of its box, including isolated vertices. Every box has a unique indexed parent, and its vertex set is contained in its parent’s vertex set. Descendants of any box cover that box’s vertex set. Distinct indices are retained even when their vertex sets overlap or coincide.

These operations define prospective layers: we will subsequently keep only a prefix of them. At the end of every prefix, the long cycles removed so far, the pieces removed so far, and the remaining input graphs partition E(G). In particular, discarding the prospective operations beyond a chosen prefix means retaining their input graphs, with all their assigned edges, at that prefix’s boundary.

Write

and set S_j=0 for j\ge m. Increase the absolute constant C_0 in Lemma 5.1 if necessary so that C_0\ge1, and put C_2=40C_0. For 0\le j<m,

Provided \log D_*\ge C_2, the product of the order increases is consequently bounded by

Here we used 1+x\le e^x and e^x\le1+2x for 0\le x\le1/2. The lower bound follows from preservation of the vertex cover at every split. The same product calculation, using the relevant subproduct, shows that the orders of all level-j descendants of a box of order y sum to at most (1+C_2/\log D_j)y. Their union still covers its full vertex set.

We also require D^{-0.01}\le1/\log D for every D\ge D_*. If \mathcal L_j is the family of long cycles removed through level j, then

These bounds have no dependence on the number of layers. Piece disjointness within each box gives S_j\le N_j\le2n.

Terminal cases. If every S_j vanishes, keep all prospective stages. Use the long cycles and take the remaining edges singly. The remaining graphs, on the level-(m-1) boxes, 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. By (7.6), the total cost is at most (20+D_*)n.

Otherwise choose i by Lemma 7.1. If i+K\ge m-1, again keep every stage. Retain all long cycles as completed parts and take every edge of the final boundary graphs singly, at cost at most (20+D_*)n as above. The zero extension of (S_j) ensures that \sum_{j=0}^{m-1}S_j\le P_0S_i. Apply Lemma 4.3 to each piece at its own scale, with c=1 and the fixed \eta. This completes at most 9P_0S_i parts and leaves graphs of total order at most

Each individual residual graph has order at most \eta r<n, where r is the order of its parent piece: the piece’s vertex set is a subset of V(G), so r\le n, and \eta<1. Apply the induction hypothesis to each nonempty residual graph; their total additional cost is at most Cn/4, using \phi\le1.

Both terminal cases are therefore covered by the bound

For C\ge4T(D_*), this is at most Cn/2\le C\phi(n)n. This choice also 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

Since \log D_t=\theta^K w, (7.5) and (7.6) imply

The latter uses C_2\ge40>20.

Fix a level-i box Y, of order y\le 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}}. Moreover,

For the last inequality, note that H/w=C_2/\log D_t\le1.

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

Each descendant has fewer than L_0 vertices, so we first group descendants to make larger folding sets possible. The number of batches will bound the loss when an intersection of a batch with a selected piece contains fewer than L_0 vertices of degree at most a in F(Y). The batch order cap B_0 keeps quotient cycles within the routing team bound.

Partition the indexed descendants into batches whose sums of orders are at most B_0. This can be done with at most 1+4y/B_0 batches: require the cutoff to ensure D^{0.001}\le B_0/2, fill a batch until the next descendant would exceed B_0, and then start a new one. Every batch except possibly the last has order sum greater than B_0/2, so their number is at most 1+2T_Y/B_0.

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 in this notation. Denote the family by \mathcal W(Y). Thus the J_W partition E(F(Y)), the sets W cover Y, and

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. Thus, at the boundary of the committed prefix, the assigned edge sets give the disjoint union

Active sets and multiplicities. Call a vertex of Y good if its degree in F(Y) is at most a. By (7.10) and (7.2), the number of other vertices is at most

where the final inequality is another uniform large-scale requirement. For each W\in\mathcal W(Y) and each level-i piece R belonging to Y, consider all good vertices of W\cap V(R). If their number is at least L_0, retain this set as X_{W,R} and call it active; otherwise skip it. Active sets in a fixed batch are disjoint, because the pieces in Y have disjoint vertex sets.

There are at most y/\sigma such pieces. Consequently the total size of all skipped sets in Y, counting occurrences in different batches separately, is at most

Here the exponent -0.15 uses y\le D^{1.02}, and the last inequality is imposed for all scales above the cutoff.

Let s(Y) be the sum of the orders of the level-i pieces in Y, and define

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 of the chosen occurrences can lie in skipped sets by (7.13). Hence \Sigma_Y\ge s(Y)-2y/w.

For the upper bound, let u_Y(v)\ge1 be the number of batches in Y containing v. Then

Since the pieces in Y are vertex-disjoint, their excess occurrences are bounded by this full excess. Thus \Sigma_Y\le s(Y)+\sum_W|W|-y. Summing the two bounds, using N_i\le2n, N_i\ge n, and (7.8)–(7.11), gives

This counts a nongood vertex only once per indexed box in the lower bound; no bound on its number of batch occurrences is needed. Overlaps between different boxes are already included in both S_i and N_i.

Resolving the batches and the pieces. In every level-i piece R, apply Lemma 4.1 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 and leave T_R untouched during the batch work.

All hypotheses of Lemma 6.2 now hold in each Y. The J_W have order at most B_0 and disjoint assigned edges; their union is F(Y). The pieces have orders between \sigma and D^{1.02}, disjoint vertex sets within 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 L_0. In particular the degree bound is shared across all batches, as required by that lemma.

The lemma produces simple quotient graphs Q_W, with orders

Every batch has positive order and pair identifications leave at least one vertex, so 1\le q_W\le B_0. Also B_0=D^{0.30}\le n^{0.30}<n. Apply the induction hypothesis to these 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 every R still contains T_R. In particular, lifting a quotient cycle produces one simple cycle and has no additional part charge.

Apply Lemma 4.3, 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 9P_0S_i. If \mathcal H is their family of residual graphs, then

Every nonempty member has order at most \eta r<n, for the same reason as in the terminal case. Induction applies to all of them.

Within each Y, Lemma 6.2 resolves exactly the batch category in (7.12) 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 remaining piece edges into completed parts and the members of \mathcal H. Distinct indexed boxes have disjoint assigned edge sets even when their vertex sets overlap. Thus the only unresolved original edges after lifting the quotient partitions are precisely the assigned edges of \mathcal H, each appearing once. Recursively partitioning them completes an edge partition of G.

Order savings and the final estimate. Define the absolute constants

By (7.15), (7.11), and (7.14),

The parts completed apart from the quotient partitions and the recursive work on \mathcal H number at most

Monotonicity of \phi, q_W\le B_0, and (7.16) therefore bound the complete partition size by

The coefficient of S_i in this expression is at most

It remains to pay for the order-overlap term. Set \delta=1/\sqrt{0.30}-1>0. For w\ge40/3, both \phi(n) and \phi(B_0) take their nonconstant values, and \log n\ge w gives

For C\ge7A_2, the remaining overhead in (7.19), beyond C\phi(B_0)n, is at most C(A_1+1)n/w. It is absorbed by (7.20) whenever

No choice made here requires the total quotient order in (7.17) to be at most n; the potential gain pays for its possible excess.

We finally specify the order of constant choices. The parameters in (7.1), the scale-split constant C_0\ge1, and hence C_2,H,A_1,A_2,\delta, are already absolute and fixed. Choose D_* large enough for Lemmas 5.1 and 6.2, for Lemma 4.1 with two classes at expansion D^{0.90}, and for Lemma 4.3 with the fixed \eta and c\in\{1,1/4\}. Also impose \log D_*\ge\max\{C_2,40/3\}, (7.21), and, for every D\ge D_*,

These are uniform eventual inequalities between fixed powers and logarithms. Such a cutoff exists independently of C. After fixing it, choose

The base and terminal cases then hold, and (7.19)–(7.20) give at most C\phi(n)n parts in the remaining case. This closes the strong induction.□