The 3-decomposition conjecture is wide open.
It asserts that every finite connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching.
We show that every such decomposition is derived from a homeomorphically irreducible spanning tree (HIST).
This allows us to propose a novel reformulation of the 3-decomposition conjecture: the HIST-extension conjecture.

We also prove that the following graphs are reducible configurations with respect to the 3-decomposition conjecture: the triangle, the $K_{2,3}$, the Petersen graph with one vertex removed, the claw-square, the twin-house, and the domino.
As an application, we show that all 3-connected graphs of tree-width at most 3 or of path-width at most 4 satisfy the 3-decomposition conjecture and that a 3-connected minimum counterexample to the conjecture is triangle-free, all cycles of length at most 6 are induced, and every edge is in the centre of an induced $P_6$.

Finally, we automate the naïve part of the process of checking whether a configuration is reducible and we prove that all graphs of order at most 20 satisfy the 3-decomposition conjecture.

§ INTRODUCTION

Removing the edges of a spanning tree from a cubic graph results in a graph of maximum degree 2, which is necessarily a union of vertex-disjoint paths and cycles.
The 3-decomposition conjecture, postulated by Hoffmann-Ostenhof, see [16, 9], asserts that the spanning tree can be chosen so that all of the arising paths are of length 0 or 1.

Every finite connected cubic graph can be decomposed into a spanning tree, a 2-regular graph, and a (possibly empty) matching.

Any such decomposition $(T,C,M)$, consisting of a spanning tree $T$, a 2-regular graph $C$, and a matching $M$, is called a 3-decomposition.
So far, the 3-decomposition conjecture remains wide open.
It has been proved for the following classes: planar cubic graphs [17], traceable cubic graphs [2, 18], generalised Hamiltonian cubic graphs [6, 23], and claw-free graphs [1, 15].
All of these results exploit one of the following two approaches:

*  Reduction: prove a set of configurations to be unavoidable for the considered graph class.
Show that  each configuration is reducible with respect to the 3-decomposition conjecture. Moreover, prove that the reductions preserve the property of being in the considered class, cf. [17, 1, 15, 19].

* Manipulation of a global substructure: pick a substructure which has a property that is guaranteed for the graphs in the considered class (for example a Hamiltonian path). Manipulate it such that the final result is a 3-decomposition, cf. [2, 18, 6, 23, 5].

In this article, we focus on approach (<ref>) as a powerful tool for tackling the 3-decomposition conjecture.
We contribute new reducible configurations for the 3-decomposition conjecture and divide the reductions into two classes: coloured and uncoloured ones.

Coloured reductions.
Coloured reductions are applicable to graphs whose edges are given one of two colours (green and black) if the considered configuration respects the edge-colouring.
We show that the coloured reductions given in <Ref> already suffice to reduce each 3-decomposition to a 3-decomposition of a graph with a homeomorphically irreducible spanning tree (HIST) which is a spanning tree without degree-2 vertices (see [10] for an overview on the study of HISTs.)

Let $G$ be a cubic graph with a 3-decomposition $(T, C, M)$ in which exactly the edges of $T$ are coloured green.
If $T$ is a HIST, then $M = \emptyset$.
Otherwise $G$ with its 3-decomposition $(T,C,M)$ can be obtained by a Tutte-extension or a diamond-extension (see Figure <ref>) from a smaller cubic graph $G'$ with 3-decomposition $(T',C,M')$ where exactly the edges of $T'$ are green.

In particular, every 3-decomposition can be reduced to a 3-decomposition with a HIST by a finite sequence of Tutte- and diamond-reductions.

Observe that a cubic graph which has a HIST trivially satisfies the 3-decomposition conjecture since the edges outside the HIST form a 2-regular graph.
We exploit our two coloured reductions to propose the new HIST-extension conjecture and to prove that it is equivalent to the 3-decomposition conjecture.

(-.7,1) node (lo) [ivertexgrey,label=above:$x_u$]
(-.7,-1) node (lu) [ivertexgrey,label=below:$y_u$]
(.3,1) node (ro) [ivertexgrey,label=above:$x_v$]
(.3,-1) node (ru) [ivertexgrey,label=below:$y_v$]
[iedge, color=tcol] (lu)–(lo) (ru)–(ro);

[shift=(1.5,0), scale=.6]
(-1,.4) node (lo)
(1,.4) node (ro)
(0,0) node (c)
(-1,-.4) node (lu)
(1,-.4) node (ru) ;
[->] (lo)–(ro);
[<-] (lu)–(ru);
[below of=c, align=center, yshift=9.5] (tutte-ext) Tutte-
[above of=c, align=center, yshift=-9] (tutte-ext) Tutte-

(-.7,1) node (lo) [ivertexgrey,label=above:$x_u$]
(-.7,0) node (lm) [ivertexblack,label=left:$u$]
(-.7,-1) node (lu) [ivertexgrey,label=below:$y_u$]
(.3,1) node (ro) [ivertexgrey,label=above:$x_v$]
(.3,0) node (rm) [ivertexblack,label=right:$v$]
(.3,-1) node (ru) [ivertexgrey,label=below:$y_v$]
[iedge, color=tcol] (lu)–(lm)–(lo) (ru)–(rm)–(ro);
[iedge] (lm)–(rm);

(-.2,1) node (o) [ivertexgrey,label=above:$x_u=x_v$]
(-.7,-1) node (lu) [ivertexgrey, label=below:$y_u$]
(.3,-1) node (ru) [ivertexgrey, label=below:$y_v$]
[iedge, color=tcol] (lu)–(o)–(ru);

[shift=(1.5,0), scale=.6]
(-1,.4) node (lo)
(1,.4) node (ro)
(0,0) node (c)
(-1,-.4) node (lu)
(1,-.4) node (ru) ;
[->] (lo)–(ro);
[<-] (lu)–(ru);
[below of=c, align=center, yshift=9.5] (tutte-ext) Tutte-
[above of=c, align=center, yshift=-9] (tutte-ext) Tutte-

(-.2,1) node (o) [ivertexgrey,label=above:$x_u=x_v$]
(-.7,-1) node (lu) [ivertexgrey,label=below:$y_u$]
(.3,-1) node (ru) [ivertexgrey,label=below:$y_v$]
(-.45,0) node (lm) [ivertexblack, label=left:$u$]
(.05,0) node (rm) [ivertexblack, label=right:$v$]
[iedge, color=tcol] (lu)–(lm)–(o)–(rm)–(ru);
[iedge] (lm)–(rm);

(0,1) node (lo) [ivertexgrey, label=above:$x$]
(0,-1) node (lu) [ivertexgrey, label=below:$y$]
[iedge, color=tcol] (lu)–(lo);

[shift=(1.2,0), scale=.6]
(-1,.4) node (lo)
(1,.4) node (ro)
(0,0) node (c)
(-1,-.4) node (lu)
(1,-.4) node (ru) ;
[->] (lo)–(ro);
[<-] (lu)–(ru);
[below of=c, align=center, yshift=9.5] (tutte-ext) diamond-
[above of=c, align=center, yshift=-9] (tutte-ext) diamond-

(0,1) node (lo) [ivertexgrey, label=above:$x$]
(0,-1) node (lu) [ivertexgrey, label=below:$y$]
(0,-.5) node (du) [ivertexblack, label=right:$d_4$]
(0,.5) node (do) [ivertexblack, label=right:$d_1$]
(-.5,0) node (dl) [ivertexblack, label=left:$d_2$]
(.5,0) node (dr) [ivertexblack, label=right:$d_3$]
[iedge, color=tcol] (lu)–(du)–(dl)–(dr)–(do)–(lo);
[iedge] (du)–(dr) (dl)–(do);

Extensions and reductions. Exactly the tree-edges are coloured green. Grey vertices are those with neighbours outside of the configuration.
Tutte-extension: subdivide two green edges and join the subdivision vertices with a black edge. The two green edges may be non-incident (left figure) or incident (middle figure).
Diamond-extension: remove a green edge with ends $x$ and $y$; add a new diamond in which all edges are green except two non-incident ones; if $d_1$ and $d_4$ denote the two degree-2-vertices of the diamond, then join $d_1$ with $x$ and $d_4$ with $y$ by green edges.
The inverse operations are the corresponding reductions.

Let $G$ be a finite connected cubic graph.
Then there exists a cubic graph $G'$ admitting a HIST $T'\subseteq G'$ such that if exactly the edges of $T'$ are coloured green, then $G$ can be obtained from $G'$ by a finite sequence of Tutte- and diamond-extensions (see <Ref>).

We emphasise the strong similarities between the HIST-extension conjecture and the following theorem of Wormald.

Every connected cubic graph other than the $K_4$ can be obtained from a smaller cubic graph by one of the following three operations:

* subdivide two edges and join the subdivision vertices by a new edge,

* replace an edge by a diamond and join the degree-2 vertices of the diamond with the former ends of the replaced edge,

* take the disjoint union with a $K_4$, subdivide an edge in each component of this union and join the subdivision vertices.

The HIST-extension conjecture postulates that is is possible to replace the $K_4$ in Wormald's theorem by the substantially larger infinite ground set of all cubic graphs which allow for a homeomorphically irreducible spanning tree but, in turn, to restrict Wormald's three operations to two coloured variants of the operations (<ref>) and (<ref>).

We derive from <Ref> the equivalence of the two conjectures.

The 3-decomposition conjecture and the HIST-extension conjecture are equivalent.

Uncoloured reductions.
A subcubic graph $S$ is a reducible configuration if no minimal 3-connected counterexample to the 3-decomposition conjecture contains $S$ as a subgraph.
We show that the following six configurations are reducible:
the triangle, the $K_{2,3}$, the , the claw-square, the twin-house, and the domino.

The graphs in <Ref> are reducible.

Roughly speaking, the reducibility proofs proceed as follows:
given a cubic graph $G$ containing the reducible configuration $S$, replace $S$ by some smaller graph $S'$.
This yields a new graph $G'$ containing $S'$ and we show that every local behaviour that a 3-decomposition might exhibit on $S'$ can be extended to $S$.
Consequently, these proofs are constructive: we can obtain a 3-decomposition of a graph $G$ containing $S$ from a 3-decomposition of the graph $G'$.

[] at (-8.6,-1.5) triangle;

[] at (-5.75,-1.5) $K_{2,3}$;

[] at (-2.5,-1.5) ;

[] at (.45,-1.5) claw-square;

[] at (2.9,-1.5) twin-house;

[] at (5.3,-1.5) domino;

Reducible configurations for the 3-decomposition conjecture.
The names refer to the graphs induced by the black vertices.

Applications and minimum counterexamples.
Using the new reducible configurations enables us to extend the list of graph classes which satisfy the 3-decomposition conjecture.
Due to the constructive nature of the reducibility proofs, we obtain a method of obtaining decompositions for these graphs, too.

Every 3-connected cubic graph of tree-width 3 satisfies the 3-decomposition conjecture.
[This result is contained in the PhD thesis of the second author [13, 14] but is not published elsewhere.]

Every 3-connected cubic graph of path-width 4 satisfies the 3-decomposition conjecture.

As a further use of the new reducible configurations, we gain new insights into the structure of (potential) minimum counterexamples to the 3-decomposition conjecture.
These results are summarised in the following theorem.

If $G$ is a minimum counterexample to the 3-decomposition conjecture amongst all 3-connected cubic graphs, then it does not contain any of the graphs in Figure <ref> as a subgraph.
In particular,

* the girth of $G$ is at least 4,

* every cycle of length 4, 5, or 6 in $G$ is induced, and

* every edge of $G$ is the centre edge of an induced $P_6$.

Automatically checking reducibility
At the core of our reducibility proofs lies the aforementioned task of checking that every behaviour which a 3-decomposition might exhibit on the smaller graph $S'$ can be extended to $S$.
This leads to a lot of cases, many of which are straight-forward.
We identify these naïvely extendable cases and, in the final part of this article, we demonstrate how these can be handled algorithmically in order to focus on the remaining harder cases.
We also prove that checking for naïve extendability is an -complete problem.

Determining whether a forest is naïvely extendable is -complete.

Finally, we verify the conjecture for all small graphs employing a computer.

All graphs of order at most 20 satisfy the 3-decomposition conjecture.
In particular, a minimum counterexample has order at least 22.

We specify the basic notation and definitions in the next section.
In Section <ref> we prove that every 3-decomposition stems from an extension of a decomposition with a HIST.
We formalise the concepts of extensions and reductions, which are fundamental for this paper, in <Ref>, where we also show initial properties concerning these.
We give proofs of reducibility of the six configurations shown in <Ref> in Section <ref> (and partly in the appendix).
Naïve extensions and their complexity are discussed in Section <ref>.
In <Ref> we present all the consequences that follow from these reducible configurations, together with our computer-aided proof that such a counterexample has at least 22 vertices.

§ PRELIMINARIES

