Decycling cubic graphsgrants
[grants]The first and the third author were supported by the grant no.
APVV-19-0308 of Slovak Research and Development Agency.  The first author
was partially supported by VEGA 2/0078/20. The second author was supported by the grant GAČR 19-17314J
of the Czech Science Foundation. The third author was partially supported by
VEGA 1/0727/22.

1,2]Roman Nedela
[1]Faculty of Applied Sciences, University of West Bohemia, Pilsen Czech republic
[2]Mathematical Institute of Slovak Academy of Sciences, Banská Bystrica, Slovakia

3]Michaela Seifrtová
[3]Faculty of Mathematics and Physics, Charles University, Prague, Czech republic

4]Martin Škovieracor1
[4]Faculty of Mathematics, Pysics, and Informatics, Comenius University, Bratislava, Slovakia
[cor1]Corresponding author

A set of vertices of a graph $G$ is said to be decycling if its
removal leaves an acyclic subgraph. The size of a smallest
decycling set is the decycling number of $G$. Generally, at
least $\lceil(n+2)/4\rceil$ vertices have to be removed in
order to decycle a cubic graph on $n$ vertices. In 1979, Payan
and Sakarovitch proved that the decycling number of a
cyclically $4$-edge-connected cubic graph of order $n$ equals
$\lceil (n+2)/4\rceil$. In addition, they characterised the
structure of minimum decycling sets and their complements. If
$n\equiv 2\pmod4$, then $G$ has a decycling set which is
independent and its complement induces a tree. If $n\equiv
0\pmod4$, then one of two possibilities occurs: either $G$ has
an independent decycling set whose complement induces a forest
of two trees, or the decycling set is near-independent (which
means that it induces a single edge) and its complement induces
a tree. In this paper we strengthen the result of Payan and
Sakarovitch by proving that the latter possibility (a
near-independent set and a tree) can always be guaranteed.
Moreover, we relax the assumption of cyclic
$4$-edge-connectivity to a significantly weaker condition
expressed through the canonical decomposition of 3-connected
cubic graphs into cyclically $4$-edge-connected ones. Our
methods substantially use a surprising and seemingly distant
relationship between the decycling number and the maximum genus
of a cubic graph.

cubic graph, decycling set, feedback vertex set, cyclic
connectivity, maximum genus

§ INTRODUCTION

Destroying all cycles of a graph by removing as few vertices as
possible is a natural and extensively studied problem in graph
theory and computer science, which can be traced back at least
as far as to Kirchhoff's work on spanning trees
[18]. The minimum number of vertices whose deletion
eliminates all cycles of a graph $G$ is its decycling
number, denoted by $\phi(G)$, and the corresponding set is a
minimum decycling set. (Here we follow the terminology
of [1, 2]. In the literature, decycling
number is also known as feedback vertex number and the
corresponding set of vertices is a feedback vertex
set, see [36] for instance.)

In contrast to a similar problem of eliminating cycles by
removing edges, which amounts to determining the cycle rank (or
the Betti number) $\beta(G)$ of a graph $G$, computing the
decycling number is long known to be a difficult problem. In
1972, it was proven by Karp <cit.> that
finding a minimum decycling set, or in other words,
establishing the decycling number, is an NP-complete problem.
The problem remains NP-complete even when restricted to planar
graphs, bipartite graphs, or perfect graphs
[5, 6]. On the other hand,
it becomes polynomial for a number of families, including
permutation graphs (Liang [22]), interval graphs,
cocomparability graphs,

and also for cubic graphs (Li and Liu [21], Ueno et
al. [38]).

Evaluating the decycling number of a cubic graph is, in a
sense, well understood. It is not difficult to see that
$\phi(G)\ge\lceil(n+2)/4\rceil$ for every cubic graph $G$ of
order $n$. In 1988, Speckenmayer [36] derived the
equation $\phi(G)=n/2-z(G)+1$, where the parameter $z(G)$
stands for the size of a maximum nonseparating independent set.
Surprisingly, the parameter $z(G)$ has an interpretation in
topological graph theory: it coincides with the maximum
orientable genus $\gamma_M(G)$ of $G$. The connection between
the decycling number and the maximum genus of a cubic graph was
revealed in 1997 by Huang and Liu [11] through the
formula $\phi(G)+\gamma_M(G)=n/2+1$ and was further developed
by Li and Liu [21]. Their results have a number of
important consequences. In particular, they imply that the
decycling number of a connected cubic graph reaches its natural
lower bound $\lceil(n+2)/4\rceil$ precisely when $G$ is
upper-embeddable, that is, when $G$ has a $2$-cell
embedding into an orientable surface with at most two faces.
The following result follows from results of Huang and Liu
[11] and Long and Ren [23]. An
independent proof can be found in Section 3
(Theorem <ref>).

(Huang and Liu [11], Long and Ren [23])
If $G$ is a connected cubic graph of order $n$, then
$\phi(G)\geq \lceil (n+2)/4\rceil$, and the equality holds if
and only if $G$ is upper-embeddable.

In 1975, Payan and Sakarovitch [32] proved that the
equality $\phi(G)=\lceil (n+2)/4\rceil$ holds for all
cyclically $4$-edge-connected graphs. In addition, they
determined the structure of the corresponding decycling sets.
They showed that every minimum decycling set $J$ of such a
graph is either independent or near-independent
(meaning that it induces a subgraph with exactly one
edge), and its complement $A=V(G)-J$ induces a forest with at
most two components. Following the terminology established by
Payan and Sakarovitch we say that the partition $\{A,J\}$ of
$V(G)$ is a stable decycling partition of $G$. If,
moreover, $A$ induces a tree, we say that $\{A,J\}$ is
coherent, otherwise it is incoherent.

Figure <ref> shows three simple examples of stable
decycling partitions. The vertices are coloured black or white,
with black vertices representing $A$ and white vertices
representing the minimum decycling set $J$; the edges within
$A$ are solid, those within $J$ are dashed, and the edges
between the sets are dotted. Out of the two
partitions of the cube, one is coherent but the other is not.

Examples of stable decycling partitions.

The theorem of Payan and Sakarovitch can be formulated as

(Payan and Sakarovitch [32])
Every cyclically $4$-edge-connected cubic graph has a stable
decycling partition. More precisely, if $G$ has $n$ vertices,
then the following hold:

(i) If $n\equiv2\pmod4$, then $G$ has a
partition $\{A,J\}$ where $A$ induces a tree and $J$ is

(ii) If $n\equiv0\pmod4$, then $G$ has a
partition $\{A,J\}$ where either

1. $A$ induces a tree and $J$ is
near-independent, or

2. $A$ induces a forest of two trees and
$J$ is independent.

It is not difficult to realise that stable decycling partitions
exist even beyond  the class of cyclically $4$-edge-connected
cubic graphs. It is therefore natural to ask which cubic graphs
admit a stable decycling partition. We answer this question in
Theorems <ref> and <ref> stated in
Section <ref> which, put together, yield the
following statement.

A connected cubic graph admits a stable decycling partition if
and only if it is upper-embeddable.

In this context it is important to note that the concepts of
maximum orientable genus and upper-embeddability of graphs have
been extensively studied and are fairly well understood. There
exist results (for example in [13, 17, 27, 41]) which provide min-max characterisations of maximum
genus in purely combinatorial terms, and there is a
polynomial-time algorithm to determine the maximum genus of an
arbitrary connected graph [4, 10]. As a consequence, the
Payan-Sakarovitch theorem readily follows from
Theorem <ref> (more precisely from the more detailed
Theorems <ref> and <ref>) and the long
known fact that all cyclically $4$-edge-connected graphs are
upper-embeddable [33, 16, 26].

Stable decycling partitions provide a useful insight into the
structure of cubic graphs, which is the reason why they
naturally emerge in several different contexts beyond decycling
of cubic graphs or embedding cubic graphs into orientable
surfaces with high genus. For example, Glover and Marušič
[9] used Theorem <ref> to construct
Hamilton cycles or Hamilton paths in cubic Cayley graphs for a
rich family of quotients of the modular group
$\PSL(2,\mathbb{Z})$. Their technique was subsequently used in
a few other papers dealing with the hamiltonicity of cubic
Cayley graphs [8, 7, 20]. Stable
decycling partitions of cubic graphs play an essential role
also in a recent computer-assisted proof of the Barnette-Goodey
conjecture due to Kardoš [14], which
states that simple planar cubic graphs with faces of size at
most 6 are hamiltonian.

Proofs of these results share the following idea of
topological nature. First, a cubic graph $G$ in question is
cellularly embedded into a closed surface. Next, a suitable
tree $T$ in the dual graph $G^*$ is identified. Under certain
conditions, the vertex set of $T$ extends to a stable decycling
partition of a cubic subgraph $H\subseteq G^*$. If this
partition is coherent, then, depending on the parity of the
Betti number of $H$, it is used to construct either a Hamilton
cycle or a Hamilton path of $G$, which traverse the boundary of
the union of faces of $G$ corresponding to the vertices of
$T\subseteq G^*$ (with possible exception of one edge).

Unfortunately, this idea does not work well if the decycling
partition is not coherent. From this point of view, coherent
decycling partitions are more valuable than incoherent ones.
Recall that for cyclically $4$-edge-connected cubic graphs
the theorem of Payan and Sakarovitch guarantees the
existence of a coherent decycling partition only when
$n\equiv2\pmod4$ (that is, when $\beta(G)$ is even). If
$n\equiv0\pmod4$, two possibilities can occur, only one of
which is a coherent decycling partition (namely the one in
Item (ii)-1 of Theorem <ref>). In this situation one has
to ask under what conditions it is possible to ensure that a
cubic graph admits a coherent decycling partition if its Betti
number is odd (that is, if $n\equiv0\pmod4$). Nedela and
Škoviera [29] answered this question in the
positive provided that $G$ is cyclically $5$-edge-connected.
The main result of this paper replaces the assumption of cyclic
$5$-connectivity with cyclic $4$-connectivity, and thus
improves Theorem <ref> by eliminating the possibility of
an incoherent decycling decomposition stated in Item (ii)-2.

Every cyclically $4$-edge-connected cubic graph $G$ admits a
coherent decycling partition. More precisely, the vertex set of
$G$ has a partition $\{A,J\}$ such that $A$ induces a tree and
$J$ is independent or near-independent, $J$ being independent
if and only if the order of $G$ equals $2\pmod4$.

What happens when the graph in question is not cyclically
$4$-edge-connected? First of all, there are many cubic graphs
with cyclic connectivity $3$ (including those with an odd Betti
number) that do admit a coherent decycling partition. In order
to get a deeper insight into the situation in $3$-connected
cubic graphs it is helpful to use the fact that every such
graph $G$ has a “canonical” decomposition $\{G_1, G_2,\ldots,
G_r\}$ into cyclically $4$-edge-connected cubic graphs. In
Section <ref> we prove that if at most one $G_i$ has
an odd Betti number, then $G$ admits a coherent decycling
partition (Theorem <ref>). The family of
3-connected cubic graphs having at most one factor with an odd
Betti number includes the so-called odd-cyclically
$4$-connected graphs. Their characteristic property is that
every edge cut whose removal leaves a component with an odd
Betti number has size at least $4$. It may be interesting to
mention that the concept of odd cyclic $4$-connectivity comes
from the study of maximum orientable genus where it was
independently introduced by Khomenko and Glukhov [16] and
Nebeský [26] in 1980 and 1983, respectively.

Nevertheless, there exist plenty of cubic graphs that do not
admit a coherent decycling partition. Theorem <ref>
tells us that a necessary condition for a connected cubic graph
to admit a coherent decycling partition is to be
upper-embeddable. This condition is, however, not sufficient.
Examples of upper-embeddable cubic graphs of connectivity $1$
with no coherent decycling partition are not difficult to find:
the example in Figure <ref> can easily be turned
into an infinite family. Two-connected examples are less
apparent. Figure <ref> displays two graphs
which are upper-embeddable, but none of them admits a coherent
decycling partition. An obvious generalisation of these two
graphs to an infinite family does not work because it produces
non-upper-embeddable graphs. In spite of that, an infinite
family does exist and is described in Section <ref>.

An upper-embeddable graph with no coherent partition.
Dashed lines represent the cotree edges of a Xuong tree
(see Section <ref> for the definition).

