3-Decomposition Conjecture: does every connected cubic graph split into a spanning tree, a matching, and cycles?
Statement
The $3$-Decomposition Conjecture, posed by Hoffmann-Ostenhof (2009/2011), asserts that **the edge set of every connected cubic graph can be decomposed into a spanning tree, a (possibly empty) matching, and a (possibly empty) family of cycles** (i.e. a $2$-regular subgraph). Here 'cubic' means $3$-regular and the three parts partition the edges. Decide the conjecture, or find a connected cubic graph with no such decomposition. Computational sub-question: verify the conjecture for all connected cubic graphs up to $n$ vertices.
Acceptance. FULLY RESOLVES: (a) a connected cubic graph with a certificate (exhaustive/ILP infeasibility) that no partition of its edges into a spanning tree, a matching, and a $2$-regular subgraph exists, or (b) a proof. PARTIAL PROGRESS: an exhaustive verification, via $\texttt{genreg}$/$\texttt{geng}$ enumeration of connected cubic graphs plus a per-graph decomposition search (SAT/ILP), that every connected cubic graph on at most $n$ vertices decomposes as required (report $n$ and count), or a proof for a new class.
Background
Frontier: proved for Hamiltonian cubic graphs and, more generally, traceable cubic graphs (Abdolhosseini et al. / Akbari, Jensen, Siggers), for $3$-connected cubic planar graphs and cubic graphs on the projective plane, and other classes. Recent independent 2025 work (Sci. China Math.; also Discrete Math. 2025) proves a relaxation (spanning tree + cycles + a bounded number of $2$-edge paths). Open in general. Source: Open Problem Garden, '3-Decomposition Conjecture' (www.openproblemgarden.org/op/3_decomposition_conjecture), originator A. Hoffmann-Ostenhof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | 3-Decomposition Conjecture — Open Problem Garden | link |
| REF-02 | The 3-decomposition conjecture of cubic graphs (Sci. China Math., 2025) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.