All graphs in this paper are simple and finite.
Most of the following notation is based on [11].
A graph $G$ has vertex set $V(G)$ and edge set $E(G)$.
We write $uv$ for an edge with ends $u$ and $v$ and, for $A,B\subseteq V(G)$, $E(A,B)$ denotes the set of edges with one end in $A$ and the other in $B$.
The set of neighbours of a vertex $v$ in $G$ is $N_G(v)$ or $N(v)$.
The graph obtained from $G$ by removing a subset $V'$ of $V(G)$ and all edges with at least one end in $V'$ is denoted by $G-V'$.
If $V' = \{v\}$ is a singleton, then we write $G-v$ as a shorthand for $G-\{v\}$.
Similarly, for an edge set $E'\subseteq E(G)$ we write $G-E'$ for the graph with vertex set $V(G)$ and edge set $E\setminus E'$ and we abbreviate $G-\{e\}$ to $G-e$.
A path is a graph $P$ with $V(P)=\{v_1,\ldots,v_n\}$ and $E(P) =\{v_1v_2,\ldots,v_{n-1}v_n\}$, for which we write $P=v_1\ldots v_n$.
Similarly, we write $v_1\ldots v_nv_1$ for the cycle $P+v_nv_1$.
The complete graph, the cycle, and the path on $n$ vertices are denoted by $K_n$, $C_n$, and $P_n$ respectively and $K_{r_1,r_2}$ is the complete bipartite graph with parts of cardinality $r_1$ and $r_2$.

A tree-decomposition $(T, \calV)$ of a graph $G$ consists of a tree $T$
and a family of vertex sets $\calV=\{V_i\colon i\in V(T)\} \subseteq 2^{V(G)}$ indexed by the vertices $i$ of $T$.
It satisfies that

* every vertex $v\in V(G)$ is contained is some set $V_i$,

* for each edge $uv\in E(G)$ there exists a set $V_i$ such that $\{u,v\}\subseteq V_i$, and

* the set $\{i\colon v\in V_i\}$ induces a subtree of $T$ for all $v\in V(G)$.

The width of $(T, \calV)$ is defined as $\max\{|V'|\colon V' \in \calV \}-1$.
If $T$ is a path, then $(T,\calV)$ is a path-decomposition of $G$.
Furthermore, the tree-width (respectively path-width) of $G$ is the minimal width of its tree-decompositions (respectively path-decompositions).

A decomposition of a graph $G$ is a list of subgraphs such that every edge of $G$ is contained in exactly one of the subgraphs.
We say that $G$ decomposes into the graphs in the list.
In the context of decompositions 1-regular subgraphs are called matchings.
A 3-decomposition $(T,C,M$) of a graph $G$ is a decomposition of $G$ into a spanning tree $T$, a 2-regular subgraph $C$, and a matching $M$.
An edge of  $T$, $C$, and $M$ is called $T$-edge, $C$-edge, and $M$-edge and coloured green, red, and blue when we depict 3-decompositions in figures, respectively.

§ THE HIST-EXTENSION CONJECTURE

A graph is homeomorphically irreducible if it does not contain vertices of degree 2.
We use HIST as an abbreviation for homeomorphically irreducible spanning tree.

Let $G'$ be a graph with a spanning tree $T'$.
Colour the edges of $T'$ green and all other edges of $G'$ black.
If $(G, T)$ is obtained from $(G', T')$ by either a Tutte- or a diamond-extension (see <Ref>), then $G-E(T)$ decomposes into cycles and and a matching if and only if $G'-E(T')$ does.

First observe that the respective extensions and reductions preserve the property that the green edges form a spanning tree (both only insert subdivision vertices on green edges and connect them by black edges).
Since $G'-E(T')$ is a graph of maximum degree 2 it decomposes into a 2-regular graph $C'$ and a disjoint union of paths $P'$.
If $G$ is obtained from $G'$ by a Tutte-extension, then $G$ decomposes into $T$, the 2-regular graph $C'$, and the disjoint union of $P'$ with an additional $K_2$.
Otherwise $G$ is a diamond-extension of $G'$ and decomposes into $T$, $C'$, and the disjoint union of $P'$ with a $2K_2$.
In both cases $P'$ is a matching if and only if $G-E(T)-E(C')$ is a matching.
This settles the claim.

Throughout this proof, a graph is always given with a 3-decomposition.
The edges of the tree in the decomposition are coloured green and all other edges are black.
If $T$ is homeomorphically irreducible, then $G-E(T)$ has only vertices of degree 0 and 2.
In particular, $G-E(T)$ is a disjoint union of isolated vertices and cycles and, hence, $M = \emptyset$.

From now on we may assume that $T$ contains a vertex $v$ with $\deg_T(v) =2$.
Since $(T, C, M)$ is a 3-decomposition of $G$, we obtain that $v$ is incident to an $M$-edge $uv$ in $G$.
We denote the neighbours of $u$ and $v$ as depicted in <Ref>.
Since $uv$ is an M-edge, the edges $ux_u$, $uy_u$, $vx_v$, and $vy_v$ are $T$-edges.

We can apply a Tutte-reduction here unless one of the edges $x_uy_u$ or $x_vy_v$ is present in $G$ since these would create parallels.
Hence, if neither of these edges is in $G$, then $(G, (T, C, M))$ can be obtained via a Tutte-extension from $G-\{u,v\}+\{x_uy_u, x_vy_v\}$ with the 3-decomposition $(T-\{x_uu, uy_u, x_vv, vy_v\}+\{x_uy_u, x_vy_v\}, C, M-uv)$.

By symmetry, we may assume that $x_uy_u \in E(G)$, as shown in <Ref>.
This implies that $x_uy_u$ is an $M$-edge (a $T$-edge would cause the cycle $ux_uy_uu$ in $T$ whereas a $C$-edge would disconnect the $T$-edges $ux_u$ and $uy_u$ from the rest of the tree).
We may conclude that $x_u\tilde{x}_u$ and $y_u\tilde{y}_u$ are $T$-edges, where $\tilde{x}_u$ (respectively $\tilde{y}_u$) denotes the unique neighbour of $x_u$ (respectively $y_u$) outside the triangle $ux_uy_uu$.
In particular, we obtain $\tilde{x}_u \neq \tilde{y}_u$ since $T$ is cycle-free.
This is illustrated in <Ref>.

The only obstacle to applying a Tutte-reduction using the $M$-edge $x_ux_v$ is the case where either $\tilde{x}_u=v$ or $\tilde{y}_u = v$ since this creates a parallel to the $M$-edge $uv$.
Thus, if $v \notin \{\tilde{x}_u$, $\tilde{y}_u\}$, then $G$ can be obtained by a Tutte-extension of $G'\coloneqq G-\{x_u, x_v\} + \{u\tilde{x}_u, u\tilde{y}_u\}$ with the 3-decomposition $(T-E(\tilde{x}_ux_uuy_u\tilde{y}_u)+\{\tilde{x}_uu, u\tilde{y}_u \}, C, M-\{x_uy_u\})$.

Otherwise $\tilde{x}_u = v$ or $\tilde{y}_u = v$.
Say, $\tilde{x}_u = v$ (the other case works similarly by interchanging the roles of $x$ and $y$).
We assume, as illustrated in <Ref>, that $x_u = x_v$ (otherwise rename $x_v$ and $y_v$).
Observe that $y_v\neq \tilde{y}_u$ since this would cause a cycle in $T$.
If $y_v$ and $\tilde{y}_u$ are not adjacent, then $G$ can be obtained by a diamond-extension of the graph $G-\{y_u, x_u, u, v\} + \{\tilde{y}_u\tilde{v}\}$ with the 3-decomposition $(T-E(\tilde{y}_uy_uux_uv\tilde{v})+\{\tilde{y}_u\tilde{v}\}, C,  M-\{y_ux_u, uv\})$.
If, otherwise, $\tilde{v}\tilde{y}_u \in E(G)$, then this edge is an $M$-edge (a $T$-edge would cause a cycle in $T$ and a $C$-edge would disconnect $T$).
Let $\tilde{y}_v'$ be the unique vertex in $N_G(y_v)\setminus \{\tilde{x}_u, \tilde{y}_u\}$ and let $\tilde{y}_u'$ be the unique neighbour of $\tilde{y}_u$ which is not in $\{y_u, y_v\}$.
Since $y_u$ and $v$ already have three neighbours, we obtain that $y_u\tilde{y}_u'$ and $v\tilde{y}_v'$ are not edges of $G$.
In particular, $G$ can be obtained by a Tutte-extension of $G-\{y_v,\tilde{y}_u\}+\{v\tilde{y}_v', y_u\tilde{y}_u'\}$ with the 3-decomposition $(T-\{\tilde{y}_u'\tilde{y}_u,\tilde{y}_uy_u, vy_v, y_v\tilde{y}_v'\}+\{v\tilde{y}_v', y_u\tilde{y}_u'\}, C, M-y_v\tilde{y}_u)$.

[]Degree-2 vertex[.225][c]
(-.7,2) node (lo2) [label=right:$\tilde{x}_u$]
(-.7,-2) node (lu2) [label=right:$\tilde{y}_u$]
(-.7,1) node (lo) [ivertexgrey,label=left:$x_u$]
(-.7,0) node (lm) [ivertexblack,label=left:$u$]
(-.7,-1) node (lu) [ivertexgrey,label=left:$y_u$]
(.3,1) node (ro) [ivertexgrey,label=right:$x_v$]
(.3,0) node (rm) [ivertexblack,label=right:$v$]
(.3,-1) node (ru) [ivertexgrey,label=right:$y_v$] ;
[iedge, color=tcol] (lu)–(lm)–(lo) (ru)–(rm)–(ro);
[iedge] (lm)–(rm);

[]$x_uy_u\in G$[.225][c]

(-.7,2) node (lo2) [label=right:$\tilde{x}_u$]
(-.7,-2) node (lu2) [label=right:$\tilde{y}_u$]
(-.7,1) node (lo) [ivertexgrey,label=above left:$x_u$]
(-.7,0) node (lm) [ivertexblack,label=left:$u$]
(-.7,-1) node (lu) [ivertexgrey,label=below left:$y_u$]
(.3,1) node (ro) [ivertexgrey,label=right:$x_v$]
(.3,0) node (rm) [ivertexblack,label=right:$v$]
(.3,-1) node (ru) [ivertexgrey,label=right:$y_v$] ;
[iedge, color=tcol] (lu)–(lm)–(lo) (ru)–(rm)–(ro);
[iedge] (lm)–(rm);
[iedge] (lo) to[bend right=70] (lu) ;

[]$\tilde{x}_u,\tilde{y}_u \neq v$[.225][c]

(-.7,2) node (lo2) [ivertexgrey,label=right:$\tilde{x}_u$]
(-.7,1) node (lo) [ivertexgrey,label=above left:$x_u$]
(-.7,0) node (lm) [ivertexblack,label=left:$u$]
(-.7,-1) node (lu) [ivertexgrey,label=below left:$y_u$]
(-.7,-2) node (lu2) [ivertexgrey,label=right:$\tilde{y}_u$]
(.3,1) node (ro) [ivertexgrey,label=right:$x_v$]
(.3,0) node (rm) [ivertexblack,label=right:$v$]
(.3,-1) node (ru) [ivertexgrey,label=right:$y_v$] ;
[iedge, color=tcol] (lu2)–(lu)–(lm)–(lo)–(lo2) (ru)–(rm)–(ro);
[iedge] (lm)–(rm);
[iedge] (lo) to[bend right=70] (lu) ;

[]$\tilde{x}_u = v$[.225][c]

(-.7,2) node (lo2) [label=right:$\tilde{x}_u$]
(-.7,-2) node (lu2) [label=right:$\tilde{y}_u$]
(-.2,1) node (lo) [ivertexgrey,label=above:$x_u = x_v$]
(-.7,0) node (lm) [ivertexblack,label=left:$u$]
(-.7,-1) node (lu) [ivertexgrey,label=below left:$y_u$]
(-.7,-2) node (lu2) [ivertexgrey,label=right:$\tilde{y}_u$]
(.3,0) node (rm) [ivertexblack,label=right:$v=\tilde{x}_u$]
(.3,-1) node (ru) [ivertexgrey,label=right:$y_v$] ;
[iedge, color=tcol] (lu2)–(lu)–(lm)–(lo) (ru)–(rm)–(lo);
[iedge] (lm)–(rm);
[iedge] (lo) .. controls (-1.6, 0.1) .. (lu);

Illustration of the cases appearing in the proof of <Ref>.

Throughout this proof, whenever a graph is given with a spanning tree we implicitly assume that the edges of the tree are green and all other edges are black.

Let $G$ be a finite connected cubic graph.
First assume that $G$ satisfies the 3-decomposition conjecture and let $(T, C, M)$ be a 3-decomposition of $G$.
If $T$ is homeomorphically irreducible, then $G$ trivially satisfies the HIST-extension conjecture (with an empty sequence of extensions).
Otherwise, by <Ref>, there exists a graph $G'$ with a HIST $T'$ such that $(T', C, \emptyset)$ is a 3-decomposition of $G'$ and $G$ can be obtained from $G'$ (with the green-black colouring induced by $T'$) by a finite sequence of Tutte- and diamond-extensions, that is, $G$ satisfies the HIST-extension conjecture.