The situation in $3$-connected cubic graphs remains open: we
have no example of a $3$-connected upper-embeddable cubic graph
which would not have a coherent decycling partition. Motivated
by the difficulty of finding examples of $2$-connected
upper-embeddable cubic graphs with no coherent decycling
partition we propose the following conjecture.

Two-connected upper-embeddable graphs $F_1$ (left) and $F_2$ (right) with no coherent
decycling partition. Dashed lines represent the cotree edges of a Xuong tree.

A $3$-connected cubic graph admits a coherent decycling
partition if and only if it is upper-embeddable.

There is yet another important aspect of decycling cubic
graphs. It concerns random graphs. As is well known [35],
a random cubic graph is hamiltonian (and therefore
$2$-connected). Bau et al. [1] used this fact to
prove that a random cubic graph of order $n$ has decycling
number equal to $\lceil (n+2)/4\rceil$ almost surely. When
combined with Theorem <ref>, this result states
that almost all cubic graphs are upper-embeddable. By contrast,
there is a positive probability that a random cubic graph
contains a triangle, which means that it cannot be cyclically
$4$-edge-connected (see Theorem 9.5 in [12]). Since all
upper-embeddable cubic graphs admit a stable decycling
partition, the following question suggests itself.

Is it true that almost all cubic graphs admit a coherent
decycling partition? Equivalently, is it true that almost all
cubic graphs contain an induced tree such that the removal of
its vertices leaves a subgraph with at most one edge?

Our paper is organised as follows. In the next section we
collect the basic definitions required for understanding this
paper. In Section <ref> we reexamine the
relationship between minimum decycling partitions and maximum
orientable genus in cubic graphs. We prove
Theorem <ref> about stable decycling partitions and
derive the result of Payan and Sakarovitch
(Theorem <ref>) as a consequence. In
Section <ref> we focus on coherent decycling
partitions. We introduce the concept of ample upper
embeddability and prove that a cubic graph with an odd Betti
number admits a coherent decycling partition if and only if it
is amply upper-embeddable (Theorem <ref>). In
Sections <ref> and <ref> we prove our main
results about coherent decycling partitions in cyclically
$4$-edge connected and certain cyclically $3$-edge-connected
cubic graphs. In Section <ref> we present an infinite
family of $2$-connected cubic graphs in which every stable
decycling partition is incoherent. The paper closes with a few
remarks and problems.

§ PRELIMINARIES

Graphs in this paper will be mostly cubic
($3$-valent) or their subgraphs (subcubic). Loops and multiple
edges are permitted. Note that a $3$-connected cubic graph is
simple, which means that it has neither parallel edges nor
loops. We use the standard notation $V=V(G)$ for the vertex set
and $E=E(G)$ for the edge set of $G$. The symbol $n$ is
reserved for the order of $G$, the number of vertices of

If a vertex $u$ of a cubic graph is incident with a loop, then
the other edge incident with $u$ is a bridge. In this paper,
both endvertices of the latter edge are regarded as
cutvertices, that is, including $u$. This useful convention
comes from topological graph theory where graphs are
defined as finite $1$-dimensional CW-complexes and graph
connectivity corresponds to the connectivity of the underlying
topological space.

For a connected graph $G$, let $\beta(G) = |E|-|V|+1$ denote
its Betti number, that is, the dimension of the cycle
space of $G$ (the cycle rank), or in other words, the
number of edges of a cotree. Recall that a cotree
of a spanning tree $T$ is the spanning subgraph $G-E(T)$ of
$G$. A graph whose Betti number is even is said to be
cyclically even, otherwise it is cyclically odd.
Observe that if $G$ is cubic, then $G$ is cyclically even
whenever $n\equiv2\pmod4$ and $G$ is cyclically odd whenever

For a subset $A\subseteq V$, let $G[A]$ denote the subgraph
of $G$ induced  by $A$. If $A$ is a proper subset of vertices,
then $\delta_G(A)$ will denote the set of edges that join a
vertex in $A$ to a vertex in $V-A$. In other words,
$\delta_G(A)$ is the edge cut that separates $G[A]$
from $G[V-A]$. A $3$-edge-cut
$\delta_G(A)$ where $A$ or $V-A$ consists of a single vertex is
called trivial. If $H=G[A]$, we usually write
$\delta_G(H)$ instead of $\delta_G(A)$.

We say that a set $B\subseteq E(G)$ is cycle-separating
if $G-B$ is disconnected, and at least two of its components
contain cycles. Note that in a cubic graph $G$ a minimum cycle
separating subset of $E(G)$ is independent (that is a
matching), and that an independent edge cut is always cycle
separating. A connected graph $G$ is cyclically
$k$-edge-connected if no set of fewer than $k$ edges is
cycle-separating in $G$. It can be shown that deleting any set
of $k\geq \beta(G)$ edges yields either a disconnected graph or
a graph without cycles. Thus, if $G$ contains a
cycle-separating set of edges, then it contains one with no
more than  $\beta(G)-1$ elements. We therefore define the
cyclic connectivity of $G$, or more precisely,
cyclic edge connectivity, denoted by $\zeta(G)$, as the
largest integer $k\leq\beta(G)$ for which $G$ is cyclically
$k$-edge-connected. For instance, $K_{3,3}$ is cyclically
$k$-edge-connected for every positive integer $k$, but its
cyclic connectivity equals $4$. In fact, $\zeta(G)=\beta(G)$ if
and only if $G$ has no cycle-separating edge cut. If $G$ is
cubic, then it happens only for three graphs, namely for
$G\cong K_4$, $G\cong K_{3,3}$, and the dipole $D_2$ (the only
bridgeless cubic graph on two vertices).

Cyclic vertex connectivity can be defined in a similar manner;
for cubic graphs see [24, 28]. It can be
shown that in cubic graphs, for $k\le 3$, $k$-connectivity,
$k$-edge-connectivity, cyclic edge-connectivity, and
cyclic vertex-connectivity are all equal
<cit.>. In other words, for cubic
graphs cyclic connectivity is a natural extension of the
classical connectivity invariants.

§ DECYCLING PARTITIONS AND MAXIMUM GENUS IN CUBIC GRAPHS

The purpose of this section
is to discuss a link between the existence of a stable
decycling partition of a cubic graph and its maximum orientable
genus. Our main aim is to prove that a connected cubic graph
has a stable decycling partition if and only if it is
upper-embeddable, that is, if it has a cellular embedding on an
orientable surface which has at most two faces. The importance
of this relationship is underscored by the fact that the
required partitions can be efficiently constructed because the
maximum orientable genus of every graph is polynomially
computable [4, 10]. This fact provides an alternative
proof of the result, proved in [21], that the
decycling number of a cubic graph can be determined in
polynomial time.

We begin our exposition by reviewing basic facts about maximum
genus. For a deeper account we refer the reader to [25]
and [39] and for a fairly recent survey to

Throughout this paper, all embeddings will be cellular and
surfaces will be closed and orientable. Recall that a
cellular embedding of a connected graph $G$ on a
closed surface $S$ is, roughly speaking, a drawing of $G$ on
$S$ without edge-crossings such that each component of $S-G$, a
face, is homeomorphic to a disk (a $2$-cell). If a
graph with $n$ vertices and $m$ edges has a cellular embedding
on an orientable surface of genus $g$, then the number of
faces, denoted by $r$, must satisfy the Euler-Poincaré

The maximum genus of a connected graph $G$, denoted by
$\gamma_M(G)$, is the largest genus of an orientable surface
into which $G$ has a cellular embedding. It is an immediate
consequence of the Euler-Poincaré formula that
$\gamma_M(G)\le\lfloor\beta(G)/2\rfloor$, where $\beta(G)$ is
the Betti number of $G$. The quantity
$\xi(G)=\beta(G)-2\gamma_M(G)$ measures the distance of
$\gamma_M(G)$ from the natural upper bound of $\beta(G)/2$ and
is called the deficiency of $G$. It is easy to see that
$\xi(G)=r_\mathrm{min}(G)-1$ where $r_\mathrm{min}(G)$ is the
minimum number of faces among all cellular embedings of $G$.
The graphs for which $\gamma_M(G) = \lfloor\beta(G)/2\rfloor$
are called upper-embeddable. Clearly, a graph is
upper-embeddable if and only if $\xi(G)\le 1$, or equivalently,
if it has a cellular embedding into an orientable surface with
one or two faces. In this context it may be worth mentioning
that every connected graph admits a cellular embedding with a
single face into some closed surface, possibly non-orientable
[34, 37].

Upper-embeddable graphs thus fall into two types:
orientably one-face embeddable graphs (whose Betti
number is even) and orientably two-face embeddable
graphs (whose Betti number is odd); for brevity the adverb
“orientably” will be omitted. In cubic graphs these two types
of upper-embeddability can easily be distinguished by the
number of vertices. A one-face embeddable cubic graph has
order $2\pmod4$ whereas a two-face embeddable cubic graph
has order $0\pmod4$.

One of the most remarkable facts about maximum genus is that
this topological invariant can be characterised in a purely
combinatorial manner. As early as in 1973, Khomenko et al.
[17] proved that the maximum genus of an arbitrary
connected graph $G$ equals the maximum number of pairs of
adjacent edges whose removal leaves a connected spanning
subgraph of $G$. A similar characterisation was later
established by Xuong [41]. It states that $\xi(G)$
equals the minimum number of components with an odd number of
edges in a cotree of $G$. For brevity, such components will be
called odd. Analogously, those with an even number of
edges will be called even.

A spanning tree of $G$ whose cotree has exactly $\xi(G)$ odd
components is called a Xuong tree of $G$. By a result of
Kotzig <cit.>, every connected graph
with an even number of edges can be decomposed into pairs of
adjacent edges. Since a component with an odd number of edges
can be decomposed into pairs of adjacent edges and one
singleton, the cotree of a Xuong tree can be partitioned into
$\gamma_M(G)$ pairs of adjacent edges and $\xi(G)$ singletons.

For the sake of completeness we present a proof of Kotzig's

(Kotzig [19])
The edge set of every connected graph with an even number of
edges can be partitioned into pairs of adjacent edges.

Let $G$ be a connected graph with an even number of edges. It
suffices to prove that $G$ can be oriented in such a way that
each vertex has an even in-degree. Indeed, for each vertex of
$G$ we simply distribute the incoming edges into disjoint
pairs, thereby producing a partition of the entire
edge set into pairs of adjacent edges.

Let us start with an arbitrary orientation $D$ of $G$. If $D$
has the required property, we are done. Otherwise, there are at
least two vertices with an odd in-degree, since $|E(G)|$ is
even. At one of them, say $v$, pick an edge directed outward
and continue to produce a directed walk $W$ starting at $v$
which extends as long as possible. Clearly, $W$ terminates at
another vertex with an odd in-degree, say $w$. After reversing
the orientation of all edges on $W$ the in-degree of $v$ and
$w$ becomes even while the other vertices of $G$ keep the
parity of their in-degree. We continue this process until all
vertices of $G$ obtain an even in-degree.

We end this brief introduction to the theory of maximum genus
of a graph by stating two, in a sense complementary,
combinatorial characterisations of upper-embeddable graphs. The
first of them is due to Jungerman [13] and Xuong

(Jungerman [13], Xuong [41])
A connected graph is one-face embeddable if and only if it has
a spanning tree with no odd cotree components; it is two-face
embeddable if and only if it has a spanning tree whose cotree
has precisely one odd component.

The second characterisation of upper-embeddable graphs is due
to  Nebeský <cit.>. Let $G$ be a graph
and $X\subseteq E(G)$ an arbitrary set of edges. Let
$\text{ec}(G-X)$  and $\text{oc}(G-X)$ denote the number of
cyclically even and cyclically odd components of $G-X$,

(Nebeský [27])
A connected graph $G$ is upper-embeddable if and only if for an
arbitrary set $X\subseteq E(G)$ one has

\begin{equation}\label{eq:Nebesky}
\text{\rm ec}(G-X)+2\text{\rm oc}(G-X)-2\leq |X|.
\end{equation}

In the rest of this section we show that the two types of
upper-embeddability of cubic graphs lead to three different
types of decycling vertex partitions $\{A,J\}$, two of which
exist when the Betti number is odd, and one exists when the
Betti number is even. We will first treat the  case of even
Betti number, but before stating the result we present a lemma
which provides a convenient tool for dealing with cubic
upper-embeddable graphs in general.

