A new arXiv preprint presents what its author describes as a proof of a three-part graph-decomposition conjecture. The claim is that every finite connected cubic loopless multigraph can have its edges divided into a spanning tree, a 2-regular subgraph made up of cycles, and a matching whose edges do not share endpoints.
The manuscript treats this as a formal existence result for finite graph classes. Its conclusion therefore rests on the definitions, theorem hypotheses and proof inputs stated in the paper, rather than on a measured sample or a statistical estimate.
The theorem at the center
The main step concerns a narrower setting. For a finite connected bridgeless simple graph with maximum degree three and at least two degree-two vertices, the manuscript states that a matching can be selected with a size equal to the number of edges minus the number of vertices plus one. After those matching edges are removed, what remains is one tree containing all of the graph's degree-two vertices, together with zero or more cycles.
The proof tracks those degree-two vertices as terminals. The theorem does not promise that every other part disappears: residual cycles are allowed. That distinction matters because the final three-part result requires a spanning tree, not simply a tree accompanied by leftover cycles.
A proof built around transfers
The terminal-selection theorem is proved by strong induction on the number of terminals. The argument also introduces a comparison matching that is guaranteed to cover at least two terminals, a lower bound used within the construction.
A key repair is called first-entry transfer. The construction follows an alternating path, switching between matching and non-matching edges, and swaps an initial segment when the path first enters the relevant part of the graph. The swap keeps the matching size unchanged while reattaching a stray vertex, preserving the count required by the theorem.
The manuscript also uses two external results and states and proves a protected removable-cycle theorem for later use. Those cited results are therefore part of the stated proof architecture alongside the new argument.
Turning the pieces into the claimed partition
A related part of the argument establishes the standard loopless-multigraph 2-Decomposition Conjecture from a spanning-tree and matching decomposition. For the three-part construction, the proof chooses an inclusion-maximal 2-regular subgraph whose complement after deleting its edges is connected. It then reduces that complement to its 2-core, the core subgraph used for the next decomposition step.
That core is placed in the domain of the 2-Decomposition Conjecture and split into a spanning tree and a matching. The proof then adds pruned forest edges to turn the tree in the core into a spanning tree of the full complement. In the manuscript's final accounting, the three edge sets are the spanning tree, the original 2-regular subgraph and the matching.
Residual cycles are the point at which a second theorem enters. Every finite connected simple fragile subcubic graph is stated to admit an edge partition into a spanning tree and a matching. The paper uses the protected removable-cycle argument to obtain that tree-and-matching structure where the terminal-selection result alone still permits cycles.
The limits set by the proof
The central terminal-selection result is limited to finite connected bridgeless simple graphs of maximum degree three with at least two degree-two vertices. The overall conclusion is stated for finite connected cubic loopless multigraphs. The supplied analysis does not extend these conclusions beyond the finiteness, degree, simplicity, bridgelessness or looplessness conditions attached to the relevant theorems.
Because the manuscript makes formal existence claims, it reports no statistical uncertainty. The relevant qualification is that the result depends on the formal argument and its stated external inputs. The terminal-selection theorem alone also does not show that its complement is always a spanning tree with no residual cycles; that requires the additional protected removable-cycle argument used for fragile graphs.
According to the author, the terminal-selection theorem is the manuscript's main piece of work and may have further applications. The work remains an arXiv preprint, identified in its front matter as version 1.
The acknowledgements say generative AI was used during preliminary exploration and language editing. They also say the author verified the mathematics and takes full responsibility; no funding source is stated there.
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