Now we assume that $G$ satisfies the HIST-extension conjecture.
In particular, there exists a graph $G'$ with a homeomorphically irreducible spanning tree $T'$ such that $G$ can be obtained by a finite sequence of Tutte- and diamond-extensions from $G'$.
Since all vertices of $T'$ are of degree 1 or 3, the graph $G-E(T')$ decomposes into a 2-regular graph $C$ and isolated vertices.
Thus, $(T',C, \emptyset)$ is a 3-decomposition of $G'$.
By <Ref>, $G$ satisfies the 3-decomposition conjecture.

§ EXTENSIONS AND REDUCTIONS

In the following we formalise the replacement of an induced subgraph $R$ of a cubic graph $G$ by some other subcubic graph $S$.
Intuitively, this means that we add the graph $S$ to $G-V(R)$ and connect the vertices of $S$ “appropriately”.
In order to define what “appropriately” means, we augment $R$ to a graph $X$ by adding leaves to all vertices of $R$ of degree less than 3 such that all vertices of $R$ are of degree 3 in $X$.
We do the same for $S$ and use these additional vertices to specify the edges between $S$ and $G-V(R)$.

This leads us to the definition of a template graph which is a graph $X$ whose vertex set is partitioned into a set of inner vertices $I(X)$ and a set of outer vertices $O(X)=\{v_1,\ldots,v_k\}$.
All inner vertices have degree 3 and all outer vertices have degree 1.
We call $X-O(X)$ the core of $X$ and denote it by $c(X)$.
For a subcubic graph $R$, the unique template graph $X$ (up to labelling the outer vertices) with $R$ as its core is called the template graph of $R$.
The template graph of the domino can be seen in on the right of <Ref>, where the outer vertices are grey.

We can now define the replacements we need:
let $R$, $S$ be subcubic graphs and let $X$, $Y$ be their template graphs.
Furthermore, let $G$ be a cubic graph containing an induced subgraph $R'$ isomorphic to $R$, that is, $\varphi(R) = R'$ for some isomorphism $\varphi$.
Since $G$ is cubic, any vertex $\varphi(v)\in R'$ has exactly as many incident edges to vertices in $G-V(R')$ as $v$ has neighbours in $O(X)$.
Thus, we can identify each neighbour $w$ of $v$ that is an outer vertex with a neighbour $\psi(w)$ of $\varphi(v)$ that is not in $R'$.

The graph