Let $G$ be a connected cubic graph and $T$ a spanning tree of
$G$. Observe that each component of $G-E(T)$ is a path or a
cycle. A component of $G-E(T)$ will be called heavy if
the number of its edges is at least three and has the
same parity as the Betti number of $G$. A component which is
not heavy will be called light.

Let $G$ be a connected loopless cubic graph of order at
least $4$. If $G$ is upper-embeddable, then it has a Xuong tree
with acyclic cotree. If, in addition, $G$ has a Xuong tree with
a heavy cotree component, then it also has a Xuong tree with
acyclic cotree that contains a heavy component of the same

Take any Xuong tree $T$ of $G$. If $G-E(T)$ is acyclic, then
there is nothing to prove. If not, $G-E(T)$ has a component $Q$
which is a cycle.  Let $Q=(u_1u_2\ldots u_k)$, where $u_1, u_2,
\ldots, u_k$ are vertices of $G$ listed in cyclic ordering.
Since $G$ is loopless, we have $k\ge 2$. Each $u_i$ is adjacent
to some vertex $v_i$ such that the edge $u_iv_i$ belongs to
$T$. Note, however, that $v_i$ and $v_j$ need not be distinct
for $i\ne j$. Furthemore, the valency of each $v_i$ in $G-E(T)$
is at most $1$ for otherwise $u_iv_i$ would be the only edge of
$T$ and $G$ would have only two vertices. In particular, each
$v_i$ belongs to an acyclic component of $G-E(T)$. Set
$T'=T+u_1u_2-u_1v_1$; clearly, $T'$ is a spanning tree of $G$.
The cycle $Q$ in $G-E(T)$ now transforms into a
$u_2$-$v_1$-path $P$ in $G-E(T')$ of length $k$. If $Q$ is an
odd cycle, then $v_1$ must belong to an even component of
$G-E(T)$, because $T$ is a Xuong tree. Therefore $P$ becomes
part of an acyclic cotree component whose number of edges
is odd and at least $k$. If $Q$ is even, then $P$ becomes part
of an acyclic component of $G-E(T')$ which has the same parity
as the component of $G-E(T)$ containing $v_1$ and has at
least $k$ edges again. In other words, the transformation of
$T$ into $T'$ turns a heavy component of $G-E(T)$ into a heavy
acyclic component of $G-E(T')$. By repeating this process as
many times as necessary we arrive at a Xuong tree $T''$ of $G$
which has an acyclic cotree, and has a heavy cotree component
whenever the cotree of $T$ had.

The following two theorems are the main results of this

For a connected cubic graph $G$ the following statements are

(i)$G$ has a cellular embedding on an
orientable surface with one face.

(ii) The vertex set of $G$ can be partitioned
into two sets $A$ and $J$ such that $A$ induces a tree
and $J$ is independent.

(i) $\Rightarrow$ (ii): By the Jungerman-Xuong Theorem, $G$ has
a spanning tree $T$ with all cotree components even.
Lemma <ref> implies that $E(G)-E(T)$ has a partition
$\mathcal{P}$ into pairs of adjacent edges. For each pair
$\{e,f\}$ from $\mathcal{P}$ pick a vertex shared by $e$ and
$f$, and let $J$ be the set of all vertices obtained in this
way. Set $A=V(G)-J$. Since $G$ is cubic, each vertex of $J$
must be a pendant vertex of $T$. Observe that the vertices
chosen from distinct pairs of $\mathcal{P}$ must be
non-adjacent. So $J$ is an independent set of vertices and
$T-J$ is a tree with $V(T-J)=A$. Since every cotree edge with
respect to $T$ is incident with a vertex in $J$, the tree $T$
is an induced subgraph. In other words, $\{A,J\}$ is the
required vertex partition.

(ii) $\Rightarrow$ (i): Assume that the vertex set of $G$ has a
partition $\{A, J\}$ where $A$ induces a tree and $J$ is an
independent set. Let $S$ be the tree induced by $A$. For any
vertex $v\in J$ choose an arbitrary edge $e_v$ incident with
$v$ and form a spanning subgraph $S^+$ of $G$ by adding to $S$ all
the edges $e_v$ with $v\in J$. Since $J$ is independent, each
edge $e_v$ has its other end on $S$. Therefore $S^+$ is a
connected spanning subgraph of $G$. In fact, $S^+$ must be
acyclic, because each vertex $v\in J$ is joined to $S$ only by
the edge $e_v$. Thus $S^+$ is a spanning tree of $G$ in which
all vertices of $J$ are pendant. By the definition of $S^+$,
each cotree edge is incident with a single vertex of $J$, and
each vertex of $J$ is incident with precisely two cotree edges.
Hence the set of cotree edges can be partitioned into pairs of
adjacent edges and, consequently, each cotree component is even.
By Theorem <ref>, $G$ is one-face embeddable.

If a cubic graph $G$ has a vertex partition $\{A,J\}$ such that
$A$ induces a tree and $J$ is independent, then by
Theorem <ref> its Betti number must be even, and
hence its order is $2\pmod4$. The next theorem shows that if
the order of $G$ is $0\pmod4$, then there exists a similar
partition $\{A,J\}$ of the vertices of $G$, however, it is
either the independence of $J$ or the connectivity of the
subgraph induced by $A$ that fails.

Let $G$ be a connected cubic graph. The following statements
are equivalent.

(i) $G$ has a cellular embedding on an
orientable surface with two faces.

(ii) The vertex set of $G$ can be partitioned
into two sets $A$ and $J$ such that either

1. $A$ induces a tree and $J$ is
near-independent, or

2. $A$ induces a forest with two components
and $J$ is independent.

(i) $\Rightarrow$ (ii): First assume that $G$ contains a loop
incident with a vertex $v$, and let $u$ be the vertex adjacent
to $v$. Then $uv$ is a bridge and since deficiency is clearly
additive over bridges, $G-v$ is a one-face embeddable graph.
Let $G'$ be the cubic graph homeomorphic to $G-v$. By
Theorem <ref>, the vertex set of $G'$ has a vertex
partition $\{A,J\}$ where $A$ induces a tree and $J$ is
independent. Then $\{A\cup\{u\},J\cup\{v\}\}$ is a partition of
$V(G)$ such that $A$ induces a tree and $J$ is

Now let $G$ be loopless. Obviously, $G$ has at least four
vertices, so we can employ Lemma <ref> to conclude
that $G$ has a Xuong tree $T$ with acyclic cotree. Let $B$ be
the unique odd component of $E(G)-E(T)$. Choose a pendant
edge $g=w_1w_2$ of $B$, where $w_2$ denotes a pendant vertex of
$B$. By applying Lemma <ref> we decompose the set
$E(G)-(E(T)\cup\{g\})$ into pairs of adjacent edges. For each
pair $\{e,f\}$ from $\mathcal{P}$ we pick a vertex shared by
$e$ and $f$ and denote by $J'$ the resulting set of vertices.
Clearly, $J'$ is an independent set. For $i\in\{1,2\}$ set
$J_i=J'\cup\{w_i\}$ and $A_i=V(G)-J_i$. We show that both
$\{A_1,J_1\}$ and $\{A_2,J_2\}$ are vertex partitions
satisfying (ii) of the theorem.

First assume that $B$ is a heavy odd component of $E(G)-E(T)$,
and let $h=w_1w_3$ be the edge of $B$ incident with $w_1$ and
different from $g$. All the vertices of $J_1$ are now pendant
in $T$, so $T-J_1$ is a tree. Since every cotree edge is
incident with a vertex in $J_1$, the tree $T-J_1$ is induced
by $A_1$. Observe that $\{w_1,w_3\}\subseteq J_1$ while $w_2\in
A_1$. As $J'$ is independent, we conclude that $h=w_1w_3$ is
the only edge joining a pair of vertices of $J_1$. Thus  $J_1$ is
near-independent and the partition $\{A_1,J_1\}$ satisfies

If $B$ has only one edge, namely $g=w_1w_2$, then the vertices
of $J_1$ except $w_1$ are pendant in $T$, and $w_1$ is a
$2$-valent vertex of $T$. Hence $T-J_1$ is a forest with two
components. Further, each cotree edge with respect to $T$ joins
a vertex in $J_1$ to a vertex in $A_1$, which implies that
$J_1$ is independent.

We remark that the partition $\{A_2,J_2\}$ is always of type
(ii)-2, no matter whether the unique odd cotree component is
heavy or not. In any case, the partitions $\{A_1,J_1\}$ and
$\{A_2,J_2\}$ fulfil (ii) of the theorem.

(ii) $\Rightarrow$ (i): Assume that the vertex set of $G$ has a
partition $\{A,J\}$ satisfying the properties stated in (ii).
We distinguish two cases.

Case 1. $A$ induces a tree and $J$ is a
near-independent set. Let $h$ be the unique edge of the
subgraph $G[J]$, and let $S=G[A]$. Since $J$ is
near-independent, for each vertex $v$ of $J$ there exists at
least one edge joining $v$ to $S$. Choose one of them and
denote it by $t_v$. Form a spanning
subgraph $S^+$ of $G$ by adding to $S$ all the edges $t_v$
where $v\in J$. Clearly, $S^+$ is connected and acyclic, so
$S^+$ is a spanning tree of $G$ in which all the vertices of
$J$ are pendant.

If $h$ is not a loop, then $h=xy$ where $x$ and $y$ are
distinct vertices. It follows that each vertex $v$ of $J$ is
incident with two distinct cotree edges $e_v$ and $f_v$. If $v$
and $w$ are not adjacent in $G$, then the pairs
$\{e_v,f_v\}$ and $\{e_w,f_w\}$ are disjoint. However, for the
ends of $h$ we have $\{e_x,f_x\}\cap\{e_y,f_y\}=\{h\}$.
Assuming that $h=e_x=e_y$ we must conclude that $f_x\ne f_y$,
because otherwise $G[J]$ would contain both $h$ and $f_x=f_y$,
contrary to the assumption that $J$ is near-independent.
Therefore the pairs $\{e_v,f_v\}$, for $v\in J-\{x\}$, and the
singleton $\{f_x\}$ form a partition of $E(G)-E(S^+)$ which
shows that $S^+$ is a Xuong tree of $G$. In fact, the cotree
component containing $h$ is heavy.

If $h$ is a loop incident with a vertex $x$, then each vertex
$v$ of $J-\{x\}$ is incident with two distinct cotree edges
$e_v$ and $f_v$, and the pairs corresponding to distinct
vertices of $J-\{x\}$ are again disjoint. It follows that the
pairs $\{e_v,f_v\}$ for $v\in J-\{x\}$ and the singleton
$\{h\}$ form a partition of $E(G)-E(S^+)$ proving that $S^+$ is
a Xuong tree of $G$.

Case 2. $A$ induces a forest with two components and
$J$ is independent. Let $S_1$ and $S_2$ be the components of
the forest $G[A]$. Because $G$ is connected and $J$ is
independent, there must be a vertex $x\in J$ with a neighbour
$y_1$ in $S_1$ and a neighbour $y_2$ in $S_2$. For each vertex
$v\in J-\{x\}$ choose an arbitrary edge $t_v$ incident with
$v$, and form a spanning subgraph $T$ of $G$ extending $S_1\cup
S_2$ with the edges $xy_1$ and $xy_2$, and with all the edges
$t_v$ where $v\in J-\{x\}$. Clearly, $T$ is a spanning tree of
$G$. Observe that each vertex $v\in J-\{x\}$ is incident with
two cotree edges $e_v$ and $f_v$ while for $x$ there is a
single cotree edge $g$ incident with it. It follows that the
pairs $\{e_v,f_v\}$ for $v\in J-\{x\}$ together with the
singleton $\{g\}$ form a partition of $E(G)-E(T)$ proving that
$T$ is a Xuong tree of $G$.

For loopless cubic graphs, the proof of
Theorem <ref> shows that the equivalence (i)
$\Leftrightarrow$ (ii) stated in the theorem holds true even
when Item (ii)-1 is removed from the statement. This fact,
combined with the theorem of Payan and Sakarovitch
(Theorem <ref>), implies that for a cyclically
$4$-edge-connected cubic graph of order $n\equiv 0\pmod4$ one
can always guarantee the existence of a vertex partition
$\{A,J\}$ where $A$ induces a forest of two trees and $J$ is
independent. If we take into account Theorem <ref>,
we can conclude that in a cyclically $4$-edge-connected cubic
graph $G$ there always exists a minimum decycling set $J$ which
is independent. In Section <ref> we show that $J$ can
also be chosen in such a way that $G-J$ is a tree (see
Theorem <ref>). By Theorem <ref>,
both properties can be achieved at the same time only when

As an immediate corollary of the previous two theorems we
obtain the following statement which is identical with
Theorem <ref>.

A connected cubic graph admits a stable decycling partition if
and only if it is upper-embeddable.

The result of Payan and Sakarovitch [32] stated as
Theorem <ref> now follows from the well known fact
[33, 16, 26] that all cyclically $4$-edge-connected
graphs are upper-embeddable.

Every cyclically $4$-edge-connected cubic graph admits a stable
decycling partition.

We finish this section by providing a different proof of the
result of Long and Ren [23] stated as
Theorem <ref>.

If $G$ is a connected cubic graph of order $n$, then
$\phi(G)\geq \lceil (n+2)/4\rceil$, and the equality holds if
and only if $G$ is upper-embeddable.

Let $J$ be an arbitrary decycling set for $G$ and let
$A=V(G)-J$ be its complement. Denote by $e_A$ and $e_J$ the
numbers of edges of the induced subgraphs $G[A]$ and $G[J]$,
respectively. Since $G[A]$ is acyclic, we obtain

$$|\delta_G(A)|=3|A|-2e_A\geq 3(n-|J|)-2(n-|J|-1)=n-|J|+2.$$

On the other hand, $|\delta_G(A)|=|\delta_G(J)|=3|J|-2e_J$, so

\begin{equation}\label{eq:J}
3|J|\geq 3|J|-2e_J=|\delta_G(A)|\geq n-|J|+2,
\end{equation}

implying that $|J|\geq \lceil (n+2)/4\rceil$. Therefore $\phi(G)\geq \lceil(n+2)/4\rceil$.

We now prove that $\phi(G)=\lceil(n+2)/4\rceil$ if and only if $G$ is upper-embeddable. First assume that $\phi(G)=\lceil(n+2)/4\rceil$ and let $\{A,J\}$ be a decycling partition where the decycling set $J$ has $\lceil(n+2)/4\rceil$ vertices. If we insert $|J|=\lceil(n+2)/4\rceil$ into (<ref>),
we obtain $e_J=0$ if $n\equiv 2\pmod4$, and $e_J\leq 1$, if
$n\equiv 0\pmod4$. An easy counting argument now shows that
$G[A]$ has exactly one component either if  $n\equiv 2\pmod4$ or if
$e_J=1$ and $n\equiv 0\pmod4$. If $n\equiv 0\pmod4$ and $e_J=
0$, we derive that $G[A]$ has exactly two components. Hence, in
either case, the decycling partition $\{A,J\}$ is stable. By
Corollary <ref>, $G$ is upper-embeddable.

Conversely, if $G$ is upper-embeddable, then, by
Corollary <ref>, it admits a stable decycling
partition $\{A,J\}$. Direct counting yields that
$\phi(G)\le |J|=\lceil(n+2)/4\rceil$ for each of the three types of stable
partitions. As shown before, $\phi(G)\geq \lceil(n+2)/4\rceil$,  so
$\phi(G)=\lceil(n+2)/4\rceil$, and the proof is complete.

§ COHERENT DECYCLING PARTITIONS AND AMPLE UPPER-EMBEDDABILITY

Theorem <ref> tells us that a connected
cubic graph on $2\pmod4$ vertices has a coherent decycling
partition if and only if is one-face embeddable. By contrast,
two-face-embeddability is not sufficient for a cubic graph of
order $0\pmod4$ to have a coherent decycling partition, as
confirmed by the graphs in Figures <ref>
and <ref>. In this section we show that a cubic
graph of order $0\pmod4$ admits a coherent decycling partition
exactly when it possesses a stronger form of
upper-embeddability, one that allows removing a pair of
adjacent vertices without affecting upper-embeddability.

Let $G$ be an upper-embeddable cubic graph. A pair $\{x,y\}$ of
distinct vertices of $G$ will be called removable if $x$
and $y$ are simply adjacent (that is, not connected by parallel
edges), the edge $xy$ is not a bridge, and $G-\{x,y\}$
remains upper-embeddable; otherwise a pair of adjacent vertices
is said to be non-removable. It follows from the
definition that $G-\{x,y\}$ is connected. If $\{x,y\}$ is a
removable pair of vertices, then the graphs $G$ and $G-\{x,y\}$
have different Betti numbers. Therefore if a pair $\{x,y\}$
of vertices is removable, one of $G$ and $G-\{x,y\}$ is
one-face-embeddable and the other one is two-face-embeddable.

We say that a cubic graph $G$ is amply upper-embeddadble
if it is upper-embeddable and contains a removable pair of
adjacent vertices. An upper-embeddable cubic graph is
tightly upper-embeddable if it is not amply
upper-embeddable. In other words, in a tightly upper-embeddable
cubic graph the removal of every pair of simply adjacent
vertices produces either a disconnected graph or a graph with
deficiency at least $2$.

In this section we focus on amply upper-embeddable cubic graphs
with an odd Betti number, that is, with order $0\pmod 4$. For
obvious reasons we refer to them as amply two-face-embeddable cubic graphs. A two-face-embeddable cubic graph
that is not amply two-face-embeddable is tightly

Our main goal is to prove that a connected cubic graph of order
$0\pmod4$ admits a coherent decycling partition if and only if
it is amply two-face-embeddable, and to characterise such
graphs by providing a Jungerman-Xuong-type theorem for them.

We begin our study of amply upper-embeddable graphs with a
lemma showing that such graphs are loopless.

If an upper-embeddable cubic graph contains a loop, then it is
tightly two-face-embeddable.

Let $G$ be an upper-embeddable graph with a loop at a vertex
$u$ and let $v$ be the neighbour of $u$. Since the deficiency
is additive over bridges, the component $H$ of $G-uv$
containing $v$ is one-face embeddable, and hence the entire $G$
is two-face-embeddable. Suppose, to the contrary, that $G$
contains a removable pair of vertices, say $\{x,y\}$. Taking
into account that $uv$ is a bridge and $v$ is a cut-vertex of
$G$ we conclude that $\{x,y\}\cap\{u,v\}=\emptyset$. In
particular, both $x$ and $y$ are contained in $H$. We wish to
prove that $G-\{x,y\}$  has deficiency at least $2$. Since
$G-\{x,y\}$ is connected, so is $H-\{x,y\}$, given the position
of $x$ and $y$ within $G$. Recall that $\xi(H)=0$. It follows
that $H-\{x,y\}$ has an odd Betti number, and therefore
. Using the additivity of $\xi$ over
bridges again we eventually obtain that  ,
which contradicts the assumption that $\{x,y\}$ is removable.
Hence, $G$ is tightly upper-embeddable.

The next lemma explores the relation of ample
upper-embeddability to the existence of heavy components in the
cotree of a Xuong tree.

Let $G$ be an upper-embeddable cubic graph. If $G$ contains a
Xuong tree whose cotree has a heavy component, then $G$ is
amply upper-embeddable.

Let $T$ be a Xuong tree of $G$ with a heavy cotree component
$K$. By Lemma <ref> we may assume that $K$ is a
path. Since the length of $K$ is at least $3$, $K$ contains an
edge $e=uv$ adjacent to a pendant edge of $K$. Consider the
graph $G'=G-\{u,v\}$. The vertices $u$ and $v$ are pendant
vertices of $T$, so $T'=T-\{u,v\}$ is a spanning tree of $G'$;
in particular, $G'$ is connected. If $\beta(G)$ is even, then
$K-\{u,v\}$ has a single non-trivial odd component. Hence $G'$
is upper-embeddable and $G$ is amply upper-embeddable. If
$\beta(G)$ is odd, then $K$ has an odd number of edges,
and $K-\{u,v\}$ consists of even components. It follows that
all components of $G'-E(T')$ are even, so $G'$ is
upper-embeddable, and therefore $G$ is again amply

Now we are ready for a characterisation of amply
upper-embeddable graphs with an odd Betti number.

The following statements are equivalent for every connected
cubic graph $G$.

(i) $G$ is amply two-face embeddable.

(ii) $G$ has a Xuong tree with a single odd
cotree component, which is heavy.

(iii) $G$ admits a coherent
decycling bipartition.

(i) $\Rightarrow$ (ii): Let $G$ be an amply two-face-embeddable
graph, and let $u$ and $v$ be a removable pair of vertices of
$G$. By Lemma <ref>, none of $u$ and $v$ is
incident with a loop. Since $u$ and $v$ are not doubly
adjacent, $u$ has a neighbour different from $v$, and vice
versa. Let $u_1$ and $u_2$ be the other two neighbours of $u$
(possibly $u_1=u_2$) and let $v_1$ and $v_2$ be the other two
neighbours of $v$ (possibly $v_1=v_2$). Since $G$ has an odd
Betti number, the Betti number of $G'=G-\{u,v\}$ must be even,
and therefore $G'$ is one-face embeddable. By Xuong's Theorem,
$G'$ has a Xuong tree $T'$ with even cotree components. Extend
$T'$ by adding the edges $u_1u$ and $v_1v$ to $T'$. The
resulting subgraph $T$ is clearly a spanning tree of $G$. Note
that both $u_2$ and $v_2$ were contained in even components of
$G'-E(T')$. In $G-E(T)$ the vertices $u_2$ and $v_2$ lie in the
same component which includes the path $u_2uvv_2$. This
component is odd and heavy, while the remaining cotree
components remain even. Thus $T$ is the required spanning tree
of $G$.

(ii) $\Rightarrow$ (iii): Assume that $G$ has a Xuong tree $T$
with a single odd cotree component, which is heavy. Clearly,
$G$ must be loopless and of order at least $4$. By
Lemma <ref> we can assume that $E(G)-E(T)$ is
acyclic, so the only odd component $B$ of $G-E(T)$ is a path of
length at least three. We now construct a partition
$\mathcal{P}$ of $E(G)-E(T)$ into pairs of adjacent edges and
one singleton in such a way that the singleton is a pendant
edge of $B$. For each pair $\{e,f\}$ from $\mathcal{P}$ pick a
vertex shared by both edges $e$ and $f$, while for the
singleton $\{g\}$ pick the end-vertex which is not a pendant
vertex of $B$. Let $J$ be the set of vertices obtained from
$\mathcal{P}$ in this way, and set $A'=V(G)-J$. Observe that
each vertex in $J$ is a pendant vertex of $T$, so the subgraph
induced by the set $A'$ is the tree $T-J$. Furthermore, the
subgraph induced by $J$ is near-independent and its single edge
is the edge of $B$ adjacent to $g$. This shows that $\{A',J\}$
is the the required partition of $G$.

The implication (iii) $\Rightarrow$ (ii) was proved in Case 1
of the proof of Theorem <ref>, so it remains to
prove only the implication (ii) $\Rightarrow$ (i). Assume that
$G$ has a Xuong tree with a single odd cotree component, which
is heavy. Then $G$ is upper-embeddable, and by
Lemma <ref> it is amply upper-embeddable.

Let $G$ be a connected cubic graph on $n$ vertices where
$n\equiv 0$ $\pmod 4$. If $G$ admits a Xuong tree with a unique
odd cotree component which has at least three edges, then $G$
admits a coherent stable decycling partition.

§ COHERENT PARTITIONS OF CYCLICALLY $4$-EDGE-CONNECTED GRAPHS

In this section we prove that every cyclically
$4$-edge-connected cubic graph admits a coherent decycling
partition. This result strengthens Theorem <ref> by
eliminating the second possibility in its item (ii). The proof
uses two important results, proved by Payan and Sakarovitch
[32] and by Wormald [40], respectively. The
former guarantees the existence of a stable decycling partition
$\{A,J\}$ where the decycling set $J$ contains an arbitrary
preassigned vertex. The latter result enables us to create
cyclically $4$-edge-connected cubic graphs from smaller ones by
adding an edge and increasing the order by $2$. The
corresponding operation is called an edge extension and
is executed as follows. In a given cubic graph $G$ we take two
nonadjacent edges, subdivide each of them by a new vertex and
join the two resulting 2-valent vertices by a new edge. The
reverse operation is an edge reduction.

(Payan and Sakarovitch [32])
Let $G$ be a cyclically $4$-edge-connected cubic graph and let
$v$ be an arbitrary vertex of $G$. Then $G$ admits a stable
decycling partition $\{A,J\}$ such that $v$ belongs to the
decycling set $J$.

(Wormald [40])
Every cyclically $4$-edge-connected cubic graph other than
$K_4$ and $Q_3$ can be obtained from a cyclically
$4$-edge-connected cubic graph with fewer vertices by an

In [32], Payan and Sakarovitch observed  that
Theorem <ref> does not hold for cubic graphs with
cyclic connectivity $3$.

We are now ready for the main result of this section.

Every cyclically $4$-edge-connected cubic graph $G$ has a
coherent stable decycling partition. More precisely, if $G$ has
$n$ vertices, then

(i) for $n\equiv2\pmod4$ the vertex set of $G$
has a partition $\{A,J\}$ where $A$ induces a tree and
$J$ is independent;

(ii) for $n\equiv0\pmod4$ the vertex set of $G$
has a partition $\{A,J\}$ where $A$ induces a tree and
$J$ is near-independent.

From Section <ref> we already know that in a
cubic graph $G$ of order $n\equiv2\pmod4$ every stable
decycling partition is coherent. Thus we can assume that $G$ is
a cyclically $4$-edge-connected cubic graph of order
$n\equiv0\pmod4$. If $G$ is either $K_4$ and $Q_3$, then a
coherent decycling partition is easily found: one for $Q_3$ is
shown in Figure <ref>, and for $K_4$ any partition of
vertices into two $2$-element subsets is good. Now, let $G$ be
different from $K_4$ and $Q_3$. By Theorem <ref>,  $G$
arises from a cyclically $4$-edge-connected cubic graph $G'$ of
order $n-2$ by an edge extension. Two independent edges $xy$
and $wz$ of $G'$ are thus subdivided by vertices $u$ and $v$,
respectively, and $G$ is then created by adding the edge
$e=uv$. Since $G'$ is cyclically $4$-edge-connected and its
order is $2\pmod4$, it has a coherent decycling partition
$\{A',J'\}$ such that $A'$ induces a tree and $J'$ is
independent. Furthermore, according to
Theorem <ref>, we can assume that $x\in J'$. Let
$T'$ denote the tree induced by $A'$ in $G'$.

We show that $\{A'\cup\{v\}, J'\cup\{u\}\}$ is a coherent
decycling partition of $G$. Let us look at the distribution of
the vertices $y$, $w$, and $z$ with respect to the partition
$\{A',J'\}$. Since $x$ is in $J'$, $xy$ is an edge of $G'$, and
$J'$ is an independent set, we conclude that $y$ belongs to
$A'$. As regards the edge $wz$, either both its end-vertices
are contained in $A'$, or they belong to different sets of the
partition, say, $w\in J'$ and $z\in A'$. Observe that in either
case the induced subgraph $G[J'\cup\{u\}]$ has a single edge,
namely $xu$, so $J'\cup\{u\}$ is a near-independent set.
Furthermore, the subgraph $T=G[A'\cup\{v\}]$ is a tree: in the
former case it arises from $T'$ by subdividing its edge $wz$
with $v$, and in the latter case $T=T'+vz$.  In both cases
$\{A'\cup\{v\}, J'\cup\{u\}\}$ is a coherent decycling
partition of $G$, as claimed.

§ COHERENT PARTITIONS OF 3-CONNECTED CUBIC GRAPHS

In this section we strengthen
Theorem <ref> by showing that coherent decycling
partitions can be guaranteed in rich classes of cubic graphs
whose cyclic connectivity equals $3$. The main idea behind is
the existence of a canonical decomposition of $3$-connected
cubic graphs into cyclically $4$-edge-connected factors.
Although such a decomposition is likely to belong to the area
of mathematical folklore, we need to work out the necessary
details before they can be applied to our main result.

Let $G_1$ and $G_2$ be bridgeless cubic graphs. Pick a vertex $v_1$ in
$G_1$ and a vertex $v_2$ in $G_2$, remove the two vertices,
retain the dangling edges (more precisely, free edge-ends),
and identify each dangling edge of
$G_1-v_1$ with a dangling edge of $G_2-v_2$ to obtain a cubic
graph $G_1*G_2$. We say that $G_1*G_2$ is a $3$-sum of
$G_1$ and $G_2$ with respect to $v_1$ and $v_2$, the two
vertices being the root vertices for the $3$-sum.  The
three edges that connect the neigbours of $v_1$ to the
neighbours of $v_2$ form a $3$-edge-cut which we call the
principal edge cut of $G_1*G_2$. Observe that if $G_1$
and $G_2$ are $3$-connected, so is $G_1*G_2$.

Conversely, let $G$ be a $3$-connected cubic graph containing a
$3$-edge-cut $S$ whose removal leaves two nontrivial components
$H_1$ and $H_2$; note that $S$ is necessarily cycle-separating,
and vice versa. We can turn each $H_i$ to a cubic graph $\bar
H_i$ by taking a new vertex $x_i$ and attaching the three
dangling edges of $H_i$ to it. Clearly, both $\bar H_1$ and
$\bar H_2$ are $3$-connected. Moreover, $G=\bar H_1 * \bar
H_2$. We  have thus decomposed $G$ into a $3$-sum of two
smaller $3$-connected graphs $\bar H_1$ and $\bar H_2$. If any
of $\bar H_1$ and $\bar H_2$ contains a cycle-separating
$3$-edge-cut, we can repeat the process and obtain a set of
three cubic graphs such that $G$ can be reconstructed from them
by using $3$-sum twice. After a finite number of steps we
produce a collection $\{G_1, G_2, \ldots, G_r\}$ of
$3$-connected cubic graphs such that $G$ can be reconstructed
from them by repeated application of $3$-sum, but none of the
graphs $G_i$ can be expressed as a $3$-sum of two smaller cubic
graphs. In other words, each $G_i$ is cyclically
$4$-edge-connected. The collection $\{G_1, G_2, \ldots, G_r\}$
is called a decomposition of $G$ into a $3$-sum of
cyclically $4$-edge-connected graphs, and the graphs $G_i$ are
called the factors of the decomposition. As we confirm
in following theorem, the collection $\{G_1, G_2,\ldots, G_r\}$
is determined uniquely up to isomorphism and permutation of
factors. In this sense, it is appropriate to call it a
canonical decomposition of $G$.

Every $3$-connected cubic graph $G$ has a decomposition
$\{G_1,\penalty0 G_2,\ldots,G_r\}$ into cyclically
$4$-edge-connected graphs such that $G$ can be reconstructed
from them by repeated $3$-sums. The decomposition is unique up
to isomorphism and order of factors.

The fact that every $3$-connected cubic graph can be decomposed
into cyclically $4$-edge-connected factors has been explained
prior to the formulation of the theorem. As regards the
uniqueness, it is not difficult to see that if $S_1$ and $S_2$
are two distinct cycle-separating $3$-edge-cuts, then the
result of the decomposition into three $3$-connected cubic
graphs by using the two cuts does not depend on the order in
which they are taken. Indeed, if $S_1\cap S_2=\emptyset$, the
conclusion is obvious. If $S_1\cap S_2\ne \emptyset$, then the
intersection consists of a single edge, and again both ways in
which the decomposition is performed produce the same set of
$3$-connected cubic graphs up to isomorphism.

We are now ready for the main result of this section.

Every $3$-connected cubic graph whose canonical decomposition
into cyclically $4$-edge-connected cubic graphs contains at
most one cyclically odd factor admits a coherent decycling

Let $G$ be a $3$-connected cubic graph whose canonical
decomposition $\{G_1,\dots,G_r\}$ into cyclically
$4$-edge-connected graphs contains at most one cyclically odd
factor, say $G_1$. We may assume that $r\ge 2$ for otherwise
the result directly follows from Theorem <ref>.
Now, $G$ can be reconstructed from $\{G_1,\dots,G_r\}$ by a
repeated use of a $3$-sum. Furthermore, for cubic graphs $H$
and $K$ one has $\beta(H*K)=\beta(H)+\beta(K)-2$, so $G$ is
cyclically odd if and only if $G_1$ is cyclically odd.
Therefore, if we start the reconstruction of $G$ from $G_1$,
the statement of the theorem will follow immediately from
following the claim.

Claim. Let $G=H*K$ be a $3$-sum of cubic graphs where $H$
admits a coherent decycling partition and $K$ is cyclically
$4$-edge-connected with $\beta(K)$ even. Then $G$ also admits a
coherent decycling partition.

Proof of Claim. Let $x$ be the root vertex of $H$, let $x_1$,
$x_2$, and $x_3$ be its neighbours, and let $y$ be the root
vertex of $K$ with neighbours $y_1$, $y_2$, and $y_3$. We
assume that the principal 3-edge-cut of $H*K$ consists of the
edges $x_1y_1$, $x_2y_2$, and $x_3y_3$.

Theorem <ref> and the fact that every cyclically
$4$-edge-connected cubic graph is upper-embeddable imply that
$K$ has a coherent decycling partition $\{A_K,J_K\}$ where
$J_K$ is independent. Let $\{A_H, J_H\}$ be an arbitrary
coherent decycling partition for $H$; recall that the induced
subgraph $H[J_H]$ has at most one edge. If such an edge exists,
we call it a surplus edge. Let $T_H\subseteq H$ and
$T_K\subseteq K$ denote the trees induced by the sets $A_H$ and
$A_K$, respectively. Note that both trees are non-trivial,
because each of $H$ and $K$ has at least four vertices and
their decycling number is given by the formula $\lceil
n+2/4\rceil$, where $n$ is the number of vertices.

We distinguish two main cases depending on whether
$x\in J_H$ or $x\in A_H$.

Case 1. The root vertex of $H$ belongs to $J_H$.

choose the partition $\{A_K,J_K\}$ in such a way that $y\in
A_K$. This is indeed possible, because
Theorem <ref> tells us that we can pick a
neighbour $y'$ of $y$ and require that $y'\in J_K$; as a
consequence, $y$ lies $A_K$.  Now we can define a vertex
partition $\{A,J\}$ of $G$ by setting $A=A_H\cup (A_K-\{y\})$
and $J=(J_H-\{x\})\cup J_K$. To show that $\{A,J\}$ is a
coherent decycling partition we consider two subcases.

Subcase 1.1. The root vertex of $H$ is incident with
the surplus edge.

Without loss of generality we may assume that the
surplus edge of $H$ is $xx_3$. We now chose the partition
$\{A_K,J_K\}$ in such a way that $y_3\in J_K$. Since $T_K$ is
non-trivial, at least one of the edges incident with $y$
belongs to $T_K$, say $yy_1$, but possibly also $yy_2$. It
follows that $T_K-y$ is either a tree or it consists of two
trees, each containing a neighbour of $y$ different from $y_3$.
It is easy to see that the induced subgraph $T=G[A]$ is a tree:
depending on the structure of $T_K-y$ either
$T=T_H\cup\{x_1y_1\}\cup (T_K-y)$ or
$T=T_H\cup\{x_1y_1,x_2y_2\}\cup(T_K-y)$. In the former case,
$J=(J_H-x)\cup J(K)$, while in the latter case $J=(J_H-x)\cup
(J(K)\cup\{y_2\})$. By the assumptions, if $e$ is an edge
joining two vertices of $J$, then $e\in\{x_1y_1, x_2y_2,
x_3y_3\}$. Clearly, $x_3y_3$ is an edge of $G[J]$. In the
former case, $x_1y_1\in E(T)$ and $x_2y_2$ joins a vertex of
$T$ to a vertex of $J$. In the latter case both $x_1y_1$ and
$x_2y_2$ belong to $T$. In either case,  $G[J]$ has precisely
one edge, namely $x_3y_3$. Hence, $\{A,J\}$ is a coherent
decycling partition of $G$.

Subcase 1.2. The root vertex of $H$ is not incident
with the surplus edge.

As before, we choose a coherent
decycling partition $\{A_K,J_K\}$ where $y\in A_K$, but now we
are not restricted to choose a suitable neighbour $y'$ of $y$
which should be in $J_K$. For simplicity we again choose
$y_3\in J_K$. We may also assume that either $xx_1$ only, or
both $xx_1$ and $xx_2$, belong to $T_K$. As in the previous
subcase, the induced subgraph $G[A]$ is a tree (with identical
description as above), and $G[J]$ has at most one edge. If such
an edge exists, then it coincides with the surplus edge of $H$.
We have thus proved that $\{A,J\}$ is a coherent decycling
partition of $G$.

Case 2. The root vertex of $H$ belongs to $A_H$.

this case we choose the coherent partition $\{A_K,J_K\}$ in
such a way that $y\in J_K$; the existence of such a partition
is guaranteed by Theorem <ref>. Let $Y$ be the set
of all edges of $G$ having the form $x_iy_i$ where $x_ix$
belongs to $T_H$. Since $T_H$ is non-trivial, $1\le |Y|\le 3$.
Let us define a vertex partition $\{A,J\}$ of $G$ by setting
$A=(A_H-\{x\})\cup A_K$ and $J=J_H\cup(J_K-\{y\})$. Observe
that $T_H-x$ is a forest whose number of components equals
$|Y|$. It follows that $T=G[A]=(T_H-x)\cup Y\cup T_K$ is a
tree. Moreover, $G[J]$ has at most one edge, which, if it
exists, coincides with the surplus edge of $H$. Hence,
$\{A,J\}$ is a coherent decycling partition of $G$.

The proof is complete.

In the remainder of this section we show that
Theorem <ref> applies to the family of cubic
graphs defined by a  weaker form of cyclic $4$-connectivity
known as odd cyclic $4$-connectivity. A graph $G$ is said to be
odd-cyclically $k$-connected, for an integer $k\ge 2$,
if every induced subgraph $H\subseteq G$ such that
$\delta_G(H)$ is cycle-separating and $\beta(H)$ is odd has
$|\delta_G(H)|\geq k$.  The concept of odd cyclic
$4$-connectivity was independently introduced by Khomenko and
Glukhov [16] and Nebeský [26] in 1980 and
1983, respectively, for the study of the maximum genus of a

Every cyclically $k$-edge-connected cubic graph is clearly
odd-cyclically $k$-connected, but the converse is false.
Figure <ref> depicts an example of a cubic graph
which is odd-cyclically $4$-connected while its standard cyclic
connectivity equals only $3$.

An odd-cyclically $4$-connected cubic graph which
is not cyclically $4$-edge-connected.

Let $\{G_1, G_2,\ldots, G_r\}$ be the canonical decomposition
of an odd-cyclically $4$-connected cubic graph with cyclic
connectivity $3$. Then each $G_i$ has an even Betti number, and
so has $G$. In particular, $G$ has a coherent decycling
partition $\{A,J\}$ where $A$ induces a tree and $J$ is an
independent set.

It is sufficient to prove that if $H$ is a $3$-connected
odd-cyclically $4$-connected cubic graph which can be expressed
as a $3$-sum $K*L$ of cubic graphs $K$ and $L$, then both $K$
and $L$ are odd-cyclically $4$-connected and have an even Betti
number. By symmetry, it suffices to prove it for, say, $K$.

Since $H=K*L$, there exists a vertex $u$ in $K$ such that $K-u$
is an induced subgraph of $H$ with $|\delta_H(K-u)|=3$. By the
definition of odd-cyclic $4$-connectivity, $\beta(K-u)$ is
even. It follows that $\beta(K)$ is even, similarly $\beta(L)$
is even, and consequently $\beta(H)=\beta(K)+\beta(L)-2$ is
also even.

Next we prove that $K$ is odd-cyclically $4$-connected. Suppose
not. Then $K$ contains an induced subgraph $Q$ such that
$\beta(Q)$ is odd and $|\delta_K(Q)|\le 3$. Since $K$ is
$3$-connected, we infer that $|\delta_K(Q)|=3$. Let $Q'$ be the
other component of the graph $K-\delta_K(Q)$, that is,
$Q'=K-V(Q)$. Further, let $u$ be the root vertex of $K$ used
for the $3$-sum producing $H$. We can clearly assume that $u$
belongs to $Q'$. Note that $\beta(Q')$ is odd, too. Now, at
most one edge of $\delta_K(Q)$ is incident with $u$, because
$\delta_K(Q)$ is a minimum cycle-separating edge cut. However,
irrespectively of whether $\delta_K(Q)$ does or does not
contain such an edge, it is easy to see that $Q$ is an induced
subgraph of $H$ with $\beta(Q)$ odd and $|\delta_H(Q)|=3$,
contradicting the assumption that $H$ is odd-cyclically
$4$-connected. This completes the proof.

§ CUBIC GRAPHS WITH NO COHERENT DECYCLING PARTITIONS

The aim of this section is to present an infinite
family of 2-connected cubic graphs which have a stable
decycling partition but no coherent one. By
Theorem <ref>, this amounts to displaying an
infinite family $\mathcal{F}$ of $2$-connected tightly
upper-embeddable graphs. For convenience, the topological
language will be in the foreground throughout.

The family $\mathcal{F}$ will be built from two graphs
displayed in Figure <ref>. An important fact
about them is that they are claw-free, which means that
they do not contain an induced subgraph isomorphic to the
complete bipartite graph $K_{1,3}$. In fact, the entire family
$\mathcal{F}$ consists of claw-free graphs.

Simple $2$-connected claw-free cubic graphs were characterised
by Palmer et al. [31] (see <cit.> in 2002). Their
characterisation requires two operations. The first of them is
the well-known inflation of a vertex to a triangle. It
replaces a vertex $v$ with a triangle $W_v$ and attaches the
edges formerly incident with $v$ to distinct vertices of $W_v$.
The second operation is a diamond insertion, where a
diamond means a graph isomorphic to $K_4$ minus an edge.
This operation is performed by replacing an edge $e=uv$ with a
path $P_e=uu'v'v$ of length $3$ and substituting the inner edge
$u'v'$ of $P_e$  with a diamond $D_{e}$ in such a way that its
$2$-valent vertices are identified with $u'$ and $v'$,
respectively. More specifically, this is an insertion of
a diamond into $e$, see Figure <ref>

Insertion of a diamond into an edge.

We can repeat the operation of inserting a diamond into the
edge $e=uv$ by inserting a diamond into the edge $v'v$, and so
on, which results in replacing $e$ with a string of
diamonds. To be more explicit, we say that $e$ is replaced
with a string of $k$ diamonds, where $k\ge 0$, if $e$ is
replaced with an alternating sequence $uu_1, D_1, v_1u_2, D_2,
\ldots, v_{k-1}u_k, D_k, v_kv$ of edges and diamonds such that
the $2$-valent vertices of the diamond $D_i$ are $u_i$ and
$v_i$ for each $i\in\{1,2,\ldots,k\}$. The number $k$ is the
length of the string. The string collapses to the edge
$e=uv$ if $k=0$.

To finish the series of definitions needed to characterise
simple $2$-connected claw-free cubic graphs we define a
ring of diamonds to be a graph obtained from an even
cycle by substituting every second edge with a diamond.

The characterisation of simple $2$-connected claw-free cubic graphs
reads as follows.

(Palmer [31]) Let $G$ be a simple $2$-connected
cubic graph. Then $G$ is claw-free cubic graph if and only if
one of the following holds:

(i) $G$ is isomorphic to $K_4$,

(ii) $G$ is a ring of diamonds,

(iii) $G$ is obtained from a
$2$-edge-connected cubic graph $H$ by inflating each
vertex of $H$ to a triangle and by replacing certain
edges of $H$ with strings of diamonds.

We continue by defining the family $\mathcal{F}$.

Construction. Take a 2-connected cubic graph $K$ on
four vertices; there are two such graphs – the complete graph
$K_4$ on four vertices and the necklace $L_4$ obtained
from a $4$-cycle by replacing every second edge with a pair of
parallel edges. In $K$, inflate each vertex to a triangle;
these triangles are called vertex-triangles. In the
resulting graph $K'$ replace each edge not lying on a
vertex-triangle with a  string of diamonds with positive
length; different edges of $K'$ may accommodate different
numbers of diamonds. Include each graph obtained in this way in
$\mathcal{F}$. The smallest graphs in $\mathcal{F}$ are the
graphs $F_1$ and $F_2$ from Figure <ref>, which
are obtained by vertex inflation and diamond insertion from
$K_4$ or to $L_4$, respectively.

Our aim is to prove that all graphs in $\mathcal{F}$ are
tightly two-face embeddable. In the course of the proof it will
be convenient to say that a Xuong tree of a two-face-embeddable
cubic graph is light if the unique odd component of the
corresponding cotree is light, that is, it is formed by a
single edge. It follows from Theorem <ref> that
every Xuong tree of a tightly two-face-embeddable cubic graph
is light. A Xuong tree which is not light will be called

We need the following lemma.

If a cubic graph $G$ contains a light Xuong tree and $G'$
arises from $G$ by a diamond insertion, then $G'$ also contains
a light Xuong tree.

Assume that $G'$ arises from $G$ by inserting a diamond $D$
into an edge $e=uv$ of $G$. Let $u'$ be the $2$-valent vertex
of $D$ adjacent to $u$ in $G'$ and similarly let $v'$ be the
$2$-valent vertex of $D$ adjacent to $v$. Let $s$ and $t$
denote the two $3$-valent vertices of $D$.

Take an an arbitrary light Xuong tree $T$ of $G$. We show that
$T$ can be modified to a light Xuong tree of $G'$. We
distinguish three cases depending on the position of $e$ with
respect to $T$.

Case 1. The edge $e$ lies in $T$. In this case we
extend $T-e$ with the edges  $uu'$, $u's$, $st$, $sv'$, and
$v'v$ to obtain a spanning tree $T'$ of $G'$. It is easy to see
that $T'$ is light.

Case 2. The edge $e$ lies in an even cotree component
with respect to $T$. Recall that every even cotree component
with respect to $T$ can be partitioned into pairs of adjacent
edges. Let $f$ be the edge forming a pair with $e$, and let $Q$
be the component of $G-E(T)$ containing $e$ and $f$. Without loss
of generality we may assume that $v$ is the common endvertex of
both $e$ and $f$.  Now we extend $T$ with the edges $uu'$,
$u's$, $st$, and $sv'$ to obtain a spanning tree $T'$ of
$G'$. Observe that $Q$ is now transformed to an even component
of $G''$ containing the path $u'tv'v$ and the edge $f$, while
the odd component of $G-E(T)$ remains in $G'-E(T')$ intact.
Hence, $T'$ is a light Xuong tree of $G'$.

Case 3. The edge $e$ coincides with the one that forms
the odd component of $G-E(T)$.  Now we form $T'$ by adding to
$T$ the path $uu'sv't$ of $G'$. As a consequence, the path
$u'ts$ forms an even component of $G'-E(T')$ and the edge $v'v$
constitutes the only odd component of $G'-E(T')$. Again, $T'$
is a light Xuong tree of $G'$.

We proceed to the main result of this section. It characterises
all tightly two-face embeddable graphs within the class of
simple $2$-connected claw-free cubic graphs.

The following statements are equivalent for every simple
$2$-connected claw-free cubic graph $G$.

(i) $G$ is tightly two-face-embeddable.

(ii) $G\in\mathcal{F}$.

(i) $\Rightarrow$ (ii): Assume that $G$ is a simple
$2$-connected claw-free cubic graph which is tightly
two-face-embeddable. Then one of the cases (i), (ii) or (iii)
of  Proposition <ref> occurs. In cases (i) and
(ii) it is easy to find a heavy Xuong tree, so $G$ belongs to
the family of graphs characterised by (iii) of
Proposition <ref>. It follows that $G$ arises
from a $2$-connected cubic graph $H$ by inflating every vertex
of $H$ to a triangle and by replacing certain edges of $H$ with
strings of diamonds.

At first we show that $H$ has four vertices. Let $n$ denote the
order of $H$. We apply Nebeský's characterisation of
upper-embeddable graphs (Theorem <ref>) to $G$. Let
$X$ be the set of all edges of $G$ not lying on a triangle.
With this choice, each cyclically odd component of $G-X$ is a
vertex-triangle and each cyclically even component is a
diamond. Clearly, $\text{oc}(G-X)=n$. To calculate the number
of cyclically even components we count the contribution of each
edge of $H$ to both $\text{ec}(G-X)$ and $|X|$. Assume that an
edge $e$ of $H$ has been replaced with a string of $k$
diamonds. Since $k+1$ edges of the string belong to $X$, the
edge $e$ contributes $-1$ to the difference
$\text{ec}(G-X)-|X|$. There are $3n/2$ edges in $H$, so
$\text{ec}(G-X)-|X|=-3n/2$. Equation (<ref>) implies

$$2\ge 2\text{oc}(G-X)+\text{ec}(G-X)-|X|=2n-3n/2,$$

hence $n\le 4$. Recall that $G$ is two-face-embeddable, which
means that $|V(G)|\equiv 0\pmod4$. It follows that
$n=|V(H)|\equiv 0\pmod4$ as well, and therefore $n=4$. Thus $H=K_4$ or

Heavy Xuong trees in three small claw-free graphs.

To finish the proof of the implication (i) $\Rightarrow$ (ii)
we need show that to obtain $G$ each edge of $H$ must be
replaced with a string of diamonds which has positive length.
Suppose this is not the case, and there are certain edges in
$H$ which are inherited to $G$ without any diamond insertion.
First, let us examine the case where there is only one such
edge $e_0$ in $H$. Up to isomorphism, there are two
possibilities to choose $e_0$ in $L_4$ and one in $K_4$. In all
three cases $G$ admits a heavy Xuong tree $T$ with the odd cotree
component containing $e_0$; see Figure <ref>. Hence,
by Theorem <ref>,
$G$ is amply upper-embeddable, contrary to the
assumption. To proceed, observe that each diamond $D\subseteq
G$ supports an even component $Q$ of $G-E(T)$ such that
$Q\subseteq D$ and both edges of $\delta_G(D)$ are contained
in $T$. If we contract any number of diamonds in $G$ and
suppress the resulting $2$-valent vertices, $T$ will transform
to a heavy Xuong tree of the resulting cubic graph, with the
original heavy cotree component containing $e_0$ being
preserved. It follows that $G$ is amply upper-embeddable unless
each edge of $H$ has been replaced with a string of diamonds
of positive length. Summing up, we have proved that if $G$ is a
simple $2$-connected claw-free cubic graph which is tightly
two-face-embeddable, then $G\in\mathcal{F}$.

(ii) $\Rightarrow$ (i): Assume that $G\in\mathcal{F}$. We first
show that $G$ admits a light Xuong tree. As
Figure <ref> indicates, this is the case for
both $F_1$ and $F_2$. Since $G$ arises from a graph
$F\in\{F_1,F_2\}$ by iterated diamond insertion, a light
spanning tree in $G$ is guaranteed by Lemma <ref>.

To prove that $G$ is tightly two-face embeddable we need to
show that every Xuong tree of $G$ is light. We proceed by
contradiction and suppose that $G$ contains a heavy Xuong tree
$T$. By Lemma <ref>, we can assume that the cotree of
$T$ is acyclic. Let $C$ denote the corresponding cotree. We now
examine all possible ways of how $T$ and $C$ can intersect a
diamond or a vertex-triangle.

Firstly, we analyse the diamonds. It is clear that for each
diamond $D$ the intersection of $T$ with $\delta_G(D)$ consists
of either one or two edges. Accordingly, we distinguish several types of
diamonds three of which are of particular interest.

We say that a diamond $D$ is

* Type $1$, if exactly one edge of $\delta_G(D)$
belongs to $T$ and $C\cap D$ forms a path of length $2$
connecting the two $2$-valent vertices of $D$;

* Type $2$, if both edges of $\delta_G(D)$
belong to $T$ and $C\cap D$ forms a path connecting the
two $2$-valent vertices of $D$; and

* Type $3$, if both edges of $\delta_G(D)$
belong to $T$ and $C\cap D$ forms a path of length $3$
connecting a $3$-valent vertex of $D$ to a $2$-valent
vertex of $D$.

Next we discuss the vertex-triangles. It may be useful to
realise that $T$ contains at least one edge of each
vertex-triangle $W$ and at least one edge of each
$\delta_G(W)$. Two types of vertex-triangles are particularly

We say that a vertex-triangle $W$ is

* Type $1$, if $C\cap W$ is a path of length $2$
and exactly one edge of $\delta_G(W)$ belongs to $C$; and

* Type $2$, if $C\cap W$ is a path of length $2$
and all three edges of $\delta_G(W)$ belong to $T$.

Note that in Type 1 the cotree edge of $\delta_G(W)$ must be
incident with the initial or terminal vertex of the path $C\cap
W$, otherwise $T$ fails to be a spanning subgraph.

The following claim explains the importance of the five types
of diamonds and vertex-triangles specified above.

Claim. In $G$, there exists a heavy Xuong tree such that
each diamond is of Type $1$, $2$, or $3$, and each
vertex-triangle is of Type $1$ or $2$.

Transformation of diamonds to Type 1, 2, and 3.

Proof of Claim. We start with an arbitrary heavy Xuong tree
$T\subseteq G$ whose cotree $C$ is acyclic. Consider an
arbitrary diamond $D$ of $G$; let $u$ and $v$ be the $2$-valent
vertices and let $s$ and $t$ be the $3$-valent vertices of $D$.
If the edge $st$ belongs to $T$, then $D$ it is easily seen to
be one of Type 1, 2, or 3. To see it, it is sufficient to
realise that $C$ is acyclic and its unique odd component is
heavy. If $st$ belongs to $C$ then, up to isomorphism, there
are three possibilities for the distribution of edges of $D$
into $T$ and $C$; they are illustrated in
Figure <ref> on the left. In each of these three
cases one can find an edge $x$ of $D$ different from $st$ such
that the elementary switch $T'=T+st-x$ gives rise to a Xuong
tree whose cotree is again acyclic and has exactly one heavy
odd component. According to the notation introduced in
Figure <ref>, it is sufficient to take $x=tv$ in
all three cases. Moreover, with respect to $T'$ the diamond $D$
turns to be one of Types 1, 2, or 3. By repeating this
procedure wherever necessary we eventually obtain a Xuong tree
with all diamonds of Type 1, 2, or 3.

Transformation of vertex-triangles to Type 1 and 2.

We now take care of vertex-triangles. By the previous part of
the proof we may assume that $T$ already has the property that
each diamond is of Type 1, 2, or 3. Consider an arbitrary
vertex-triangle $W$ of $G$. At least one edge of $W$ belongs to
$T$ and at least one edge of $\delta_G(W)$ belongs to $T$. If
exactly one edge of $W$ belongs to $T$, then, up to
isomorphism, there are two possibilities for the distribution
of edges of $\delta_G(W)$ to $T$ and $C$, which depend on the
size of $\delta_G(W) \cap E(T)$: if $|\delta_G(W)\cap E(T)|=2$,
then $W$ is Type 1, and if $|\delta_G(W)\cap E(T)|=3$, then $W$
is Type 2. The situation that $|\delta_G(W)\cap E(T)|=1$ does
not occur, as $T$ would not be connected. Next assume that
exactly two edges of $W$ belong to $T$. This leads to three
possible distributions, two with $|\delta_G(W)\cap E(T)|=1$ and
one with $|\delta_G(W)\cap E(T)|=2$, see
Figure <ref> on the left. The situation that
$|\delta_G(W)\cap E(T)|=3$ does not occur, because it would
create a light odd cotree component of $C$.

Observe that if $W$ is neither Type 1 nor Type 2, then at least
one edge of $\delta_G(W)$ lies in $C$. If $z$ is such an edge,
then $z$ joins $W$ to a diamond of Type 1, implying that $C$
lies in a cotree component with at least three edges.
With this in mind, it is easy to perform a suitable elementary
switch of the form $T'=T+x-y$ in such a way that the resulting
tree $T'$ is again a heavy Xuong tree and, moreover, $W$ turns
to a vertex-triangle of Type 1 or Type 2. The transformations
are indicated in Figure <ref>. After performing
these modifications as many times as necessary we produce a
Xuong tree, still denoted by $T$, where each diamond is Type 1,
2, or 3, and each vertex-triangle is Type 1 or 2. The unique
odd component of the corresponding cotree remains heavy by all
theese modifications. This proves the claim.

We are ready to derive a contradiction. For $i\in\{1,2,3\}$,
let $n_i$ denote the number of $i$-valent vertices of $T$.  A
straightforward inductive argument implies that $n_1=n_3+2$.
Since the diamonds and the vertex-triangles partition the
vertex set of $G$, we can express $n_1$ and $n_3$ as sums of
values ranging through the set $\mathcal{D}$ of all diamonds
and the set $\mathcal{W}$ of vertex-triangles of $G$. Let $d_i$
denote the number of diamonds of Type $i$, and let $w_i$ denote
the number of vertex-triangles of Type $i$. Clearly,

Note that every vertex-triangle $W$ of Type 1 is matched to a
unique diamond $D_W$ of Type 1 via a cotree edge $e_W$, and
together they form the subgraph $W\cup\{e_W\}\cup D_W$. There
exist $w_1$ such subgraphs in $G$, and since each of them
encloses a cotree component comprising five edges, we conclude
that $w_1\le 1$ and $w_2\ge 3$.

Given an induced subgraph $K\subseteq G$, set
$\lambda(K)=n_1(K)-n_3(K)$, where $n_i(K)$ denotes the number
of $i$-valent vertices of $T$ contained in $K$. In particular,
for a diamond $D$ we have $\lambda(D)=2-1=1$ if $D$ is Type 1;
$\lambda(D)=1-1=0$ if $D$ is Type 2; and $\lambda(D)=2-0=2$ if
$D$ is Type 3. Similarly, for a vertex-triangle $W$ we have
$\lambda(W)=2-0=2$ if $W$ is Type 1, and $\lambda(W)=1-0=1$ if
$W$ is Type 2. Putting this information together we obtain:

\begin{align*}
\sum_{D\in\mathcal{D}}\lambda(D)+\sum_{W\in\mathcal{W}}\lambda(W)\\
&=1d_1+0d_2+2d_3+2w_1+1w_2\ge w_2\ge 3,
\end{align*}

which is a contradiction. Our initial assumption that
$G\in\mathcal{F}$ admits a heavy Xuong tree was therefore
false; it follows that $G$ is tightly upper-embeddable. The
proof is complete.

The collection of known tightly two-face-embeddable graphs can
be significantly enlarged by applying a specific form of a
well-known operation, known as the $2$-sum of cubic graphs.
Before defining this operation it is convenient to recall that
a cubic graph $G$ is tightly two-face-embeddable if and only if
every Xuong tree of $G$ is light, that is, the unique odd
component of the corresponding cotree is formed by a single
edge (Theorem <ref>). An edge $e$ of a tightly
two-face-embeddable cubic graph will be called odd if
there exists a Xuong tree $T$ such that $e$ consitutes the
unique odd cotree component of $G-E(T)$.

Let $G_1$ and $G_2$ be two tightly two-face-embeddable graphs,
and let $e_i$ be an odd edge of $G_i$ for $i\in\{1,2\}$. We
construct a new graph $G$ by adding to $(G_1-e_1)\cup
(G_2-e_2)$ two independent edges $f_1$ and $f_2$, each joining
a $2$-valent vertex of $G-e_1$ to a $2$-valent vertex of
$G-e_2$, in such a way that $G$ becomes cubic. We say that $G$
is an odd $2$-sum of $G_1$ and $G_2$ with respect to
$e_1$ and $e_2$. It is easy to see that $G$ is again
$2$-connected and that the two newly added edges form a
$2$-edge-cut of $G$. This cut will be referred to as the
principal $2$-edge-cut of the $2$-sum.

An odd $2$-sum of two $2$-connected tightly two-face embeddable
cubic graphs is again $2$-connected and tightly two-face

Let $G_1$ and $G_2$ be tightly two-face-embeddable graphs with
odd edges $e_1$ and $e_2$, respectively, and let $G$ be an odd
$2$-sum of $G_1$ and $G_2$ with respect to $e_1$ and $e_2$. Let
$f_1$ and $f_2$ be the edges of the principal $2$-edge-cut of

Take Xuong trees $T_1\subseteq G_1$ and $T_2\subseteq G_2$ for
which $e_1$ and $e_2$, respectively, form the corresponding odd
components. Observe that $(T_1\cup T_2)+f_1$ is a spanning tree
of $G$ and that $f_2$ constitutes the unique odd component of
the corresponding cotree. Thus $G$ is two-face-embeddable. To
prove that $G$ is tightly $2$-face-embeddable it remains to
show that for every Xuong tree $T$ of $G$ is light.

Suppose to the contrary that $G$ admits a Xuong tree $T$ such
that $G-E(T)$ has a heavy odd component, which we denote by
$H$. For $i\in\{1,2\}$ set $G_i'=G_i-e_i$ and $T_i=T\cap G_i'$.
Clearly, $T$ contains at least one of the edges $f_1$ and
$f_2$. Accordingly, we have two cases to consider.

Case 1. The spanning tree $T$ contains exactly one edge
of the principal edge cut. Without loss of generality we may
assume that $f_1$ is contained in $T$. It follows that
$T=T_1\cup\{f_1\}\cup T_2$ and both $T_1$ and $T_2$ are
spanning trees of $G_1$ and $G_2$, respectively. Now, if $H$
does not contain $f_2$, then $H$ is a heavy odd cotree component
with respect to either $T_1$ or $T_2$. However, this is
impossible because both $G_1$ and $G_2$ are tightly
upper-embeddable. Therefore $H$ contains $f_2$. For
$i\in\{1,2\}$ set $H_i=H\cap G_i'$. Since $H$ is odd and
contains $f_2$, both $H_1$ and $H_2$ have the same parity and
at least one of them is nonempty, say $H_1$. If $H_1$ is even,
then $H_1\cup\{e_1\}$ is a unique odd component of
$G_1-E(T_1)$, and is heavy, which is a contradiction. It
follows that both $H_1$ and $H_2$ are odd and consequently both
$T_1$ and $T_2$ have only even cotree components in $G_1$ and
$G_2$, respectively. This contradiction excludes Case 1.

Case 2. The spanning tree $T$ contains both edges of
the principal edge cut. In this case exactly one of $T_1$ and
$T_2$ is connected, say $T_1$. It follows that $T_1$ is a
spanning tree of $G_1$ and $T_2+e_2$ is a spanning tree of
$G_2$. Since $T$ contains both edges of the principal
$2$-edge-cut, each cotree component with respect to $T$ must be
contained either in $G_1'$ or in $G_2'$. If $H\subseteq G_2'$,
then $T_2+e_2$ would be a heavy Xuong tree of $G_2$, which is
impossible because $G_2$ is tightly two-face-embeddable.
Therefore $H\subseteq G_1'$. Now, $H$ cannot have a common
vertex with $e_1$, because $T_1$ would be a Xuong tree of $G_1$
with all cotree components even, one of them being $H\cup
\{e_1\}$. But if $H$ has no common vertex with $e_i$, then it
constitutes a heavy odd component of $G_1-E(T_1)$, which is
impossible because $G_1$ is tightly two-face-embeddable. Thus
Case 2 cannot happen as well, and the statement is proved.

In certain cases, odd edges are not difficult to specify. For
instance, both the necklace $L_4$ and the graph of order $8$
obtained from the dipole $D_2$ by inserting a digon into each
edge are easily seen to be tightly two-face embeddable graphs.
It is also easy to see that each edge lying on a digon in any
of these two graphs is odd. Consulting
Figure <ref> again we can conclude that in the
two basic graphs $F_1$ and $F_2$ of the family $\mathcal{F}$
each edge lying on a vertex-triangle is odd. Since
vertex-triangles are preserved by a diamond insertion and, by
Lemma <ref>, a tight spanning tree of the smaller
graph extends to a tight spanning tree of the larger one, we
conclude that every edge lying on a vertex-triangle of any
graph $F\in\mathcal{F}$ is also odd.

§ CONCLUDING REMARKS

In Theorem <ref> we have characterised amply
two-face embeddable graphs as those which admit a Xuong tree
whose single odd cotree component has at least three edges.
Finding a similar
characterisation for amply one-face embeddable graphs – or
even finding the “right” definition of ample one-face
embeddability that would be compatible with that for ample
two-face embeddability – remains an open problem.

If we wish to prove that a given cubic graph $G$ is amply
two-face embeddable it is sufficient to find a heavy Xuong tree
in $G$. By contrast, the proof of
Theorem <ref> suggests that to argue that $G$
is not amply two-face-embeddable is not such an easy
task. The reason is that we do not have a tool similar to
Nebeský's theorem, which can be efficiently used to prove
that a graph is not upper-embeddable. By
Equation (<ref>), a connected graph $G$ is
upper-embeddable if and only if

\begin{equation*}\label{eq:ue}
\text{ec}(G-X)+2\text{oc}(G-X)-2\le |X|
\end{equation*}

for each subset $X\subseteq E(G)$. In other words, to prove
that a connected cubic graph is not upper-embeddable it is
sufficient to identify a subset $Y\subseteq E(G)$ such that
$\text{ec}(G-Y)+2\text{oc}(G-Y)-2>|Y|$. In this context it is a
natural question to ask whether there exists a  function
$\alpha\colon E(G)\to\mathbb{Z}$ “similar” to the Nebeský function
$\nu(X)= \text{ec}(G-X)+2\text{oc}(G-X)-2$
such that a connected cubic graph
is amply upper-embeddable (or at least amply
two-face-embeddable) if and only $\alpha(X)\le |X|$ for each
subset $X\subseteq E(G)$.

Theorem <ref> offers a natural question of
how amply and tightly upper-embeddable graphs are distributed
within the class of cubic graphs. In general, tightly
upper-embeddable cubic graphs are not easy to find. Moreover,
it does not seem easy to prove that a given cubic graph is
tightly upper-embeddable. We have shown that there exist
infinite families of tightly upper-embeddable cubic graphs with
connectivity $1$ and $2$. However, no examples of $3$-connected
tightly upper-embeddable graphs are known to us. This is why we
conjecture that a 3-connected cubic graph admits a coherent
decycling partition if and only if it is upper-embeddable
(Conjecture <ref>).

As far as cubic graphs with connectivity $2$ are concerned,
tight upper embeddability appears to be a rare event. This
indicates that among the upper-embeddable graphs those that are
tightly upper-embeddable should constitute a negligible part.
Therefore, if we take into account that almost all cubic graphs
are upper-embeddable and return to the equivalent language of
decycling partitions, it seems likely that
Problem <ref> has a positive answer. In other
words, we make the following conjecture.

Almost all cubic graphs contain an induced tree whose
removal leaves a subgraph with at most one edge.

§ ACKNOWLEDGEMENTS

The authors express their gratitude to the anonymous
referees for their careful reading and constructive
suggestions, and to J. Fiala and J. Karabáš for useful

[1]
S. Bau, N. C. Wormald, and S. Zhou, Decycling numbers of random regular graphs, Random Structures Algorithms 21 (2002), 397–413.

[2]
L. W. Beineke and R. C. Vandell, Decycling graphs, J. Graph Theory 25 (1997), 59–77.

[3]
J. Chen and Y. Huang, Maximum genus, Topics in Topological Graph Theory (L. Beineke, R. Wilson (in consultation with J. L. Gross, and T. W. Tucker), eds.), Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2009, pp. 34–44.

[4]
M. L. Furst, J. L. Gross, and L. A. McGeoch, Finding a maximum-genus graph imbedding, J. ACM 35 (1988), 523–534.

[5]
M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman, 1979.

[6]
M. R. Garey, D. S. Johnson, and L. J. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci. 1 (1976), 237–267.

[7]
H. Glover, K. Kutnar, A. Malnič, and D. Marušič, Hamilton cycles in $(2,\text{\rm odd},3)$-Cayley graph, Proc. Lond. Math. Soc. 104 (2012), 1171–1197.

[8]
H. Glover, K. Kutnar, and D. Marušič, Hamiltonian cycles in cubic Cayley graphs: the $\langle 2,4k,3\rangle$ case, J. Algebraic Combin. 30 (2009), 447–475.

[9]
H. Glover and D. Marušič, Hamiltonicity of cubic Cayley graphs, J. Eur. Math. Soc. (JEMS) 9 (2007), 775–787.

[10]
A. D. Glukhov, A contribution to the theory of maximum genus of a graph, Structure and Topological Properties of Graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1981, pp. 15–29 (Russian).

[11]
Y. Huang and Y. Liu, Maximum genus and maximum nonseparating independent set of a $3$-regular graph, Discrete Math. 176 (1997), 149–158.

[12]
S. Janson, T. Luczak, and A. Rucinski, Random graphs, John Wiley & Sons, 2000.

[13]
M. Jungerman, A characterization of upper-embeddable graphs, Trans. Amer. Math. Soc. (1978), 401–406.

[14]
F. Kardoš, A computer-assisted proof of the Barnette-Goodey conjecture: Not only fullerene graphs are Hamiltonian, SIAM J. Discrete Math. 34 (2020), 62–100.

[15]
R. M. Karp, Reducibility among combinatorial problems, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA (Raymond E. Miller and James W. Thatcher, eds.), The IBM Research Symposia Series, Plenum Press, New York, 1972, pp. 85–103.

[16]
N. P. Khomenko and A. D. Glukhov, Single-component $2$-cell embeddings and maximum genus of a graph, Some topological and combinatorial properties of graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1980, pp. 5–23 (Russian).

[17]
N. P. Khomenko, N. A. Ostroverkhy, and V. A. Kuzmenko, The maximum genus of a graph, $\phi$-Transformations of Graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1973, pp. 180–207 (Ukrainian, English summary).

[18]
G. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72 (1847), 497–508.

[19]
A. Kotzig, From the theory of finite regular graphs of degree three and four, Časopis pěstov. mat. 82 (1957), 76–92 (Slovak).

[20]
K. Kutnar and D. Marušič, Hamilton cycles and paths in vertex-transitive graphs—Current directions, Discrete Math. 309 (2009), 5491–5500.

[21]
D. Li and Y. Liu, A polynomial algorithm for finding the minimum feedback vertex set of a $3$-regular simple graph, Acta Math. Sci. Ser. B 19 (1999), 375–381.

[22]
Y. D. Liang, On the feedback vertex set problem in permutation graphs, Inform. Process. Lett. 52 (1994), 123–129.

[23]
S. Long and H. Ren, The decycling number and maximum genus of cubic graphs, J. Graph Theory 88 (2018), 375–384.

[24]
W. McCuaig, Edge reductions in cyclically k-connected cubic graphs, J. Combin. Theory Ser. B 56 (1992), 16–44.

[25]
B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, 2001.

[26]
L. Nebeský, A note on upper embeddable graphs, Czechoslovak Math. J. 33 (1983), 37–40.

[27]
L. Nebeský, A new characterization of the maximum genus of a graph, Czechoslovak Math. J. 31 (1981), 604–613.

[28]
R. Nedela and M. Škoviera, Atoms of cyclic connectivity in cubic graphs, Mathematica Slovaca 45 (1995), 481–499.

[29]
, Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs, J. Combin. Theory Ser. B 155 (2022), 17–44.

[30]
S. Oum, Perfect matchings in claw-free cubic graphs, Electron. J. Combin. 18 (2011), $\#$62.

[31]
E. M. Palmer, R. C. Read, and R. W. Robinson, Counting claw-free cubic graphs, SIAM J. Discrete Math. 16 (2002), 65–73.

[32]
C. Payan and M. Sakarovitch, Ensembles cycliquement stables et graphes cubiques, Cahiers du Centre d'Etudes de Recherche Operationelle 17 (1975), 319–343 (French).

[33]
C. Payan and N. H. Xuong, Upper embeddability and connectivity of graphs, Discrete Math. 27 (1979), 71–80.

[34]
G. Ringel, The combinatorial map color theorem, J. Graph Theory 1 (1977), 141–155.

[35]
R. W. Robinson and N. C. Wormald, Almost all regular graphs are hamiltonian, Random Structures Algorithms 5 (1994), 363–374.

[36]
E. Speckenmeyer, On feedback vertex sets and nonseparating independent sets in cubic graphs, J. Graph Theory 12 (1988), 405–412.

[37]
S. Stahl, Generalized embedding schemes, J. Graph Theory 2 (1978), 41–52.

[38]
S. Ueno, Y. Kajitani, and S. Gotoh, On the nonseparating independent set problem and feedback vertex set problem for graphs with no vertex degree exceeding three, Discrete Math. 72 (1988), 355–360.

[39]
A. T. White, Graphs of groups on surfaces, Interactions and Models, North Holland, 2001.

[40]
N. C. Wormald, Classifying $k$-connected cubic graphs, Lecture Notes in Math. 748 (1979), 199–206.

[41]
N. H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B 26 (1979), 217–225.