Partition of a cubic 3-connected graphs into paths of length 2.

Partition of a cubic 3-connected graphs into paths of length 2.

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple $3$-connected cubic graph. Here cubic means degree three at every vertex, and $3$-connected means that $|V|\geq4$ and deletion of any set of at most two vertices leaves a connected graph. Let $P_3$ denote the path on three distinct vertices $x,y,z$ with its two edges $xy,yz$. Its length is two, measured in edges.

A $P_3$-factor of $G$ is a spanning subgraph whose connected components are copies of $P_3$. Equivalently, it consists of pairwise vertex-disjoint three-vertex paths whose vertex sets partition $V$. The paths are not required to be induced: an additional edge between the two endpoints of one chosen path may exist in $G$ and is simply omitted from the factor.

The question is whether \[ 3\mid |V(G)|\quad\Longrightarrow\quad G\text{ has a }P_3\text{-factor} \] for every $3$-connected cubic $G$. Writing $|V|=3k$, the conclusion requires exactly $k$ selected paths. Since a cubic graph has even order by the handshaking identity, admissible orders are in fact multiples of six.

This partitions the vertices, not all edges of $G$. Every vertex must occupy exactly one position in exactly one selected path, either an endpoint or its middle vertex. The unused edges may join different paths or form chords within their three-vertex sets and have no prescribed structure.

Short English statement

Can every 3-connected cubic graph whose order is divisible by three have its vertices partitioned into three-vertex paths?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. The catalogue formulation is retained above. This attempt checks the original problem and primary literature, proves the restricted claims stated below, and identifies the exact limit of its conclusions. Reproved facts are not claimed as novel results.

Literature and convention.

Kelmans's paper [S3] studies this packing problem and equivalences with stronger-looking assertions. We use none of those equivalences as an unproved shortcut. A factor here is a selected spanning subgraph whose components are three-vertex paths; additional ambient edges between the endpoints are allowed. In particular, two edges of a triangle are a valid path component. The order of a cubic graph is even, so the catalogue divisibility assumption actually gives $|V(G)|\equiv0\pmod6$.

A path-based sufficient condition.

If a graph on $3k$ vertices has a Hamilton path $v_1,\ldots,v_{3k}$, the $k$ paths \[ v_{3i+1}v_{3i+2}v_{3i+3},\qquad0\le i<k, \] form the desired factor. More generally, a spanning disjoint union of cycles, each of length divisible by three, can be partitioned by taking consecutive triples on each cycle. The disjointness and covering statements are literal partitions of the vertex lists; all selected edges exist. This proves the target for Hamiltonian cubic graphs of the allowed order, but does not assume that all 3-connected cubic graphs are Hamiltonian.

For a concrete infinite family, the prism $C_{3k}\square K_2$ has $6k$ vertices, is cubic and simple for $k\ge1$, and the two layer cycles each split into $k$ triples. Deleting at most two vertices leaves the prism connected: if the deletions lie in one layer, the other intact cycle connects every remaining vertex of that layer by a vertical edge; if there is one deletion in each layer, each remaining layer is a connected path and at least one vertical edge survives. This verifies 3-connectivity as well as the factor.

Triangle expansion without a Hamiltonicity assumption.

Let $H$ be any simple cubic 3-connected graph. Replace each vertex $v$ by a triangle with three ports, one for each incident edge. For every edge $vw$ of $H$, join the corresponding port in the triangle for $v$ to that in the triangle for $w$. Denote the expanded graph by $T(H)$. It is simple and cubic: each port has two neighbours in its triangle and one external neighbour. Its order is $3|V(H)|$, divisible by six. Choosing any two edges from each replacement triangle immediately gives a three-vertex-path factor.

We verify that the expanded graph satisfies the nontrivial connectivity hypothesis. First, a simple cubic 3-connected graph has no edge cut of size at most two. If a cut $\delta(X)$ had that size, at most two vertices of $X$ would touch it. Unless all of $X$ were those vertices, removing them would disconnect the remaining vertices of $X$ from the other shore, contradicting 3-connectivity. But a shore of size one has boundary size three, and a shore of size two has boundary size at least four in a simple cubic graph. Thus the exceptional small shores cannot occur either.

Now delete at most two vertices of $T(H)$. Every replacement triangle retains a nonempty connected set. At most two external edges have lost a port, since each deleted port belongs to exactly one external edge. The base graph $H$ with those at most two edges deleted is connected by the preceding paragraph. Contract the surviving part of each triangle: the surviving external edges connect these contracted vertices exactly as in that connected base subgraph. It follows that the uncontracted remainder is connected too. Hence $T(H)$ is 3-connected, and the factor construction solves the catalogue target on this entire expansion family.

Verification and obstruction to the general route.

The script scripts/check_attempt_batch02_graphs_2026_10_01.py expands both $K_4$ and the Petersen graph, verifies cubic degrees, checks connectivity after every deletion of at most two vertices, and checks the triangle-path partitions. This is a check of the construction, not an enumeration of all cubic graphs. The proof requires no Hamilton cycle in the base graph.

An arbitrary perfect matching leaves a 2-factor, but its cycles need not have lengths divisible by three. Cutting a cycle of length $3q+1$ or $3q+2$ into triples leaves one or two vertices; the matching edges between cycles are not automatically arranged to absorb those leftovers. Triangle expansion avoids this obstacle by providing a partition at the outset. It supplies no decomposition of a general cubic graph into such triangles.

Final status.

The Hamilton-path criterion, the cycle-divisibility criterion, and all triangle expansions of simple cubic 3-connected bases are proved. The unrestricted factor-existence statement is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3189 (OPG-46613), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Partition of a cubic 3-connected graphs into paths of length 2.. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/partition_of_a_cubic_3_connected_graphs_into_paths_of_length_2.
• S3 Alexander Kelmans, Packing 3-vertex Paths In Cubic 3-connected Graphs, arXiv:0910.2766v2, revised 25 July 2011. Primary discussion of the conjecture and its equivalences. https://arxiv.org/abs/0910.2766v2.