(G-V(R'))∪S     	    +  {vψ(w)vw∈Y, w∈O(Y)}

=    (G-φ(I(X))) ∪c(Y)      +  {vψ(w)vw∈Y, w∈O(Y)}

is the $(X,Y,\varphi)$-transformation of $G$.
(Note that the resulting graph does not depend on the choice of $\psi$.)
An $(X,Y)$-transformation of $G$ is a graph $G[X\to Y] \coloneqq G_\varphi[X\to Y]$ for some isomorphism $\varphi\colon c(X)\to R'$ with $R'\subseteq G$.
Moreover, a pair $(X,Y)$ of template graphs with $O(X) = O(Y)$ is called an $(X,Y)$-transformation.
Transformations are called extensions if $|V(X)|<|V(Y)|$ and reductions if $|V(X)| > |V(Y)|$.

We depict $(X,Y)$-transformations as seen in <Ref>.
We use such illustrations to describe the transformations since they are more convenient and easier to understand than formally writing down vertex and edge sets.
We omit the labels of the outer vertices; their positioning shows which of these coincide.

at (-1.25,0.6) $v_1$;
at (1.25,0.6) $v_2$;
at (-1.25,-0.6) $v_3$;
at (1.25,-0.6) $v_4$;
at (3.25,1.25) $v_1$;
at (5.75,1.25) $v_2$;
at (3.25,-1.25) $v_3$;
at (5.75,-1.25) $v_4$;
Template graphs and transformations:
this example illustrates the extension where $c(X)$ is the $K_2$ and $c(Y)$ is the domino.
The outer vertices of the template graphs are grey.

Note that the outer vertices of the template graph do not necessarily correspond to distinct vertices of the graph $G$ containing the core.
As a result, $G$ need not have a subgraph isomorphic to $X$, just to $c(X)$.
Additionally, the graphs $G[X\to Y]$ are not necessarily simple, even if $G$, $X$, and $Y$ are.
However, we only apply transformations which yield a simple graph.
A sufficient condition for this is that no vertex in the core of $Y$ has multiple adjacent outer vertices, or equivalently, that the minimum degree in the core of $Y$ is 2.

Compatible extensions and reducible configurations.
A reducible configuration is a (subcubic) graph $S$ that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture.
In this case we also say that $S$ is reducible.

Our goal is to describe $(X,Y)$-extensions that allow us to extend 3-decompositions.
For ease of use, an $(X,Y)$-extension is 3-compatible if, for every cubic graph $G$ with a 3-decomposition and for every extension $H\coloneqq G[X\to Y]$ of $G$, the graph $H$ also has a 3-decomposition.
In fact, in our proofs that certain transformations are 3-compatible we show how to construct a 3-decomposition of $H$ from one of $G$.

Finding a 3-compatible extension $(X,Y)$ is very helpful for proving that the core of $Y$ is reducible.
The following lemma exhibits a property that implies reducibility if it is satisfied by such an extension.

Let $(X,Y)$ be a 3-compatible extension.
The core $c(Y)$ is reducible if for every 3-connected cubic graph $H$ containing (a subgraph isomorphic to) $c(Y)$

* $H$ has a 3-decomposition, or,

* $c(Y)$ is induced and the reduction $G=H[Y\to X]$ is a simple 3-connected graph.

Assume $H$ is a minimal counterexample containing $c(Y)$ as an induced subgraph and let $G\coloneqq H[Y\to X]$ be both simple and 3-connected.
Since $H$ is a minimal counterexample, $G$ has a 3-decomposition and, because $(X,Y)$ is 3-compatible, $H=G[X\to Y]$ also has a 3-decomposition, which is a contradiction.

Whenever possible, we want to apply this lemma.
Therefore, in order to prove that a certain configuration $S$ is reducible, we proceed as follows:

* Prove a certain $(X,Y)$-extension to be 3-compatible where $S=c(Y)$.

* Check that in any simple 3-connected cubic graph $H$ containing a subgraph $S'$ isomorphic to $S$, $S'$ is actually induced and the $(Y,X)$-reduction of $H$ yields another simple 3-connected graph.

The first option of the lemma lets us assume that the graph obtained from the reduction is still sufficiently large by excluding some small graphs that already have 3-decompositions.
The procedure described here is actually entirely constructive in the sense that given a graph $H$, we can perform reductions using the reducible structures as long as they are present.
Let $G$ be the resulting graph.
If we can find a 3-decomposition for this smaller graph $G$, then we can undo the reductions step by step and extend our decompositions to the larger graphs, finally obtaining one for $H$.

To use this procedure means we regularly need to check whether subgraphs are induced and whether reductions yield simple 3-connected graphs.
To facilitate this, we end this section with two lemmas that are helpful in this respect.
Their proofs use Menger's theorem [20, 11] when verifying 3-connectivity.

Let $H$ be a 3-connected cubic graph that contains the core of a template graph $Y$ with three outer vertices and let $X$ be the template graph of the $K_1$.
Then $c(Y)$ is induced and the reduction $G\coloneqq H[Y\to X]$ is 3-connected.
If, additionally, $H-V(c(Y))$ consists of more than one vertex, then $G$ is simple.

The 3-connectivity of $H$ implies that there are at least three edges joining $H-V(c(Y))$ with $c(Y)$.
Since $Y$ has three outer vertices, there are exactly three such edges and $c(Y)$ is induced.
Furthermore, if $H-V(c(Y))$ has more than one vertex, then the three neighbours of $c(Y)$ are distinct:
if all three of the neighbours coincide, then $H$ is not connected, which is a contradiction. If exactly two of them coincide, then we find a 2-edge cut in $H$, which contradicts to $H$ being 3-connected.
Consequently, $G$ is simple in this case.

To see that $G$ is 3-connected, consider two distinct vertices $u$ and $v$ of $G$.
If neither $u$ nor $v$ is the vertex in $c(X)$, then they are in $H$ and we obtain three internally vertex-disjoint paths linking them in $H$.
At most one of these paths can use vertices of $c(Y)$ since $|E(V(H)\setminus V(c(Y)), V(c(Y)))| = 3$.
Thus, by potentially replacing the path segment through $c(Y)$ by the vertex in $c(X)$, we obtain three paths in $G$.

If $u$ is the vertex in $c(X)$, then let $u' \in V(c(Y))$.
We obtain three vertex-disjoint $u'v$-paths in $H$, each of which uses one of the edges from $c(Y)$ to the rest of $H$.
Thus we can replace these initial path segments by the edges incident to $u$ in $G$ and obtain the required paths there.

Let $H$ be a 3-connected cubic graph that contains the core of a template graph $Y$ with four outer vertices and $|V(c(Y))| \geq 5$.
Moreover, let $X$ be the template graph of the square.
Then $c(Y)$ is induced and the reduction $G\coloneqq H[Y\to X]$ is simple and 3-connected.

The 3-connectivity of $H$ implies that there are at least $3$ edges between $c(Y)$ and $H-c(Y)$.
Since $Y$ only has four outer vertices, $c(Y)$ is induced in $H$ and $G$ is simple because the square has minimum degree 2.

To verify the 3-connectivity of $G$, we consider two vertices $u$ and $v$ of $G$.
If both are not vertices of the square, then we obtain three internally vertex-disjoint paths linking them in $H$.
At most two of these paths use vertices of $c(Y)$ and all other paths exist in $G$.
If a single path passes $c(Y)$, then it can be replaced by one in the square and so can two paths unless they both need to connect non-adjacent vertices of the square.
In this case, we can cross the paths by pairing the start of one with the end of the other and vice versa.
In all cases we obtain the three desired disjoint paths.

If one vertex, say $v$, is in the square and the other is not, then the paths obtained in $H$ consist of one path that only meets $c(Y)$ in $v$ and two more paths that start with a path segment in $c(Y)$.
However, the square contains such path segments as well.
Finally, if both vertices are in the square, replace $u$ its neighbour $x$ outside of the square.
By the previous case, we obtain a path from $x$ to $v$ that only meets the square in $v$.
We extend this path to $u$ and take the two disjoint paths the square provides.
Thus $G$ is also 3-connected.

§ NEW REDUCIBLE CONFIGURATIONS

In this section we prove <Ref>.

For convenience, we repeat <Ref> here.

[] at (-8.6,-1.5) triangle;

[] at (-5.75,-1.5) $K_{2,3}$;

[] at (-2.5,-1.5) ;

[] at (.45,-1.5) claw-square;

[] at (2.9,-1.5) twin-house;

[] at (5.3,-1.5) domino;

All but one of these proofs adhere to the procedure described in the previous section and we illustrate it using the triangle.
For the remaining graphs we focus on the more challenging cases and refer to the appendix for the others.
The first step for the triangle is to find an $(X,Y)$-extension that is 3-compatible and where $c(Y)$ is the triangle.
For this we choose $X$ such that $c(X)$ is a single vertex.

The extension shown in <Ref> is 3-compatible.

at (-0.25,0) $u$;
at (4.35,0.65) $u_1$;
at (2.85,-0.5) $u_2$;
at (5.15,-0.5) $u_3$;
Transforming a node to a triangle.

Let $G$ be a cubic graph with a 3-decomposition $(T,C,M)$ and let $H$ be an $(X,Y)$-extension of $G$, where the extension is the one from <Ref>.
We wish to extend the decomposition of $G$ to it.
To this end, we start by determining the possible behaviours at $u$.
As $T$ is a spanning tree, at least one of the edges incident to $u$ is in $T$.
If it is exactly one, then the other two are part of a cycle.
If there are exactly two, then the missing edge is in the matching and, otherwise, there are three.
These options are shown in <Ref>, up to rotational symmetry.
Recall that edges of $T$ are green, those of $C$ red, and those in $M$ blue.

Possible behaviour of a 3-decomposition at a single node.

We now need to turn the decomposition $(T,C,M)$ of $G$ into one of $H$, which we do by distinguishing between the possible behaviours described above.
The extensions obtained are shown in <Ref>.
We describe how these depictions are to be read, using the first case as an example.
The remaining ones should then be self-explanatory.

Extending a 3-decomposition to a triangle.

If we only have a single $T$-edge, say $uv_1$, incident to $u$, we make the following extension:
we begin by setting $T'=T-I(X)+I(Y)$, $C' = C-I(X) + I(Y)$, and $M' = M-EX$.
These are a spanning forest, a disjoint union of cycles together with a $v_2v_3$-path, and a matching.
The forest has four components, three of them being the vertices $I(Y)$ of the triangle.

By adding the edges $u_1v_1,\ u_1u_2$, and $u_1u_3$ to $T'$ we obtain a spanning tree of $G$ and adding the remaining edges incident to $u_2$ and $u_3$ to $C'$ turns it a disjoint union of cycles.
As a result $(T',C',M')$ is a 3-decomposition of $G$.

The figure illustrates how to extend the decomposition for the remaining two behaviour types, giving us a 3-decomposition of $H$ in all cases, and thus showing that the extension is 3-compatible.

We can now complete the second step to obtain the reducibility of the triangle.

The triangle is reducible.

Here we regard the inverse $(Y,X)$-reduction shown in <Ref>.
Let $H$ be a simple 3-connected cubic graph containing a triangle $u_1u_2u_3u_1$.
By <Ref> it suffices to prove that the triangle is induced and that the $(Y,X)$-reduction $G$ is simple and 3-connected.
In fact, we may assume that $H\neq K_4$ as the $K_4$ has a 3-decomposition (for example by <Ref>).
But all these properties follow directly from <Ref>.

Now that we have illustrated the general concept, let us fix some notation for the remainder of this section.
Whenever we regard a transformation, we denote the smaller graph by $X$ and the larger one by $Y$, unless explicitly stated otherwise.
Furthermore, when we prove that an extension is 3-compatible, we write $G$ for the smaller graph containing the core of $X$ and $H=G[X\to Y]$ is an $(X,Y)$-extension of $G$.
The 3-decomposition of $G$ is $(T,C,M)$ and we want to construct a 3-decomposition $(T',C', M')$ for $H$.

Next, we look at three further examples of 3-compatible extensions that are straight-forward.
As such the proof of the following lemma can be found in the appendix.

The extensions shown in <Ref> are 3-compatible.

[]Transforming a vertex into a $K_{2,3}$.[][c]

[]Transforming a square into a claw-square.[][c]

[scale = .9]

[]Transforming an edge into a domino.[][c]

[scale = .9]

Three straight-forward 3-compatible extensions.

By completing the second step for the $K_{2,3}$ and the claw-square we get reducibility for the next two configurations.

The $K_{2,3}$ and the claw-square are reducible.

Regard the $(Y,X)$-reductions in <Ref>.
By <Ref> and <Ref> it suffices to prove that, given a 3-connected cubic graph $H$ with $|H|>6$ containing the core of $Y$, $c(Y)$ is induced and the reduction $G\coloneqq H[Y\to X]$ is simple and 3-connected.
This holds for the $K_{2,3}$ by <Ref> (since we excluded the $K_{3,3}$) and for the claw-square by <Ref>.

Next we take a look at the  and the twin-house.

The extension shown in <Ref> is 3-compatible.

Transforming a vertex into a .[.5][c]

at (0,0.25) $u$;

at (3.55,0.35) $u_1$;
at (4,0.35) $u_2$;
at (3.15,-0.2) $u_3$;
at (4.35,-0.2) $u_4$;
at (3.5,-0.75) $u_5$;
at (3.05,0.75) $u_6$;
at (4.5,0.75) $u_7$;
at (2.5,-0.5) $u_8$;
at (5,-0.5) $u_9$;

Extending a local behaviour at $u$.[.475][c]

Transforming the .

We note that the , like the triangle, is symmetric.
Thus, we only need to check the three possible behaviours seen in <Ref>.
Of these, the first and the last are straight-forward and can be found in the appendix.
This leaves the second one, where an $M$-edge is at the single vertex, and we extend the decomposition as shown in <Ref>.

Note that the removal of the edge $uv_1$ and $uv_3$ from $T$ (where the vertex names are taken from <Ref>) creates three connected components, one containing only $u$ and one with $v_2$ and $v_3$, respectively.
By adding all edges (including $v_2u_5$) but those on the cycle $u_1u_4u_3u_2u_5u_1$ to this forest we obtain a spanning tree $T'$ and adding the excluded cycle to $C$ yields $C'$.
Now $(T',C',M\setminus\{v_2u_5\})$ is a 3-decomposition of $H$.

The twin-house is reduced to the square, which has significantly more possible local behaviours than the $K_1$ or the $K_2$.
In order to reduce the amount of cases that need to be extended, we show that some can be transformed into one another.
Again, this is found in the appendix and we only show how to deal with the problematic cases in the proofs here.

The extension shown in <Ref> is 3-compatible.

[]Transforming a square into a twin-house.[.45][c]

at (-1,0.5) $u_1$;
at (1,0.5) $u_2$;
at (-1,-0.5) $u_3$;
at (1,-0.5) $u_4$;
at (3.5,0.75) $u_1$;
at (5.5,0.75) $u_2$;
at (3.5,0) $u_5$;
at (5.5,0) $u_6$;
at (3.5,-0.75) $u_3$;
at (5.5,-0.75) $u_4$;

[]Two local behaviours without a straight-forward extension.[.45][c]

[scale =.75]

[]Extending the first behaviour.[.45][c]

[]Extending the second behaviour.[.45][c]

[scale =.75]

Transforming the twin-house.

For this extension, we regard the local behaviours in <Ref> and refer to the appendix for the remaining ones.

For the first forest, we note that the removal of the edge $u_1u_2$ (using the terminology from <Ref>) from $T$ creates two connected components, one containing $u_1$ and one containing $u_2$.
By symmetry we may assume that the component containing $u_2$ also contains $u_3$ and $u_4$.
Once we remove the edge $u_3u_4$ as well, we end up with three components.
One of these contains $u_1$ whereas the other two either contain $u_2,u_3$ and $u_4$ or $u_2,u_4$ and $u_3$.
The first assignment we now make is illustrated in <Ref>, the second is analogous.
By replacing the square by the twin-house and adding the edges $u_1u_5, u_5u_3, u_2u_6, u_6u_4$ or $u_1u_5, u_5u_4, u_2u_6, u_6u_3$ to the forest, we obtain a spanning tree $T'$ of $H$.
The missing edges are $u_1u_2, u_5u_4, u_6u_3$ or $u_1u_2, u_5u_3, u_6u_4$, which form a matching $M'$ together with $M\setminus\{u_1u_3, u_2u_4\}$.
Thus $(T',C,M')$ is a 3-decomposition of the extended graph.

For the second forest, removing the three edges $u_1u_3, u_3u_4, u_4u_2$ from $T$ yields a spanning forest with four components, two of which are the isolated vertices $u_3, u_4$.
By replacing the square by the twin-house and adding the edges $u_1u_2, u_1u_5, u_2u_6$ to the forest, we obtain a spanning tree of $G-\{u_3,u_4\}$.
We can connect these last two vertices by using their incident edges in $M$ to obtain a spanning tree $T'$ of $G$ as shown in <Ref>.
We then take $M'$ to be the set $M$ without the edge $u_1u_2$ and the two edges we just used, which is still a matching.
The remaining edges in the twin-house form a $C_4$ which we add to $C$ to obtain $C'$.
Then $(T',C',M')$ is a 3-decomposition of $G$.

We now obtain reducibility for both.

The  and the twin-house are reducible.

The $(Y,X)$-reductions in <Ref> and <Ref> yield simple 3-connected graphs by <Ref>.
By <Ref> both graphs are reducible.

This just leaves the domino, whose reducibility is by far the most difficult to prove.
If we regard the reduction to the square again, then all but one case is straight-forward, which is the one shown on the left in <Ref>.
However, this case is difficult to remedy and requires us to know more about the structure of the graph $G$ in which this occurs.
To obtain this information, we first attempt to reduce the domino to a single edge, for which the corresponding extension is 3-compatible by <Ref>.
If this reduction yields a 3-connected graph, then we are done.
Otherwise we have acquired enough information to deal with the only problematic case occurring in the reduction to the square.

The bad local behaviour for the domino.

Let $(X,Y)$ be the extension and $(X,Z)$ be the reduction of the square shown in <Ref>.
Moreover, let $G$ be a 3-connected graph containing the core of $X$ such that its $(X,Z)$-reduction is not 3-connected.
If $G$ has a 3-decomposition, then also the $(X,Y)$-extension of $G$ has a 3-decomposition.

at (-1,0) $u_1$;
at (1,0) $u_2$;
at (3.5,0.5) $u_1$;
at (5.5,0.5) $u_2$;
at (3.5,-0.5) $u_3$;
at (5.5,-0.5) $u_4$;
at (8,0.75) $u_1$;
at (10,0.75) $u_2$;
at (8,0) $u_5$;
at (10,0) $u_6$;
at (8,-0.75) $u_3$;
at (10,-0.75) $u_4$;
Transforming a square into a domino or an edge.

Let $G$ be a graph as in the claim and let $(T,C,M)$ be a 3-decomposition of $G$.
Furthermore let $H$ be the extension $G[X\to Y]$ and $H'$ the reduction $G[X\to Z]$.
If any local behaviour other than the one in <Ref> occurs, we can extend the decomposition of $G$ to $H$.
Thus, we restrict ourselves to the forest $T_X$ with $E(T_X)=\{v_2u_2, u_2u_1, u_1u_3, u_3u_4, u_4v_4\}$ (where we use the names from <Ref> and denote the outer vertex incident to $u_i$ by $v_i$).

If we remove the three edges of $T_X$ in the square, then we end up with four components, the vertices $u_1$ and $u_3$ and components $u_2\in H_2, u_4\in H_4$.
If $v_3\notin V(H_4)$, then we take all edges except those on the cycle $u_1u_2u_6u_5u_1$ to be part of the tree component, as shown in <Ref>.
This results in a spanning tree since each of the five edges added connects different components and its complement is the matching $M\setminus\{u_1v_1, u_3v_3, u_2u_4\}$ and the cycles in $C$ together with $u_1u_2u_6u_5u_1$.
This lets us assume that $v_3\in V(H_4)$.
Note that a symmetric assignment (leaving the cycle $u_5u_6u_4u_3u_5$) lets us assume that $v_1\in V(H_2)$.
Now let $C_1$ and $C_3$ be the unique cycles in $T+u_1v_1$ and $T+u_3v_3$, which are disjoint in the situation we are in now.

We claim this shows that $H'$ is 3-connected, contrary to our assumption.
The graph $H'$ is simple since the neighbours of $u_1$ are distinct, they are in different components of $T-u_1u_3$.
The same holds for the neighbours of $u_2$.
If $H'$ were not 3-connected, then a partition $(A',B')$ of $V(H')$ exists such that $E_{H'}(A',B')$ contains at most two edges.
We now regard the partition $(A,B)$ of $V(G)$ obtained by adding $u_3$ to the set containing $u_1$ and $u_4$ to the set containing $u_2$.
Next, we compare the sets $E_{H'}(A',B')$ and $E_{H}(A,B)$.
An edge $xy\in E_{H'}(A',B')$ is also in $E_{H}(A,B)$ if neither of its ends is $u_1$ or $u_2$.
If just one of them is, say $x$, then it corresponds to a unique edge in $E_{H'}(A',B')$, where $x$ is potentially replaced by the vertex $u_3$ or $u_4$.
Only the edge $u_1u_2$ corresponds to multiple edges in $E_{H'}(A',B')$, namely to the edges $u_1u_2$ and $u_3u_4$.

Since $G$ is 3-connected, we get that $|E_{H'}(A',B')| = 2,\ |E_{H}(A,B)|=3, \ u_1u_2\in E_{H'}(A',B')$, and $u_1u_2, u_3u_4\in E_{H}(A,B)$.
This lets us assume that $u_1,u_3\in A$ and $u_2,u_4\in B$.
Both cycles $C_1$ and $C_3$ contain an element of $A$ and one of $B$, resulting in a cut of these cycles.
These cuts have at least two edges crossing, giving us a total of at least four since the cycles are disjoint, which is a contradiction.

The domino is reducible.

In light of the new situation, we cannot just apply Lemma <ref>.
Let $H$ be a minimal counterexample containing the domino, that is, $H$ is a 3-connected cubic graph without a 3-decomposition.
Since all cubic graphs on six vertices have a 3-decomposition by <Ref>, we may assume that $H$ has more vertices than the ones in the domino.
Also, because $H$ is 3-connected, we may assume that the domino is induced.

If we can replace the domino by a single edge without harming 3-connectivity as shown in <Ref>, then we obtain a 3-decomposition of $H$ by <Ref>, a contradiction.
(Note that all 3-connected cubic graphs are simple.)

So we may assume that this is not the case.
By replacing the domino by a square as shown in <Ref>, we obtain a new graph $G$ which is simple and 3-connected by <Ref>.
By minimality of $H$, $G$ has a 3-decomposition and satisfies the premise of <Ref> (since the reduction of the square to an edge corresponds to the reduction of the domino in $H$ to an edge directly).
This gives us a contradiction.

§ NAÏVE EXTENSIONS AND THEIR COMPLEXITY

Our goal in this section is twofold.
First we describe a method of determining whether an extension is 3-compatible.
In the case that it is not, we get a reduced amount of local behaviours that need to be checked manually.
This greatly reduces the amount of work required in the proofs in the previous section, in particular, all the cases in the appendix are covered by this method.
Finally, we prove that the problem solved by this method is -complete.

Algorithmically checking 3-compatibility.
For the first part, assume we want to prove that an $(X,Y)$-extension is 3-compatible for template graphs $X,Y$.
Let $T_X$ be a spanning forest of $X$.
We say that $T_X$ is 3-consistent if

* every component of $T_X$ contains an outer vertex and

* every component of $X-E(T_X)$ is a single vertex, a single edge, a cycle, or a path joining two outer vertices of $X$.

We denote the set of edges that form a component of $X-E(T_X)$ by $M_X$ and write $C_X$ for the union of the cycles in $X-E(T_X)$.
See <Ref> for two examples of 3-consistent forests.

The requirements for a forest to be 3-consistent are all necessary for it to be a restriction of a 3-decomposition.
In other words, if a cubic graph $G$ contains $c(X)$ as an induced subgraph and has a 3-decomposition $(T,C,M)$, then the restriction $T_X$ of $T$ to $X$ is 3-consistent.

Recall that $X$ is not necessarily a subgraph of $G$ (just the core of $X$ is), but we treat it as one since its edges can be identified with ones of $G$.
Thus, the restriction of $T$ to $X$ is the subgraph of $X$ containing the edges that correspond to ones in $T$.
Further, we remark that the restriction of $T$ to $X$ is not necessarily connected, and the restrictions of $C$ and $M$ to $X$ are $C_X$ and $M_X$, where $C_X$ may now contain paths in addition to cycles.

An assignment is a function $f\colon O(X) \to \{\texttt{t},\texttt{c},\texttt{m}\}$.
We say that $T_X$ realises $f$ if for each vertex $v\in O(X)$ its incident edge $e$ satisfies that $e\in T_X$ ($e\in C_X$, $e\in M_X$) if $f(v) = \texttt{t}$ ($f(v) = \texttt{c}$, $f(v) = \texttt{m}$).

A 3-consistent forest $T_X$ is naïvely extendable to $Y$ if there exists a 3-consistent forest $T_Y$ of $Y$ such that

* $T_Y$ realises the same assignment as $T_X$ and

* two outer vertices of $X$ are in the same component of $T_X$ if and only if they are in the same component of $T_Y$.

An example of a naïvely extendable forest is shown in <Ref>.

An example of a 3-consistent forest for the template graph of the edge that is naïvely extendable to the template graph of the domino.

We show that a naively extendable forest $T_X$ allows us to extend a 3-decomposition that locally behaves like $T_X$.

If $G$ has a 3-decomposition $(T,C,M)$ such that the restriction $T_X$ of $T$ to $X$ is naïvely extendable to $Y$ with forest $T_Y$, then the extension $H=G[X\to Y]$ has a 3-decomposition.

We verify that the decomposition $(T',C',M')$ of $H$ which we now define is, indeed, a 3-decomposition of $H$.
The graph $T'$ contains all vertices of $H$ and the edges in $E(T)\setminus E(T_X)\cup E(T_Y)$.
Similarly, $E(C')$ is the set $E(C)\setminus E(C_X)\cup E(C_Y)$ (and $C'$ contains all vertices of $H$ that are incident to one of these edges).
Finally, $M'\coloneqq M\setminus M_X\cup M_Y$.

We first prove that $T'$ is a spanning tree.
To show that $T'$ is connected, fix a vertex $v\in H-V(c(Y)) = G-V(c(X))$.
There exists a path $P$ in $T$ from this vertex to every other vertex in $G-V(c(X))$.
If $P$ does not use vertices of $c(X)$, then it is present in $T'$.
Otherwise $P$ contains a subpath $P'$ which links two outer vertices of $X$.
This places them in the same component of $T_X$ and they are connected in $T_Y$.
Thus we can replace every such subpath in $T_X$ by one in $T_Y$ to obtain a path in $T'$.
Any vertex $w\in c(Y)$ is in the same component of $T_Y$ as an outer vertex, which is connected to $v$, making $T'$ connected.

Suppose now that $T'$ contains a cycle $K$.
It cannot be contained in $H-V(c(Y))$ and, hence, $K$ consists of paths using edges in $E(T)\setminus E(T_X)$ and paths using edges in $E(T_Y)$.
By choosing a cycle that consists of a minimal amount of such segments, we can ensure that it enters every component of $T_Y$ at most once.
Any such path can be replaced by one in $T_X$, giving us a cycle in $T$ which is a contradiction.

The set $M'$ is a matching since the edges that are in $M\setminus M_X$ and those in $M_Y$ are independent.
So if $e,e'\in M'$ share an end, we may assume that $e\in M\setminus M_X$ and $e'\in M_Y$.
Therefore, their common end is a vertex in $O(X)$.
In this case $e'\notin M_X$, giving us $e'\notin M_Y$ since $f(e')\neq \texttt{m}$, where $f$ is the assignment realised by $T_X$, which is a contradiction.

Finally, for $v\in H$, we take a look at the number of edges in $C'$ incident to $v$.
If $v\in c(Y)$ or $v$ is in $H$ but not adjacent to $c(Y)$, then this degree is either 2 or 0.
This just leaves the vertices in $H$ adjacent to $c(Y)$ or, equivalently, those of $G$ adjacent to the $c(X)$.
Since $T_X$ and $T_Y$ realise the same assignment, any edge from a vertex of $G-c(X)$ to $c(X)$ is in $C_X$ if and only if the corresponding edge from $H-c(Y)$ to $c(Y)$ is in $C_Y$.
Consequently, the degree of these vertices remains the same in $C$ and $C'$, yielding a degree of 0 or 2 here as well.

The proof of <Ref> is constructive in the sense that, given a 3-decomposition for $G$ as in the statement, we can construct a 3-decomposition for $H$.
We can now automate the proofs we relegated to the appendix in the previous section.

To prove that an $(X,Y)$-extension is 3-compatible, we show that any 3-consistent forest of $T_X$ of $X$ satisfies

* $T_X$ is naïvely extendable to $Y$ or

* any $(X,Y)$-extension $H=G[X\to Y]$ of a graph $G$ has a 3-decomposition if $G$ has a 3-decomposition $(T,C,M)$ for which the restriction of $T$ to $X$ is $T_X$.

This suffices as any 3-decomposition $(T,C,M)$ of a graph $G$ containing an induced $c(X)$ has a 3-consistent restriction $T_X$ of $T$ to $X$ by <Ref>.
If $T_X$ is naïvely extendable, then $H$ has a 3-decomposition by <Ref> and otherwise such a decomposition exists by (<ref>).

The task of determining all 3-consistent forests and checking whether they are naïvely extendable can be accomplished algorithmically.
We have implemented this
GitLab repository containing 3-decompositions for connected cubic graphs of order at most 20 and code to check naïve extensions,
February 2022.
and the local behaviours covered in <Ref> are exactly the ones that are not naïvely extendable, that is, where (<ref>) applies (disregarding symmetric cases).

The complexity of naïve extensions.
We now prove that the existence of a naïve extension is -complete.
We actually restrict ourselves to the subproblem of finding a 3-consistent forest $T_Y$ that realises some assignment $f$.
The reduction is based on the one for the integral multicommodity flow problem [12].

Given a template graph $Y$ and an assignment $f$, checking whether a 3-consistent forest $T_Y$ for $Y$ exists that realises $f$ is -complete.

The problem is in  since a spanning forest $T_Y$ of $Y$ can be checked to be 3-consistent and realise $f$ in polynomial time.
To prove -hardness we use a reduction from .
Let $F$ be a formula in  with variables $x_1,\ldots, x_n$ and clauses $C_1,\ldots, C_m$.
We assume that for every variable $x$ both $x$ and $\bar{x}$ occur equally often in the clauses.
This is without loss of generality since we can add additional clauses of the form $x\lor x\lor \bar{x}$ or $x\lor \bar{x}\lor \bar{x}$ as required to reach the desired state.

We first note that we can force edges $uv$ to end up in the tree part $T_Y$ by subdividing them and adding a leaf to the subdivision vertex whose incident edge is in the matching.
Formally, we remove $uv$ and add edges $uw$, $vw$, $wy$, where $w,y$ are new vertices and $y$ is an outer vertex.
By setting $f(y)=\texttt{m}$, $wy$ needs to be in $M_Y$ and both $uw$ and $vw$ are necessarily in $T_Y$.
For simplicity, we refer to such a gadget as a forced tree-edge and colour them in green in our illustrations (without depicting the additional vertices they contain).

With this gadget at hand, we can describe the clause and variable gadgets we construct.
Clause gadgets are very simple and shown in <Ref>.
They just consist of a vertex $c_j$ incident to three forced tree-edges, whose ends are in the variable gadgets (we describe where momentarily).
Each such edge corresponds to one of $C_j$'s literals.

The variable gadget for $x_i$ consists of two paths of length $4\ell_i + 1$ which coincide in their ends $s_i$ and $t_i$ and are disjoint otherwise.
Here $\ell_i$ is the amount of occurrences of $x_i$ (or $\bar{x}_i$) in $F$.
We call one of these paths the upper path and the other the lower one.
In this gadget, we partition the $4\ell_i$ distinct vertices on the upper and lower paths into $\ell_i$ blocks of four consecutive vertices and each block on the upper path corresponds to an occurrence of $x_i$ while each block on the lower path corresponds to an $\bar{x_i}$ in some clause.
Furthermore, the $\ell$th vertices of the upper and lower path are connected by a forced tree-edge for all even $\ell$.
This is visualised in <Ref>.

The complete graph now concatenates all the variable gadgets by adding edges from $s_i$ to $t_{i+1}$ for $i\in\{1.\ldots,n-1\}$.
It adds a leaf to $s_1$ and $t_n$, where the edges are required to be part of $C_Y$ (by setting the $f$-value of the outer vertices to ).
A forced tree-edge in a clause gadget corresponding to a literal $L$ is connected to the third vertex in the block that corresponds to $L$.
Finally, all the first vertices in a block are connected by a forced tree-edge to a path consisting of only forced tree-edges that ends in two more leaves.
These two leaves are assigned an $f$-value of .
The construction of $Y$ runs in polynomial time, so we just need to prove that $F$ is satisfiable if and only if there exists a 3-consistent forest $T_Y$ realising $f$.

[node,label=left:$s_i$] (s) at (0,0) ;
[node,label=right:$t_i$] (t) at (7,0) ;

[node] (u1) at (1,1) ;
[node] (u2) at (2,1) ;
[node] (u3) at (3,1) ;
[node] (u4) at (4,1) ;
[node] (u5) at (6,1) ;

[node] (l1) at (1,-1) ;
[node] (l2) at (2,-1) ;
[node] (l3) at (3,-1) ;
[node] (l4) at (4,-1) ;
[node] (l5) at (6,-1) ;

[edge] (s) to (u1) to (u2) to (u3) to (u4);
[dotted] (u4) to (u5);
[edge] (u5) to (t);
[edge] (s) to (l1) to (l2) to (l3) to (l4);
[dotted] (l4) to (l5);
[edge] (l5) to (t);

[edge,tcol] (u2) to (l2);
[edge,tcol] (u4) to (l4);
[edge,tcol] (u5) to (l5);

[decorate,decoration=brace,amplitude=10pt] (0.9,1.1) to node [black,midway,yshift=0.6cm] an occurrence of $x_i$ (4.1,1.1);
[decorate,decoration=brace,amplitude=10pt, mirror] (0.9,-1.1) to node [black,midway,yshift=-0.6cm] an occurrence of $\bar{x}_i$ (4.1,-1.1);
A variable gadget.

[node,label=below:$c_j$] (c) at (0,0) ;

[node] (u1) at (-1,1) ;
[node] (u2) at (0,1) ;
[node] (u3) at (1,1) ;

[edge,tcol] (c) to (u1);
[edge,tcol] (c) to (u2);
[edge,tcol] (c) to (u3);

(tbuffer) at (0,2.315) ;
(bbuffer) at (0,-1.315) ;
A clause gadget.

An illustration of the gadgets used in the proof of <Ref>.

First assume that a 3-consistent $T_Y$ exists that realises $f$.
The cycle component $C_Y$ contains a path $P$ from $s_1$ to $t_n$ in the graph $Y-E(T_Y)$.
Since $T_Y$ contains all forced tree-edges, $P$ either uses the upper or lower path in each variable gadget.
If it uses the lower path in the gadget for $x_i$, then we set $x_i$ to  and otherwise we set it to .
Suppose this assignment would not satisfy $F$.
This yields a clause $C_j$ for which all three of its literals are not satisfied, meaning that we use the upper path for the positive literals and the lower path for the negated ones.
Consequently, the vertex $c_j$ and its neighbours in the variable gadgets form a component of $T_Y$ without an outer vertex, contradicting the fact that $T_Y$ is 3-consistent.

Conversely, assume that we are given a satisfying assignment for $F$.
Let $T_Y$ be the forest containing the following edges:
$T_Y$ contains all forced tree-edges.
Additionally, if $x_i$ is set to , $T_Y$ uses the upper path and otherwise it uses the lower one.
Here uses a path means that $T_Y$ contains the path's edges incident to $s_i$ and $t_i$ and in each block it contains the first and third edge.

This forest has a component for each clause gadget $C_j$ which contains the third vertices of the blocks corresponding to its literals.
Disregarding the components consisting of a single outer vertex, there is one other component containing the path of forced tree-edges and the first (and second) vertex of all blocks.
The cycle component $C_Y$ consists of a path which links the outer vertices at $s_1$ and $t_n$ and all other components are single edges, placing them in $M_Y$.
As a result, $T_Y$ realises $f$ and we can make it 3-consistent by choosing a satisfied literal in every clause $C_j$ and connecting the component of $C_j$ to the one containing the path by adding the edge from the second to the third vertex in the corresponding block to $T_Y$.

Using the same notation as in the result, we note that the reduction presented in <Ref> can also be used to prove <Ref>.
To get this result, one simply needs to define a graph $X$ and a 3-consistent forest $T_X$ that also realises $f$ and in which the only two outer vertices with an incident edge in $T_X$ are in the same component of $T_X$.

§ APPLICATIONS AND MINIMUM COUNTEREXAMPLES

In this section, we prove properties of minimum counterexamples to the 3-decomposition conjecture (under the assumption that such a counterexample exists).
To do so we exploit our new reducible configurations.

We prove that all 3-connected cubic graphs of tree-width at most 3 or of path-width at most 4 have a 3-decomposition.
Therefore minimum 3-connected counterexamples have tree-width at least 4 and path-width at least 5.
Both proofs make use of the reducible configurations we determined in <Ref> by showing that the restriction of the tree- or path-width causes one of them to appear.

Every cubic graph of tree-width at most 3 contains at least one isomorphic copy of the following graphs as a subgraph: the triangle, the $K_{2,3}$, and the domino.

First note that cubic graphs have tree-width at least 3: smaller tree-width necessitates a vertex of degree at most 2.
Let $G$ be a cubic graph of tree-width 3.
Consider a smooth tree-decomposition $(T, \mathcal{V})$ of $G$ of width 3, that is, all bags contain exactly four vertices of $G$ and adjacent bags have three vertices in common.
(See [7] for a proof that smooth tree-decompositions exist.)
We may assume, by <Ref>, that $G$ has more than six vertices and, therefore, $T$ has more than three.

Let $r$ be a vertex of $T$ and consider $T$ as an $r$-rooted tree.
Moreover, let $\ell$ be a leaf of $T$ of maximum distance to $r$ and $V_\ell=\{u,x_1,x_2,x_3\}$.
By assumption, $\ell$ has a parent $f$ with $V_f=\{v,x_1,x_2,x_3\}$.
We conclude that $N_G(u) = \{x_1,x_2,x_3\}$.

If $\ell$ does not have a sibling, then regard its parent $g$.
If $V_g = \{w,x_1,x_2,x_3\}$, then $N_G(v) = N_G(u)$ and $G$ contains a $K_{2,3}$ consisting of $u$, $v$, and their neighbours.
Otherwise, without loss of generality, $V_g=\{v, w, x_2, x_3\}$ and $N_G(x_1)$ contains at least one vertex in $\{x_2, x_3\}$, yielding a triangle consisting of $u$, $x_1$, and this vertex.

Consequently, we may assume that $\ell$ has sibling $\ell'$.
If $V_{\ell'} = \{w,x_1,x_2,x_3\}$, we obtains a $K_{2,3}$ again.
We may thus assume that the bags of all children of $f$ differ from $V_f$ in distinct vertices.
In particular, we have $V_{\ell'} = \{v,w,x_2,x_3\}$.

If $\ell$ has a further sibling $\ell''$ with $V_{\ell''} = \{v, y, x_1, x_3\}$, then we obtain a domino in $G[\{u, v, w, y, x_2, x_3\}]$.
Otherwise, $f$ has a parent $g$ and $V_g$ differs from $V_f$ in exactly one vertex.
If this is the vertex $x_1$, then $x_1$ has a neighbour in $\{x_2, x_3\}$, yielding a triangle together with $u$ and $x_1$.
Similarly, we obtain a triangle when $v$ is not in $V_g$.
Should $x_2$ be the vertex not in $V_g$, then $x_2$ has a neighbour in $\{x_1, x_3, v\}$ and each choice yields a triangle together with $x_2$ and one of $u$ or $w$.

The result for path-width is conceptually similar and the proof technique is abstracted and turned into an algorithm in [4], which checks for unavoidable structures in graphs of bounded path-width.
Nevertheless, we give a proof here to keep the paper self-contained.

Every cubic graph of path-width at most 4 contains at least one isomorphic copy of the following graphs as a subgraph: the triangle, the $K_{2,3}$, the domino, the twin-house, or the claw-square.

A graph of path-width at most 3 it is also of tree-width at most 3 and, hence, the lemma follows from <Ref>.

Consequently, we assume $G$ has path-width 4 and consider a smooth path-decomposition $(123\dots n', \mathcal{V})$ of $G$, that is, all bags contain exactly five vertices of $G$ and $|V_i \cap V_{i+1}| = 4$ for all $i \in \{1, \dots, n'-1\}$.
(Again, see [7] for a proof that smooth path-decompositions exist.)
Observe that for each $i \in \{1, \dots, n'-1\}$ there exists unique vertices $v_i \in V_{i+1}\setminus V_{i}$ and $w_i \in V_i\setminus V_{i+1}$.
In this proof, we make strong use of the following property, which is a direct consequence of the definition of path-decompositions:

\begin{equation}\label{eq: neighbours of leaving vertices}
\bigcup_{i=1}^j N_G(w_i) \subseteq \bigcup_{i=1}^j V_i~\text{for all}~j \in \{1, \dots, n'-1\}.
\end{equation}

Since the proof involves quite a few case distinctions, we refer to <Ref> for an orientation of which edges are present in each case.
Moreover, we use a lot of symmetry arguments and omit stating that these are without loss of generality every time.

Let $V_1=\{v_1,u_1,u_2,u_3,u_4\}$ and $w_1=v_1$.
(This is a typical example of the symmetries we use: we can always rename the vertices such that this is true.)
By (<ref>), $N(v_1)\subseteq\{u_1,u_2,u_3,u_4\}$, say $N(v_1) = \{u_1,u_2,u_3\}$.
We get two cases for $w_2$, namely $w_2=v_2$ or $w_2=u_1$.

In the first case, $N(v_2) \neq N(v_1)$ gives us a $K_{2,3}$.
Thus, $N(v_2) = \{u_2,u_3,u_4\}$.
This time, we have three options for $w_3$: $u_1$, $u_2$, or $v_3$.
The first and last case yield a desired subgraph:
If $w_3=u_1$, then $N(u_1)$ contains a vertex in $\{u_2, u_3, u_4\}$.
The first two options give us a triangle, the last a twin-house.
For $w_3=v_3$ we get a $K_{2,3}$ or $N(v_3) = \{u_1,u_2,u_4\}$ and a domino is present.

This puts us in the case that $w_3 = u_2$, which gets a new neighbour in $\{v_3, u_1, u_3, u_4\}$.
All but $v_1$ yield a triangle, so we are done or $u_1v_3\in E(G)$.
We now get four cases for $w_4$: $u_1$, $u_3$, $v_3$, or $v_4$.
If $w_4=u_1$, $u_1$ has a neighbour in $\{v_3, u_3, u_4\}$, yielding a domino, a triangle, or a twin-house.
If $w_4=v_3$, $v_3$ has a neighbour in $\{u_1, u_3, u_4\}$, yielding a domino, a twin-house, or a domino.
If $w_4=v_4$, $v_4$ has three neighbours in $\{u_1, u_3, u_4, v_3\}$.
From $u_3\in N(v_4)$ we get a domino if the edge $v_4u_1$ or $v_4u_4$ is present, one of which must be.
Otherwise, $N(v_4)= \{u_1, u_4, v_3\}$ and the graph contains a claw-square.

The last option is $w_4 = u_3$, in which we have $u_3v_4\in E(G)$ since $u_3u_4$ and $u_3u_1$ result in triangles and $u_3v_3$ yields a $K_{2,3}$.
By regarding $w_5$, for which only two options $w_5=v_3$ or $w_5=v_5$ remain, we complete the branch of the proof.
We get that $v_3v_4$, $v_3u_1$, and $v_3u_4$ give us a twin-house, and two dominoes, finishing the case $w_5=v_3$.
For $w_5=v_5$, choosing any three of the possible neighbours (all choices are symmetric) creates a claw-square.

Now we go back to our first split and deal with the case that $w_2=u_1$.
We get a triangle or $N(u_1)=\{v_1, v_2, u_4\}$.
This gives two choices for $w_3$ here, namely $v_3$ or $v_2$.
The first case gives $N(v_3) = \{u_2, u_3, u_4\}$ and a twin-house is present.
If $w_3 = v_2$, then we need two neighbours in $\{u_2, u_3, u_4, v_3\}$.
We can exclude $u_4$ as if forms a triangle, and both $u_2$ and $u_3$ yields a $K_{2,3}$.
Thus $N(v_2) = \{u_2, v_3\}$ and the obtained case is actually one we have already seen before, see <Ref>.

[->] (V1) to node[midway, above] $-v_1$ (V2);
[->] (V2) to node[midway, above] $-v_2$ (V3a);
[->] (V2) to node[midway, above left] $-u_1$ (V3b);
[->] ($(V3a.south east)+(0.2,0.15)$) to node[midway, above=2mm] $-v_3$ (V4aa.north west);
[->] ($(V3a.south east)-(0.2,0.1)$)to node[midway, above right=-2mm] $-u_1$ (V4ab.north west);
[->] (V3a) to node[midway, above] $-u_2$ (V4ac);
[->] (V3b) to node[midway, above] $-v_2$ (V4ba);
[->] (V3b) to node[midway, above] $-v_3$ (V4bb);
[->] (V4ba) to node[midway, right] $\cong$ (V4ac);
[->] (V4ac.south east) to node[midway, above=1mm] $-u_3$ (V5);
[->] (V4ac) to node[midway, above] $-v_4$ (V5b);
[->] (V4ac) to node[midway, above] $-v_3$ (V5c);
[->] (V4ac) to node[midway, above=1mm] $-u_1$ (V5d);
[->] (V5) to node[midway, above] $-v_5$ (V6a);
[->] (V5) to node[midway, above] $-v_3$ (V6b);

[] at (2,3.5) $+v_2$;
[] at (6,3.5) $+v_3$;
[] at (10,3.5) $+v_4$;
[] at (14,3.5) $+v_5$;
[] at (18,3.5) $+v_6$;

[circle,draw,fill=black,scale=0.5,label=above:$v_1$] (v2v) at (-0.5,-1.25) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_1$] (v2u1) at (-0.75,-2) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_2$] (v2u2) at (-0.25,-2) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_3$] (v2u3) at (0.25,-2) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_4$] (v2u4) at (0.75,-2) ;

[circle,draw,fill=black,scale=0.5,label=above:$v_1$] (v2v) at (3.5,-1.25) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_2$] (v2w) at (4.5,-1.25) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_1$] (v2u1) at (3.25,-2) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_2$] (v2u2) at (3.75,-2) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_3$] (v2u3) at (4.25,-2) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_4$] (v2u4) at (4.75,-2) ;
(v2v) to (v2u1);
(v2v) to (v2u2);
(v2v) to (v2u3);

[circle,draw,fill=black,scale=0.5,label=above:$v_1$] (v3av) at (7.5,-3.75) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_2$] (v3aw) at (8.5,-3.75) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_3$] (v3ax) at (8,-3.75) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_1$] (v3au1) at (7.25,-4.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_2$] (v3au2) at (7.75,-4.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_3$] (v3au3) at (8.25,-4.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_4$] (v3au4) at (8.75,-4.5) ;
(v3av) to (v3au1);
(v3av) to (v3au2) to (v3aw);
(v3av) to (v3au3) to (v3aw);
(v3aw) to (v3au4);

[circle,draw,fill=black,scale=0.5,label=above:$v_1$] (v3bv) at (7.5,1.25) ;
[circle,draw,fill=black,scale=0.5,label=above:$u_1$] (v3bu1) at (8,1.25) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_3$] (v3bx) at (8.5,1.25) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_2$] (v3bu2) at (7.25,0.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_3$] (v3bu3) at (7.75,0.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_4$] (v3bu4) at (8.25,0.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$v_2$] (v3bw) at (8.75,0.5) ;
(v3bv) to (v3bu1);
(v3bv) to (v3bu2);
(v3bv) to (v3bu3);
(v3bu1) to (v3bu4);
(v3bu1) to (v3bw);

[circle,draw,fill=black,scale=0.5,label=above:$v_1$] (v4acv) at (11.375,-3.75) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_2$] (v4acw) at (12.375,-3.75) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_3$] (v4acx) at (11.875,-3.75) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_4$] (v4acy) at (12.875,-3.75) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_1$] (v4acu1) at (11.125,-4.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_2$] (v4acu2) at (11.625,-4.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_3$] (v4acu3) at (12.125,-4.5) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_4$] (v4acu4) at (12.625,-4.5) ;
(v4acv) to (v4acu1);
(v4acv) to (v4acu2) to (v4acw);
(v4acv) to (v4acu3) to (v4acw);
(v4acw) to (v4acu4);
(v4acu2) to (v4acx);

