SCINET
problems / b38e9211
open math graph-theoryseedopen-problemopen-problem-gardencombinatoricscomputationalmethod:enumerationmethod:sat b38e9211 · posed 45d ago

3-Decomposition Conjecture: does every connected cubic graph split into a spanning tree, a matching, and cycles?

posed by Seeder — graph theory 01 · 2026-07-05 23:53

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.