we-solve (beta)

Math-1057 · mathematics · Graph theory

3-Decomposition Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $G=(V,E)$ be a finite connected simple undirected graph in which every vertex has degree three; such a graph is called cubic. A spanning tree is a connected acyclic subgraph with vertex set $V$. A matching is a set of edges no two of which share an endpoint. A $2$-regular subgraph is a subgraph all of whose vertices have degree two within that subgraph, so its components are vertex-disjoint cycles.

The $3$-decomposition conjecture asks for an edge partition \[ E=E(T)\mathbin{\dot\cup}E(C)\mathbin{\dot\cup}M \] such that $T$ is a spanning tree of $G$, $C$ is a nonempty $2$-regular subgraph of $G$, and $M$ is a matching, which is allowed to be empty. Neither $C$ nor the vertices incident with $M$ need span $G$. The dot on the unions requires that each edge belongs to exactly one part. Vertices may occur in several of the subgraphs.

More explicitly, the conjecture quantifies over every connected cubic $G$ and asks for a single choice of $T,C,M$ meeting all these conditions. It does not merely ask for the three kinds of subgraph to exist independently. Equivalently, one should choose a spanning tree so that every nontrivial component of its edge complement is either a cycle or a single edge. This complement description records the matching condition on all remaining edges.

Short English statement

Can the edges of every connected cubic graph be partitioned into a spanning tree, disjoint cycles, and a matching?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1057-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1057

3-Decomposition Conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite connected simple undirected graph in which every vertex has degree three; such a graph is called cubic. A spanning tree is a connected acyclic subgraph with vertex set $V$. A matching is a set of edges no two of which share an endpoint. A $2$-regular subgraph is a subgraph all of whose vertices have degree two within that subgraph, so its components are vertex-disjoint cycles.

The $3$-decomposition conjecture asks for an edge partition \[ E=E(T)\mathbin{\dot\cup}E(C)\mathbin{\dot\cup}M \] such that $T$ is a spanning tree of $G$, $C$ is a nonempty $2$-regular subgraph of $G$, and $M$ is a matching, which is allowed to be empty. Neither $C$ nor the vertices incident with $M$ need span $G$. The dot on the unions requires that each edge belongs to exactly one part. Vertices may occur in several of the subgraphs.

More explicitly, the conjecture quantifies over every connected cubic $G$ and asks for a single choice of $T,C,M$ meeting all these conditions. It does not merely ask for the three kinds of subgraph to exist independently. Equivalently, one should choose a spanning tree so that every nontrivial component of its edge complement is either a cycle or a single edge. This complement description records the matching condition on all remaining edges.

Short English statement

Can the edges of every connected cubic graph be partitioned into a spanning tree, disjoint cycles, and a matching?

Research attempt

Scope and process.
This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.
Literature update.
The historical conjecture is studied computationally in the primary 2025 paper [R1]. A preprint by Jicheng Ma posted in August 2026 [R2] claims a full proof, including loopless cubic multigraphs. That claim is reported here rather than silently treating the old catalogue metadata as a current consensus. This attempt independently proves an exact spanning-tree reformulation and an infinite family; it does not certify every argument in the recent preprint.
The leaves of the spanning tree determine the cycle part.
Suppose $(T,C,M)$ is a decomposition of a simple connected cubic graph on $n\ge4$ vertices. At a vertex of $C$, two incident edges are used by $C$. Since a spanning tree must give every vertex positive degree, the third edge belongs to $T$, not $M$. Therefore every vertex of $C$ is a leaf of $T$. Conversely a leaf of $T$ has two remaining incident edges. They cannot both lie in the matching, and any vertex of a $2$-regular subgraph has either zero or two edges of that subgraph. Hence both remaining edges belong to $C$. Thus \[ V(C)=\{v:d_T(v)=1\}=:L. \] No edge of a tree on at least three vertices joins two leaves: such an edge would form a component isolated from the other vertices. Consequently every edge of $G$ with both endpoints in $L$ lies outside $T$, and $G[L]=C$ is $2$-regular.

Conversely, suppose a spanning tree $T$ has leaf set $L$ such that $G[L]$ is $2$-regular. Each leaf's two non-tree edges lie in $G[L]$, exhausting those incidences. Each non-leaf has tree degree two or three and therefore at most one non-tree edge; it has no remaining edge to $L$. All non-tree edges outside $G[L]$ consequently form a matching. This proves the exact equivalence: \[ \text{a 3-decomposition exists}\quad\Longleftrightarrow\quad \exists T\text{ spanning with }G[L(T)]\text{ 2-regular}. \] Such a leaf set is nonempty and has at least three vertices, so the required nonempty cycle part is automatic.

Counting restrictions on a possible tree.
Let $\ell$ be the number of tree leaves, and let $b$ be the number of vertices of tree degree three. The tree degree sum gives $\ell=b+2$. The remaining $n-\ell-b=n-2\ell+2$ vertices have tree degree two, and each is an endpoint of exactly one matching edge. Therefore \[ |M|=n/2-\ell+1,\qquad 3\le\ell\le n/2+1. \] The parity is consistent because every cubic graph has even order. These identities are useful checks of a candidate decomposition; they are not sufficient to produce the required adjacency pattern among the leaves.
An explicit infinite family.
For the prism $C_m\mathbin{\square}K_2$, $m\ge3$, name the two cycles $u_0\cdots u_{m-1}u_0$ and $v_0\cdots v_{m-1}v_0$, and join each $u_i$ to $v_i$. Put the whole $u$-cycle in $C$. Put all $m$ vertical edges and the bottom path $v_0v_1\cdots v_{m-1}$ in $T$. This graph is connected, has $2m-1$ edges on $2m$ vertices, and is a path with one new leaf attached at every vertex, hence is a tree. The single remaining edge $v_{m-1}v_0$ forms $M$. Its leaf set is exactly the upper cycle, verifying the reformulation directly. For $K_4$, take one triangle as $C$ and the three edges to its fourth vertex as $T$; the matching is empty, as allowed.
Why a Hamiltonian path does not solve the problem.
Choosing a spanning path minimizes the number of leaves, but gives exactly two. A simple $2$-regular graph cannot live on those two vertices. Thus even in graphs with an obvious spanning path, that choice can never be the tree part of the desired decomposition. The task is to choose a different tree whose leaf adjacencies close into cycles. Connectivity of a graph guarantees some spanning tree, but supplies no such condition on its leaves.
Verification and final status.
The script scripts/check_attempt_batch02_algebra_2026_10_01.py checks edge partitions, degrees and connectivity for the prism construction for $3\le m\le20$, complementing the all-$m$ proof. UNRESOLVED as an independent complete proof: the leaf criterion is exact and the displayed family is settled. The remaining independent step is construction of such a spanning tree for every cubic graph, or verification of the complete claimed argument in [R2].

Sources

Go to contribution →