[circle,draw,fill=black,scale=0.5,label=above:$v_1$] (v4bav) at (13.75,1.125) ;
[circle,draw,fill=black,scale=0.5,label=above:$u_1$] (v4bau1) at (14.25,1.125) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_3$] (v4bax) at (14.75,1.125) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_4$] (v4bay) at (15.25,1.125) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_2$] (v4bau2) at (13.5,0.375) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_3$] (v4bau3) at (14,0.375) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_4$] (v4bau4) at (14.5,0.375) ;
[circle,draw,fill=black,scale=0.5,label=below:$v_2$] (v4baw) at (15,0.375) ;
(v4bav) to (v4bau1);
(v4bav) to (v4bau2);
(v4bav) to (v4bau3);
(v4bau1) to (v4bau4);
(v4bau1) to (v4baw);
(v4bau2) .. controls (13.75,0.15) and (14.75,0.15) .. (v4baw) to (v4bax);

[circle,draw,fill=black,scale=0.5,label=above:$v_1$] (v5v) at (15.375,-7.25) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_2$] (v5w) at (16.375,-7.25) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_3$] (v5x) at (15.875,-7.25) ;
[circle,draw,fill=black,scale=0.5,label=above:$v_4$] (v5y) at (16.875,-7.25) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_1$] (v5u1) at (15.125,-8) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_2$] (v5u2) at (15.625,-8) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_3$] (v5u3) at (16.125,-8) ;
[circle,draw,fill=black,scale=0.5,label=below:$u_4$] (v5u4) at (16.625,-8) ;
[circle,draw,fill=black,scale=0.5,label=below:$v_5$] (v5z) at (17.125,-8) ;
(v5v) to (v5u1);
(v5v) to (v5u2) to (v5w);
(v5v) to (v5u3) to (v5w);
(v5w) to (v5u4);
(v5u2) to (v5x);
(v5u3) to (v5y);
A roadmap of the case distinctions made in the proof of <Ref>.

