The central finding is that the 3-Decomposition Conjecture holds for every finite connected cubic loopless multigraph. In plain language, that means every finite, connected graph in which each vertex has degree three, repeated edges are allowed and self-loops are excluded has the edge split the conjecture requires. The split has three disjoint parts: a spanning tree, a connected, cycle-free backbone that reaches every vertex; a 2-regular subgraph, where each vertex in that subgraph has degree two; and a matching, whose edges do not share endpoints.
The matching at the centre
The paper's central intermediate result works with finite connected bridgeless simple graphs of maximum degree three. It uses a set S of degree-two vertices, with at least two members, and treats those vertices as terminals in the argument. The theorem says a matching can be chosen at a prescribed size based on the graph's total number of vertices and terminal count. Once those edges are removed, what remains is a single tree containing every terminal, plus zero or more cycles.
The proof's key exchange
The proof uses strong induction on the number of terminals: it handles a graph with two terminals first and then closes the remaining cases. A handshaking and counting identity follows each component by comparing its exposed vertices and terminals with its cyclomatic number, a measure of its independent cycles. In the two-terminal base case, the construction adds a new edge between the terminals and takes a perfect matching containing an old edge. The complement becomes one terminal-to-terminal path, with zero or more cycles alongside it.
The more delicate part is an exchange argument. The proof invokes the result that every finite bridgeless cubic loopless multigraph has a perfect matching, then compares that matching with one in an auxiliary cubic construction. Restricted to the original graph, the comparison matching covers every cubic vertex and at least two terminals, while its size is the target size plus a nonnegative excess. An alternating-path prefix flip preserves the matching's size, leaves the selected complement component's internal edges untouched and moves all exposed vertices into the component being repaired. The first vertex where the path re-enters that component is shown to lie inside it. If a restoration attempt still fails, the next counting step keeps the target size, puts all but two exposed vertices and all but one old terminal in the same component, and parity forces the remaining terminal into it.
A chain of consequences
The matching-complement theorem is then used to show that every finite connected simple fragile subcubic graph admits an edge partition into a spanning tree and a matching. A minimum-counterexample argument uses that statement to establish the standard loopless-multigraph form of the 2-Decomposition Conjecture. Finally, the construction supplies a disjoint partition of the full edge set into the spanning tree, the 2-regular subgraph and the matching. In the paper's notation, that construction is the step summarized as 2DC implying 3DC.
The boundaries of the result
This is a proof over graph classes, not a statistical estimate, so no statistical uncertainty is reported. The manuscript reports no empirical evaluation, computational performance analysis or algorithmic complexity bound. The document is an arXiv version 2 preprint dated 3 September 2026.
The paper also notes a prior bound of the number of vertices minus four, divided by eight, for paths of length two in a connected cubic graph. It states that this count is zero under the paper's result. Questions remain about the minimum possible number of cycle components in a 3-decomposition, the maximum number of distinct 3-decompositions as a graph grows, and the behavior of other extremal parameters.
Paper data and sources
Original title: Matching complements in subcubic graphs and a proof of the 3-Decomposition Conjecture
Authors: Jicheng Ma
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text