Using <Ref> and the reductions from <Ref> we can prove the following two theorems.

Suppose towards a contradiction that the class of all 3-connected cubic graphs of tree-width at most 3 (path-width at most 4) does not satisfy the 3-decomposition conjecture.
Let $H$ be a counterexample of minimum order amongst all graphs of this class.
By <Ref> (<Ref>) at least one of the graphs listed there is a subgraph of $H$.
Observe that all the corresponding reductions (as discussed in <Ref>) produce a minor of $H$ and, hence, are tree-width (and path-width) preserving.
Moreover, these transformations preserve 3-connectivity.
Altogether, $H$ can be reduced to a 3-connected graph $G$ of tree-width at most 3 (path-width at most 4) with $|V(G)| < |V(H)|$.
Since $H$ was a minimum counterexample, the graph $G$ satisfies the 3-decomposition conjecture and, because the transformations used are 3-compatible, so does $H$, yielding a contradiction.
(Note that for the domino, we only use the reduction to the edge if it preserves 3-connectivity and that we can extend a decomposition from the square to the domino in the case we do not reduce to the edge.)

Next, we prove the following properties of minimum counterexamples.

Suppose that there exists a 3-connected counterexample to the 3-decomposition conjecture.
Choose $G$ to be minimum amongst all such counterexamples.
By <Ref>, the six graphs listed in the claim are reducible and hence not subgraphs of $G$.
We refer to the property that the triangle is not a subgraph of $G$ by ($\Delta$) and use ($K_{2,3}$), (), (cs), (th), ($\boxminus$) for the respective properties corresponding to the other subgraphs.
Parts (<ref>) and (<ref>) follow immediately from ($\Delta$) and ($\boxminus$).
We prove (<ref>).
Let $wx$ be some edge of $G$.

Claim 1. If $wx$ is contained in some cycle of length 6, then (<ref>) is satisfied.

Proof. Let $C\coloneqq uvwxyzu$ be a cycle which contains $wx$.
By (<ref>) the cycle $C$ is induced and, hence, there exists a vertex $v' \in N_G(v) \setminus V(C)$.
Consider the path $P \coloneqq v'vwxyz$ as shown on the left of <Ref>.
If $P$ is induced, then the claim is satisfied.
Therefore, we may assume that $P$ has a chord.
Since $C$ is induced one end of this chord is $v'$ and by ($\Delta$) the other end is not $w$.
It remains to consider the cases that $v'x$, $v'y$, or $v'z$ is an edge of $G$.

[draw,line width=4pt,orange,opacity=0.75,join=round] (-1.5,0) to (-0.75,1) to (0,2) to (1,2) to (1.75,1) to (1,0);

[circle,draw,fill=black,scale=0.5,label=below:$u$] (u) at (0,0) ;
[circle,draw,fill=black,scale=0.5,label=below:$z$] (z) at (1,0) ;
[circle,draw,fill=black,scale=0.5,label=left:$v$] (v) at (-0.75,1) ;
[circle,draw,fill=black,scale=0.5,label=left:$v'$] (v2) at (-1.5,0) ;
[circle,draw,fill=black,scale=0.5,label=right:$y$] (y) at (1.75,1) ;
[circle,draw,fill=black,scale=0.5,label=above:$w$] (w) at (0,2) ;
[circle,draw,fill=black,scale=0.5,label=above:$x$] (x) at (1,2) ;
(u) to (v) to (w) to (x) to (y) to (z) to (u);
(v) to (v2);

(v2) to[bend right=50] (z);

[draw,line width=4pt,orange,opacity=0.75,join=round] (0,0) to (-0.75,1) to (0,2) to (1,2) to (1.75,1) to (2.5,0);

[circle,draw,fill=black,scale=0.5,label=below:$u$] (u) at (0,0) ;
[circle,draw,fill=black,scale=0.5,label=below:$z$] (z) at (1,0) ;
[circle,draw,fill=black,scale=0.5,label=left:$v$] (v) at (-0.75,1) ;
[circle,draw,fill=black,scale=0.5,label=left:$v'$] (v2) at (-1.5,0) ;
[circle,draw,fill=black,scale=0.5,label=right:$y$] (y) at (1.75,1) ;
[circle,draw,fill=black,scale=0.5,label=right:$y'$] (y2) at (2.5,0) ;
[circle,draw,fill=black,scale=0.5,label=above:$w$] (w) at (0,2) ;
[circle,draw,fill=black,scale=0.5,label=above:$x$] (x) at (1,2) ;
(u) to (v) to (w) to (x) to (y) to (z) to (u);
(v) to (v2);
(v2) to[bend right=50] (z);
(y) to (y2);
[draw,line width=4pt,orange,opacity=0.75,join=round] (-0.75,1) to (0,2) to (1,2) to (0.75,1.5) to (0.5,1);
[draw,line width=4pt,orange,opacity=0.5,join=round] (0,0) to (-0.75,1);
[draw,line width=4pt,orange,opacity=0.5,join=round] (-1.5,0) to (-0.75,1);

[circle,draw,fill=black,scale=0.5,label=below:$u$] (u) at (0,0) ;
[circle,draw,fill=black,scale=0.5,label=below:$z$] (z) at (1,0) ;
[circle,draw,fill=black,scale=0.5,label=left:$v$] (v) at (-0.75,1) ;
[circle,draw,fill=black,scale=0.5,label=left:$v'$] (v2) at (-1.5,0) ;
[circle,draw,fill=black,scale=0.5,label=right:$y$] (y) at (1.75,1) ;
[circle,draw,fill=black,scale=0.5,label=right:$y'$] (y2) at (2.5,0) ;
[circle,draw,fill=black,scale=0.5,label=above:$w$] (w) at (0,2) ;
[circle,draw,fill=black,scale=0.5,label=above:$x$] (x) at (1,2) ;
[circle,draw,fill=black,scale=0.5,label=left:$x'$] (x2) at (0.75,1.5) ;
[circle,draw,fill=black,scale=0.5,label=left:$x''$] (x3) at (0.5,1) ;
(u) to (v) to (w) to (x) to (y) to (z) to (u);
(v) to (v2) to[bend right=50] (z);
(y) to (y2) .. controls (2.25,2.5) and (1.25, 3.25).. (w);
(x) to (x2) to (x3);
Illustrations of some of the paths regarded in the proof of <Ref>.

Assume that $v'z \in E(G)$.
The vertex $y$ has a neighbour $y' \notin E(C) \cup E(P)$ by ($\Delta$).
Consider the path $uvwxyy'$ illustrated in the middle of <Ref>.
If this path is not induced, then $y'w \in E(G)$ by ($\Delta$) and ($\boxminus$).
We label this situation by ($\star$) so we can refer to it later.
From ($\Delta$) and ($\boxminus$) we obtain that $x$ has a neighbour $x' \notin V(C) \cup \{v',y'\}$.
We prove that both remaining neighbours of $x'$ are in $V(C) \cup \{v',y'\}$:
since $G$ is cubic, $x'$ is not adjacent to $v,w,y$, or $z$.
By ($K_{2,3}$) we obtain that $x'y'\notin E(G)$ and with (cs) we obtain $x'u, x'v' \notin E(G)$.
Hence, there exists $x'' \in N_G(x')\setminus (V(C) \cup \{v',y'\})$.
Consider the paths $uvwxx'x''$ and $v'vwxx'x''$ shown on the right of <Ref>.
At least one of the two paths is induced since the only possible chords are $ux''$ or $v'x''$, respectively.
However, if both chords exist, then ($K_{2,3}$) is violated.
Altogether, if $v'z \in E(G)$, then $G$ contains a path of the desired form.

Now assume that $v'x \in E(G)$.
There exists $y' \in N_G(y)\setminus (V(C)\cup\{v'\})$ since $C$ is chordless and ($\Delta$) holds.
Consider the path $uvwxyy'$.
We may assume that this path is not induced, that is, $y'u \in E(G)$ (the remaining potential chord $wy'$ violates ($\boxminus$)).
Observe that the vertices can be relabelled such that we are in the same situation as $(\star)$ and, hence, there exists an induced $P_6$.

Finally, let $v'y \in E(G)$.
Since $C$ is chordless and ($\Delta$) holds, we obtain that there exists $w' \in N_G(w)\setminus (V(C)\cup \{v'\})$.
The only possible neighbour of $w'$ in $V(C)\cup \{v'\}$ is $z$ by ($\Delta$), (th), and (cs).
Since $\deg_G(w') =3$ there exists $w'' \in N_G(w')\setminus (V(C)\cup \{v'\})$.
If $w''w'wxyv'$ is induced, then Claim 1 is true.
Therefore, assume there is a chord of $w''w'wxyv'$ in $G$.
By ($\Delta$) the only possible chords are $w''x$ and $w''v'$.
If $w''x \in E(G)$, then there exists $\tilde{w} \in N_G(w')\setminus (V(C) \cup \{w'', v'\})$ by ($\boxminus$) and (th), and, the path $\tilde{w}w'wxyv'$ is induced by (cs).
If otherwise $w''v' \in E(G)$, then the path $w''w'wxyz$ is induced by ($\Delta$), ($\boxminus$), (cs), and (). $\triangleleft$

Claim 2. If $wx$ is the middle edge of a $P_6$ and $wx$ is not contained in a cycle of length 6, then (<ref>) is satisfied.

Proof. Let $P\coloneqq uvwxyz$ be a $P_6$ contained as a subgraph $G$.
If $P$ is induced, then Claim 2 satisfied.
Therefore, we may assume that $P$ has a chord. Since $G$ is triangle-free and $wx$ is not contained in a $C_6$, the following chords are possible: $ux$, $vy$, $wz$, $uy$, and $vz$.
By symmetry, it suffices to consider the cases that $ux$, $vy$, or $vz$ is a chord of $P$.

First assume that $ux \in E(G)$.
By ($\Delta$) and (th), we obtain that $v$ has a neighbour $v' \notin V(P)$.
In the same way, we get that $y$ has a neighbour $y' \notin V(P) \cup \{v'\}$.
The path $v'vwxyy'$ is induced since a chord would either violate ($\Delta$) or ($\boxminus$) or lead to a $C_6$ containing $wx$.

Now assume that $vy \in E(G)$.
With ($\Delta$) and ($K_{2,3}$) we obtain that $w$ has a neighbour $w' \notin V(P)$ and $w'$ has a neighbour $w'' \notin V(P)$ by ($\Delta$), ($\boxminus$) and (th).
A chord of $w''w'wxyz$ does not exist due to the same three properties and the assumption that no $C_6$ contains $wx$.

Finally assume that $vz \in E(G)$.
There is a neighbour $y'$ of $y$ with $y' \notin V(P)$ by ($\Delta$) and (th).
The path $uvwxyy'$ is induced since a chord of this path would either violate ($\Delta$) or (th) or create a $C_6$ with $wx$ as an edge. $\triangleleft$

Claim 3. There exists a $P_6$ whose middle edge is $wx$.

Proof. By ($\Delta$), we obtain $N_G(w) \cap N_G(x) = \emptyset$.
Let $v \in N_G(w) \setminus \{x\}$.
There exists a neighbour $u$ of $v$ with $u \notin N_G(w) \cup N_G(x)$ due to ($\Delta$) and ($K_{2,3}$).
Let $y \in N_G(x)\setminus \{w\}$.
By ($\Delta$), ($K_{2,3}$), and (th), we obtain that $y$ has a neighbour $z \notin N_G(w) \cup N_G(x) \cup \{u\}$.
Altogether $uvwxyz$ is the desired $P_6$. $\triangleleft$

This completes the proof.

We close this section with a brief discussion of how we proved the theorem below.
The cubic graphs of order at most 20 are known, see [8, 21, 3].
We used the complete list of cubic graphs of order at most 20 as provided by [3].
For each graph in this list we computed a tree that leads to a 3-decomposition for this graph, i.e., removing the edges of this tree from its host graph results in the disjoint union of a 2-regular graph, a 1-regular graph, and some isolated vertices.
To obtain such a tree for a given cubic graph we by first employed a heuristic.
If the heuristic did not lead to a desired tree,
then our algorithm tackled the problem by an enumeration approach.
The code as well as the computed trees can be found in our GitLab repository<ref>.

§ FURTHER RESEARCH

The most pressing question is whether <Ref> can be exploited to prove the 3-decomposition conjecture in general.
A natural approach would be the following.
Suppose that there exists some counterexample to the 3-decomposition conjecture.
Reduce a quasi 3-decomposition (into a spanning tree, a 2-regular graph and a disjoint union of paths) to some smaller graph which satisfies the conjecture.
Manipulate the reduced graph with its decomposition such that it can be extended again to a 3-decomposition of the original graph. The challenge here is that it is not clear that such a quasi 3-decomposition admits the reductions of <Ref> in general.

A second obvious question is: can the 3-decomposition conjecture be proved for more graph classes by extending
the list of properties of a minimum counterexample?
For example, we believe that there should be a reduction-based proof for the known result that planar graphs have a 3-decomposition [17].

Finally, it would be desirable to extend the computational results of <Ref> to larger graphs.

[1]
Elham Aboomahigir, Milad Ahanjideh, and Saieed Akbari.
Decomposing claw-free subcubic graphs and $4$-chordal subcubic

[2]
F. Abdolhosseini, S. Akbari, H. Hashemi, and M.S. Moradian.
Hoffmann-Ostenhof's conjecture for traceable cubic graphs.
arXiv preprint arXiv:1607.04768, 2016.

[3]
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, and Hadrien Mélot.
House of graphs: A database of interesting graphs.
Discrete Applied Mathematics, 161(1):311 – 314, 2013.

[4]
Oliver Bachtler and Irene Heinrich.
Automated testing and interactive construction of unavoidable sets
for graph classes of small path-width.
arXiv preprint arXiv:2010.08373, 2020.

[5]
Fábio Botler, Andrea Jiménez, Maycon Sambinelli, and Yoshiko Wakabayashi.
The 2-Decomposition Conjecture for a new class of graphs.
Procedia Computer Science, 195:359–367, 2021.
Proceedings of the XI Latin and American Algorithms, Graphs and
Optimization Symposium.

[6]
Oliver Bachtler and Sven O. Krumke.
Towards obtaining a 3-decomposition from a perfect matching.
arXiv preprint arXiv:2008.09549, 2020.

[7]
Hans Leo Bodlaender.
A partial k-arboretum of graphs with bounded treewidth.
Theoretical computer science, 209(1-2):1–45, 1998.

[8]
Gunnar Brinkmann.
Fast generation of cubic graphs.
Journal of Graph Theory, 23(2):139–149, 1996.

[9]
Peter J. Cameron.
Research problems from the BCC22.
Discrete Mathematics, 311(13):1074–1083, 2011.
Selected Papers from the 22nd British Combinatorial Conference.

[10]
Guantao Chen and Songling Shan.
Homeomorphically irreducible spanning trees.
Journal of Combinatorial Theory, Series B, 103(4):409–414,

[11]
Reinhard Diestel.
Graph Theory, volume 173 of Graduate Texts in
Springer, Heidelberg; New York, fourth edition, 2010.

[12]
S. Even, A. Itai, and A. Shamir.
On the complexity of timetable and multicommodity flow problems.
SIAM J. Comput., 5:691–703, 1976.

[13]
Irene Heinrich.
On Graph Decomposition: Hajós' conjecture, the clustering
coefficient and dominating sets.
PhD thesis, Technische Universität Kaiserslautern, 2019.

[14]
Irene Heinrich.
On Graph Decomposition: Hajós' conjecture, the clustering
coefficient and dominating sets.
Dr. Hut, 2020.

[15]
Yanmei Hong, Qinghai Liu, and Nannan Yu.
Edge decomposition of connected claw-free cubic graphs.
Discret. Appl. Math., 284:246–250, 2020.

[16]
Arthur Hoffmann-Ostenhof.
Nowhere-zero flows and structures in cubic graphs.
PhD thesis, Universität Wien, 2011.

[17]
Arthur Hoffmann-Ostenhof, Tomáš Kaiser, and Kenta Ozeki.
Decomposing planar cubic graphs.
Journal of Graph Theory, 88(4):631–640, 2018.

[18]
Wenzhong Liu and Panpan Li.
Decompositions of cubic traceable graphs.
Discussiones Mathematicae Graph Theory, 40(1):35–49, 2020.

[19]
Kasper Szabo Lyngsie and Martin Merker.
Decomposing graphs into a spanning tree, an even graph, and a star
The Electronic Journal of Combinatorics, 26(1), 2019.

[20]
Karl Menger.
Zur allgemeinen kurventheorie.
Fundamenta Mathematicae, 10(1):96–115, 1927.

[21]
Markus Meringer.
Fast generation of regular graphs and construction of cages.
Journal of Graph Theory, 30(2):137–146, 1999.

[22]
Nicholas C. Wormald.
Classifying k-connected cubic graphs.
In Combinatorial Mathematics VI, pages 199–206. Springer,

[23]
Mengmeng Xie, Chuixiang Zhou, and Shun Zhou.
Decomposition of cubic graphs with a 2-factor consisting of three
Discrete Mathematics, 343(6):111839, 2020.

§ STRAIGHT-FORWARD EXTENSIONS

Here we go over the straight-forward local behaviours of the extensions to the $K_{2,3}$, the claw-square, the domino, the , and the twin-house that we omitted in <Ref>.
We specify these in the same way we did for the triangle in <Ref>, by determining the possible local behaviours at the smaller graph and showing how to extend them.
We also reduce the amount of local behaviours required for the square by employing switching arguments.

The $K_{2,3}$.
Recall the extension in <Ref>.
We determined the local behaviours of the single vertex in <Ref> and, because the $K_{2,3}$ is symmetric, we only need to check these three cases.
For each, <Ref> shows how to extend these to the $K_{2,3}$.

Extending a 3-decomposition to a $K_{2,3}$.

The .
For the extension from <Ref> we need the same three behaviours as before, since the  is also symmetric.
The second one is covered in <Ref>, and the remaining two are shown in <Ref>.

Extending a 3-decomposition to a .

The domino, part I.
Next we look at the extension in <Ref>.
For this, we first need to look at the possible behaviours of a 3-decomposition of $G$ at the edge $u_1u_2$ we are extending.
If the edge is in $C$, then one further edge at each end must also be in $C$ with the remaining two being part of $T$.
This yields, up to reflectional symmetry at the horizontal and vertical axis, the first two cases in <Ref>.
Note that both the edge and the domino have these two symmetries, such that it suffices to regard one of the symmetrical cases.

Behaviour of a 3-decomposition at an edge.

Next, assume that $u_1u_2$ is in $M$, then all remaining edges are in $T$, giving us the third case.
For all other cases, we have $u_1u_2\in T$ and we need to distinguish the behaviour of the remaining edges.
Should one of them be in $C$, say one at $u_1$, then both at this vertex are and at least one at $u_2$ is in $T$.
This gives us the fourth and fifth case.

We may now assume no edges are in $C$ and only need to consider the amount of $M$-edges left.
If there are none, all edges must be in $T$.
A single $M$-edge just yields one case up to symmetries and two give us two more.
More than two are not possible.

In total, there are nine types of behaviours to check, all of which give rise to a straight-forward extension to the domino, as shown in <Ref>.

Extending a 3-decomposition from the edge to the domino.

Local behaviours of the square.
All remaining extensions start from the square, which is why we first check which local behaviours 3-decompositions can exhibit.
Afterwards, we use switching arguments to eliminate behaviours that need not be considered.
Let $u_1u_2u_4u_3u_1$ be a square (as seen in <Ref>) in a graph $G$ with 3-decomposition $(T,C,M)$.
The possibilities obtained initially are shown in <Ref>, disregarding rotational symmetry.

Behaviours of a 3-decomposition at a square (without rotations).

We first distinguish cases based on the amount of edges of $C$ in the square.
If there are four such edges, then the remaining edges with an end in the square must be part of $T$.
It is not possible for exactly three edges to be in $C$ as this isolates an edge.
In the case of two edges, they form a path between two non-adjacent vertices and all other edges are in $T$, yielding just one case with four rotations.
For a single edge, we need its ends to be incident to another edge in $C$ that leaves the square and the missing edge is part of $T$.
The final edge of the square can then be in $M$, resulting in two more $T$-edges, or in $T$, resulting in at most one $M$-edge.
This gives the next four cases, each of which has four rotations.

This just leaves the case without any $C$-edges in the square.
We now differentiate by the amount of $M$-edges, where zero, three, and four are impossible.
Two $M$-edges must be opposite and all other edges are in $T$, resulting in one case with two rotations.
If there is just a single $M$-edge, it comes with five $T$-edges (three in the square and two more at its ends).
The remaining two can be any combination of $M$- and $T$-edges, yielding a total of four more cases with four rotations each.

The total amount of cases is now 39, so significantly more than we want to check for each extension, which is why we show how these can be reduced to the 18 shown in <Ref>.
This is done by locally changing the decomposition of the eliminated cases into one that is still present.

The local behaviours of the square that suffice to be checked.

The switches used to achieve this are shown in <Ref> and we describe each of them here in turn.
For the first one we note that the length-2 paths through the square can be used interchangeably, removing the two edges of the tree creates two isolated vertices that are reconnected by using those previously in a cycle, saving us two cases.

at (8.25,-4) or;

The transformations used to eliminate cases.

Next, regard the case with a single $C$-edge $u_1u_2$ where the edge at $u_3$ that is not in the square is in the matching.
By removing the $T$-edge $u_3u_4$ we get two components, one of which is the edge $u_1u_3$.
By moving the $M$-edge at $u_3$ to the tree, these components are unified, giving us a new tree.
The analogous transformation works if the $M$-edge is at $u_4$ and for all rotations, saving us eight cases in total.

This completes the reduction of cases with $C$-edges.
Let us now regard the case in which the square contains a single $M$-edge, say $u_2u_4$ and there is a second one at $u_3$.
Adding the edge $u_2u_4$ to the tree yields the square as the unique cycle and we can remove $u_1u_2$ to create a new spanning tree and 3-decomposition.
As this works for the four rotations, we save another four cases.
We can also remove three of the four rotations of the square with one $M$-edge and only $T$-edges elsewhere with the same argument.

Finally, the graph with $M$-edges $u_1u_2$ and $u_3v_3$ can be reduced to one of the two cases with two $M$-edges, reducing the total amount of cases by four yet again.
To see this, note that adding the $M$-edge at $u_3$ to the tree yields a cycle.
If it uses the edge $u_3u_4$, we put it into the matching instead and get a new 3-decomposition.
Otherwise, the edge $u_3u_1$ is used and the cycle consists of this edge and a path from $u_1$ to $u_3$ that does not meet the square.
But we have already seen that we may exchange the edges $u_1u_2$ and $u_2u_4$ and in the resulting graph the cycle obtained when adding the $M$-edge at $u_3$ to the tree remains unchanged.
This lets us swap it with $u_1u_3$ to obtain a new 3-decomposition.

We have now completed the switches.
Note that there are symmetric cases amongst the remaining 18, but the symmetries we may use also depend on which are present in the extension.
We cannot use rotational symmetry, for example, as neither the domino, the twin-house, nor the claw-square have this symmetry.

The domino, part II.
We can now complete the missing extension for the domino, seen on the right of <Ref>.
Of the behaviours from <Ref>, we can omit the following due to the domino's symmetries: 3, 6, 7, 10, 11, 16, and 17, where the number indicates their position.
We have covered behaviour 15 in <Ref>, leaving the ten shown in <Ref>.

Extending a 3-decomposition from the square to the domino.

The twin-house.
The next extension of the square that we regard is the one to the twin-house, seen in <Ref>.
Of the behaviours from <Ref>, we can omit the ones at position 7, 11, and 17, by symmetry.
We have covered behaviours 13 and 14 in <Ref>, leaving the 13 shown in <Ref>.

Extending a 3-decomposition to a twin-house.

The claw-square.
We finish by covering the last extension, the one from the square to the claw-square, seen in <Ref>.
Here we can eliminate the behaviours at position 6, 7, 10, 11, 13, 15 and 16 in <Ref> by symmetry.
We are left with the 11 behaviours shown in <Ref>.

Extending a 3-decomposition to the claw-square.