Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 79–93
On 2-factors with long cycles in cubic graphs∗
André Kündgen †
Department of Mathematics, California State University San Marcos
San Marcos, California 92096, USA
R. Bruce Richter
Department of Combinatorics & Optimization, University of Waterloo
Waterloo, Ontario, N2L 3G1, Canada
Received 25 May 2010, accepted 6 October 2010, published online 23 March 2011
Abstract
Every 2-connected cubic graph G has a 2-factor, and much effort has gone into studying
conditions that guarantee G to be Hamiltonian. We show that if G is not Hamiltonian, then
G is either the Petersen graph or contains a 2-factor with a cycle of length at least 7. We
also give infinite families of, respectively, 2- and 3-connected cubic graphs in which every
2-factor consists of cycles of length at most, respectively, 10 and 16.
Keywords: Cubic graph, 2-factor, long cycle, snark, infinite graph
Math. Subj. Class.: 05C38, 05C45, 05C70
1 Introduction
A theorem of Petersen [6] states that every cubic 2-connected graph G has a perfect match-
ing, and thus a 2-factor. Much effort has gone into studying conditions for when G has a
2-factor consisting of only one cycle, that is G is Hamiltonian. This motivates our defini-
tion of `(G) as the length of a longest cycle in any 2-factor of G, and any such cycle as a
longest 2-factor cycle. Obviously G is Hamiltonian precisely when `(G) = |V (G)|. We
also call any 2-factor achieving `(G) a longest 2-factor of G. (All graphs in this work are
simple; that is, there are no loops or multiple edges.)
Petersen’s theorem says that `(G) is well-defined when G is cubic and 2-connected. A
typical proof of Petersen’s theorem simply verifies that Tutte’s 1-factor condition holds for
∗Dedicated to Michael O. Albertson.
†Corresponding author.
E-mail addresses: akundgen@csusm.edu (André Kündgen), brichter@math.uwaterloo.ca (R. Bruce Richter)
Copyright c© 2011 DMFA Slovenije
80 Ars Math. Contemp. 4 (2011) 79–93
cubic 2-connected graphs. Schönberger [7] (see also [9, Exercise 3.3.17] and [2, Corol-
lary 4.4]) found a strengthening of Petersen’s theorem by showing that every edge f in
a 2-connected cubic graph G can be extended to a 1-factor, and so G contains a 2-factor
avoiding f . This also guarantees that G must have a 2-factor using any two specified edges
e1, e2, since we can subdivide e1, e2 and connect the new vertices with the new edge f and
then consider the 2-factor avoiding f in the new cubic graph.
Schönberger’s theorem allows us to study `(G) in a slightly more general context. A
graph is near-cubic if every vertex has degree 3, except for at most one vertex of degree 2.
Schönberger’s theorem implies that every 2-connected near-cubic graph G has a 2-factor,
and thus `(G) is defined for this wider class.
Jackson and Yoshimoto [3] prove a theorem that implies that a 3-connected cubic graph
G has a 2-factor in which every component has length at least 5. In particular, for a 3-
connected cubic graph G, `(G) ≥ 5.
A near-cubic graph is cyclically k-connected if the removal of fewer than k edges does
not create a graph with cycles in two different components, and we let Ck(n) denote the
class of all near-cubic cyclically k-connected graphs on n vertices. Observe that, in a
cubic graph, a minimal size edge-cut is either a matching or the 3 edges incident with a
vertex, so that, for k ≤ 3, the three notions of being cyclically k-connected, being k-edge
connected, and being k-connected are all equivalent. Subdividing an edge does not affect
cyclic connectivity, so that this notion is a more useful indicator of the structure of near-
cubic graphs. We define Lk(n) as the least value of `(G), taken over all graphs G in Ck(n).
The only cubic graphs on at most 6 vertices are the 3-connected graphs K4, K3,3 and
the triangular prism K3K2. All of these are Hamiltonian, as are all other 2-connected
cubic graphs on 8 or 10 vertices, with the exception of the Petersen graph P (see Figure 2.)
It is also not hard to see that the near-cubic graphs G∗ obtained by subdividing any 2-
connected cubic graph G on at most 10 vertices other than P is also Hamiltonian, and it
follows that L2(n) = n for 4 ≤ n ≤ 9, whereas L2(10) = 5 and L2(11) = 6. With
some more case analysis it can be shown that L2(n) = n − 5 for 10 ≤ n ≤ 16, except
L2(15) = 9, and the constructions achieving these values are given at the end of the proof
of Theorem 2.1. For general k, observe that any G ∈ Ck(n) (with the possible exception
of K4 and K3,3) has girth at least k, and thus `(G) ≥ k and n ≥ 2k. By considering an
arbitrary 2-factor, it is not hard to see that Lk(n) = n for n = 2k, except for P yielding
L5(10) = 5.
The obvious question is, what is the behavior of L2(n), and more generally Lk(n), as
n tends to infinity. In Section 2, we show that, for all n, L2(n) ≤ 11 and L3(n) ≤ 16. In
Section 3 we prove that, for all n ≥ 12, L2(n) ≥ 7.
Our consideration of the parameter L3(n) arose from the question: how does Petersen’s
Theorem generalize to infinite graphs? Tutte [8] proved his 1-factor theorem for locally
finite graphs, so the modern proof of Petersen’s Theorem from Tutte’s Theorem applies
to show that every 2-connected cubic graph has a 2-factor. In the infinite case, we were
initially interested in whether there is a 2-factor in which every component is finite or
whether there is a 2-factor in which every component is infinite. Thomassen (personal
communication) gave us an example of a 2-connected cubic graph with infinitely many
ends so that every 2-factor must have an infinite component. The construction showing
L3(n) ≤ 16 provides an infinite (1-ended) 3-connected cubic graph in which every 2-factor
has only cycles of length at most 16. In Section 4, we provide an example of an infinite
(1-ended) 3-connected cubic graph in which every 2-factor is a 2-way infinite Hamilton
A. Kündgen and R. B. Richter: On 2-factors with long cycles in cubic graphs 81
path.
2 Upper bounds
In this section we prove that L2(n) ≤ 11 and L3(n) ≤ 16.
For our constructions we first need some simple observations about the Petersen graph
P: every 2-factor in P consists of two 5-cycles, and every 5-cycle is in a unique 2-factor.
The edges of P partition into five sets of three edges, no two of which are together in any
path of length 3 in P; any 2-factor uses precisely two edges from each of the five sets and
the two edges from the same set are in distinct components of the 2-factor.
The 2-merge of a graph G (at an edge xy of G) with a graph H (at an edge uv of H)
means that we take disjoint copies of G and H and replace the edges xy and uv with the
edges xu and yv. If G and H are 2-connected near-cubic graphs, then their 2-merge is also
2-connected and near-cubic, as long as at least one of G and H is cubic.
If G is a cubic graph, then the graph G∗ is obtained from G by subdividing one edge
of G. If G is a graph and w is a vertex of degree 2 in G, then suppressing w results in the
graph Gw obtained from G−w by adding in an edge joining the two neighbours of w. If
W is a set {w1, w2, . . . , wk} of vertices, all with degree 2 in G, then suppressing W results
in the graph (· · · (G  w1)  w2)  · · · )  wk. We will be careful to only suppress vertices
in situations when no parallel edges can arise.
For “large” values of n we have the following upper bounds; we conjecture equality
holds for n sufficiently large.
Theorem 2.1. L2(n) ≤ 11 when n is congruent to 2 or 6 modulo 10, and L2(n) ≤ 10
otherwise.
Proof. The result is obviously true for n ≤ 10, and follows for n = 11 by the subdivided
Petersen graph P∗, and for n = 12 by replacing a vertex of P by a triangle. Thus, we may
assume n > 12.
Consider n = 10k for some k ≥ 1. Take disjoint copies G1, . . . Gk of P, each with
two specified edges uivi and xiyi of Gi not in the same cycle of any 2-factor of Gi. We
iteratively 2-merge all the Gi, starting with the 2-merge G1 (at x1y1) with G2 (at u2v2),
then 2-merging this (at x2y2) with G3 (at u3v3), and in general merging Gi at xiyi with
Gi+1 at ui+1vi+1. The resulting graph H(k) is a cubic 2-connected graph on n vertices.
•
•
•
•
• •
•
•
•
•
UUUU
UUUU
UU

6666666666
iiii
iiii
ii
))))


HHH
H
vvvv
iiiiiiii
66666666
UUUUUUUU




•
•
•
•
• •
•
•
•
•
UUUU
UUUU
UU

6666666666
iiii
iiii
ii
))))


HHH
H
vvvv
iiiiiiii
66666666
UUUUUUUU




•
•
•
•
• •
•
•
•
•
UUUU
UUUU
UU

6666666666
iiii
iiii
ii
))))


HHH
H
vvvv
UUUUUUUU




66
66
66
66
iiiiiiiiy1 v2
x1 u2
y2 v3
x2 u3
]]]]]]]]]]]]]]
aaaaaaaaaaaaaa
]]]]]]]]]]]]]]
aaaaaaaaaaaaaa
Figure 1: H(3).
Claim 1. For k ≥ 2, `(H(k)) = 10.
Proof. It is easy to see that any 2-factor of H(k) arises from a 2-factor of the Gi’s by
doing the specified edge replacements where necessary, and thus the length of each cycle
82 Ars Math. Contemp. 4 (2011) 79–93
in a 2-factor of H(k) is a multiple of 5. Taking a 2-factor in each Gi containing both of the
specified edges, we obtain a 2-factor of H(k) consisting of two 5-cycles (one each in G1
and Gk) and k − 1 10-cycles, so that `(H(k)) ≥ 10.
To see that equality holds, observe that any 2-factor F of H(k) induces a 2-factor Fi
in each Gi. Each Fi has two cycles of length 5 and none uses both edges that are switched
to connect Gi with Gi−1 and Gi+1. Thus, each component of F can intersect at most two
consecutive Gi and, therefore, has length at most 10. 4
To complete the proof of Theorem 2.1, let n = 10k + r, with 1 ≤ r ≤ 9.
Case r = 6. In this case 2-merge H(k) at u1v1 with K3,3, which at the most can lengthen
the 5-cycle in H(k) through u1v1 by six vertices to an 11-cycle, and hence L(10k + 6) ≤
11.
Case r = 2. Here we 2-merge H(k− 1) with a K3,3 each at u1v1 and xk−1yk−1 to obtain
L(10(k − 1) + 12) ≤ 11, since here k ≥ 2.
The following construction is useful in many of the remaining cases. The (2k − 1)-
replacement in G at the edge w1z1, is obtained by subdividing the edge w1z1 2k − 1
times, thereby creating the path (w1, w2, . . . , wk, v, zk, zk−1, . . . , z1), and then adding all
the edges wizi, i = 2, 3, . . . , k. It is easy to see that, if k ≥ 2, for any (2k−1)-replacement
G′ in G and any 2-factor F of G, there is a 2-factor F ′ that naturally extends F ; in par-
ticular, `(G′) ≥ `(G). In the case k = 1, the (2k − 1)-replacement is simply subdividing
w1z1.
If r is not 2 or 6, then there exist s ∈ {0, 1, 3, 4, 5} and t ∈ {0, 4} such that r = s+ t.
Start with H(k). If t = 4, then 2-merge H(k) at xkyk with a K4 to obtain a graph G′ on
10k + t vertices. If k ≥ 2, then `(G′) = 10, while for k = 1 `(G′) = 9. If s ∈ {1, 3, 5},
s-replace u1v1, while if s = 4 we 2-merge G′ at u1v1 with a K4. None of these operations
increases ` beyond 10.
To obtain a construction for the 3-connected case, let w, z be non-adjacent vertices in
P, let c be their common neighbor, and let the remaining neighbors of w be u, v and the
remaining neighbors of z be x, y, where ux and vy are edges of P. Observe that every
5-cycle in P that contains w and z also contains c and exactly one of ux and vy. Moreover,
P−z has exactly two 2-factors: a 9-cycle through wc and wu and a 9-cycle through wc and
wv.
•
•
•
• •
•
•
• •
•vv
vv
vv
vv
vv
))
))
))
))
)) 
HHHHHHHHHH
UUUU

6666
iiii
))))))))
vv
vv
vv
vv




HH
HH
HH
HH
z
c
w
v y
xu
Figure 2: Petersen graph P.
A 3-merge of a cubic graph G (at a vertex w in G) with a near-cubic graph H (at a
degree 3 vertex z of H) is obtained from disjoint copies of G − w and H − z by adding a
A. Kündgen and R. B. Richter: On 2-factors with long cycles in cubic graphs 83
matching u1x1, u2x2, u3x3 from the neighborhood {u1, u2, u3} of w to the neighborhood
{x1, x2, x3} of z. The resulting near-cubic graph is cyclically 3-connected if and only if
both G and H are.
Theorem 2.2. L3(n) ≤ 16.
Proof. The result is obviously true for n ≤ 16.
We start by considering the case n = 8k + 2, k ≥ 2. Take disjoint copies G1, . . . Gk
of P, each with the specified vertices ui, vi, wi, ci, xi, yi, zi as above. We obtain the graph
J(k) by iteratively 3-merging the Gi, beginning with G1 (at z1) and G2 (at w2), and then
3-merging this (at z2) with G3 (at w3), and so on. The specific 3-merges we use include
the edges in Mi = {ciui+1, xivi+1, yici+1} (see Figure 3.)
•
•
•
• •
•
•
• •
vv
vv
vv
vv
vv
))
))
))
))
)) UUUU

6666
))))))))
vv
vv
vv
vv




HH
HH
HH
HH
c1
w1
v1 y1
x1
u1
•
•
•
• •
•
• •

6666
))))))))
vv
vv
vv
vv




HH
HH
HH
HH
c2
v2 y2
x2
u2
•
•
•
• •
•
•
• •

HHHHHHHHHH
iiii

6666




HH
HH
HH
HH vvvvvvvv
))))))))
z3
c3
v3 y3
x3u3
SSS
SSS
SSS
SSS
SSS
SSS
SS
KKK
KKK
KKK
KKK
KKK
K
{{{{{{{{{{{{{{{{{{{{{{{{
SSS
SSS
SSS
SSS
SSS
SSS
SS
KKK
KKK
KKK
KKK
KKK
K
{{{{{{{{{{{{{{{{{{{{{{{{
M1 M2
Figure 3: J(3).
Claim 1. Suppose k ≥ 3 and F is a 2-factor of J(k). If, for some i with 1 < i < k, C is
a cycle in F meeting both Mi−1 and Mi, then yi−1ci and ciui+1 are both edges of C, and
V (C) ∩ V (Gi) is {ci, ui, xi} or {ci, vi, yi}.
Proof. Because F is a 2-factor, two edges incident with ci are in F . Thus, either yi−1ci
or ciui+1 (or both) is in F . Since C is the only cycle in F that meets Mi−1 ∪ Mi it
follows that ci is in C. Obtain a 2-factor Fi in Gi from F by deleting all of G1, . . . , Gi−1,
Gi+1, . . . , Gk, and adding back wi and zi, together with the edges corresponding to those
in F ∩Mi−1 as incident with wi, and likewise with zi. The cycle C now corresponds to
the 5-cycle Ci in Fi containing ci.
As Ci contains edges incident with both wi and zi, the remark preceding Theorem 2.2
shows that Ci contains exactly one of uixi and viyi. Also, both wici and cizi are in Ci and,
therefore, yi−1ci and ciui+1 are in C and V (C)∩V (Gi) is either {ci, ui, xi} or {ci, vi, yi},
as required. 4
Claim 2. If C is a cycle of a 2-factor F of J(k) that is contained in at most two Gi, then
C has length at most 16.
Proof. If C is contained in a single Gi, then obviously C has length at most 9 (which could
occur for G1 or Gk). If C meets both Gi and Gi+1, then C has length at most 16: this is
obvious if 1 < i < k − 1, while in the remaining case, C can have at most 4 vertices in
either G1 or Gk and, therefore, has length at most 12. 4
Claim 3. For k ≥ 4, `(J(k)) = 16.
84 Ars Math. Contemp. 4 (2011) 79–93
Proof. It is easy to see that `(J(k)) ≥ 16: pick the 9-cycle in G1− z1, a cycle of length 16
using only vertices from G2 and G3, and any 2-factor to cover the remainder. (If k is even,
then this can be done with two 9-cycles and (k − 2)/2 16-cycles; if k is odd, then this can
be done with one 9-cycle, (k − 3)/2 16-cycles, one 12-cycle, and one 5-cycle.)
For the reverse inequality, let C be a cycle of a 2-factor F of J(k). By Claim 2, if C
is contained in at most two consecutive Gi, then C has length at most 16. Thus, we may
assume that C meets all of Gi−1, Gi, and Gi+1. From Claim 1, we see that ci, yi−1, and
ui+1 are in C, and that C meets Gi in exactly 3 vertices.
Suppose first that neither ci−1 nor ci+1 is in C. Then Claim 1 implies C meets neither
Mi−2 or Mi+2. In this case (or if i = 2 or i = k − 1), C meets both Gi−1 and Gi+1
in precisely four vertices, as the cycles containing ci−1 and ci+1 are different from C. As
there are three vertices of Gi in C, C has exactly 11 vertices.
Suppose C contains ci−1. We claim ci+1 is not in C. To see this, observe that Claim 2
implies ci−1ui and yi−1ci are in C, as is uivi. This implies that yi is not in C, so Claim 2
implies ci+1 is not in C.
It follows that C meets Gi+1 in four vertices. Likewise, C meets Gi−2 (assuming
i ≥ 3) in four vertices, for a total length of 14. 4
Suppose n = 8k + 2 + r, for k ≥ 2 and 0 ≤ r ≤ 7. We exhibit a graph Jr(k) so that
`(Jr(k)) ≤ 16. We start with J0(k) = J(k). Observe that the same argument as above
shows that if a cycle in a 2-factor of J(k) contains exactly one of w1 or zk, then its length
is at most 12, whereas if it contains both, then it has length at most 8 (and k ≤ 3).
We get J1(k) by subdividing an edge of J(k) incident with w1. When 2 ≤ r ≤ 4,
Jr(k) is a 3-merge of J(k) at w1 with any graph in C3(r + 2).
When 5 ≤ r ≤ 7, Jr(k) is the 3-merge of Jr−4(k) at zk with K3,3. The only remaining
case is n = 17, in which case we take a 3-merge of P with any graph in C3(9) to see that
L3(17) ≤ 12.
3 Lower bound
The previous section shows that L2(n) ≤ 11. In this section, we show that L2(n) ≥ 7 for
n ≥ 12. More precisely, we prove the following.
Theorem 3.1. If G is a 2-connected near-cubic graph, then either `(G) ≥ 7 or `(G) =
|V (G)| or G is P or G is P∗.
The proof will be by induction. We start with some useful terminology and basic lem-
mas that will serve as reductions in the proof of Theorem 3.1.
We always let t be the vertex of degree 2 in G, if it exists. Given an edge e in a near-
cubic graph G, let `(G, e) denote the length of a longest cycle through e that is contained
in a 2-factor of G. The first lemma yields the base case for our induction, and will help in
many of the reductions. It can be verified by checking all small cases.
Lemma 3.2. Let n ≤ 10 and let G be a 2-connected near-cubic graph on n vertices.
1. `(G) = n, except if G = P.
2. If G is cyclically 3-connected, then, for each edge e of G, `(G, e) = `(G).
A. Kündgen and R. B. Richter: On 2-factors with long cycles in cubic graphs 85
Observe that the smallest near-cubic graph with cyclic connectivity 2 is the Hamiltonian
graph G on 7 vertices obtained from a 3-replacement of K4, but that the edge w2z2 is in
no Hamilton cycle of G. Recall (see the paragraph following the case r = 2 in the proof of
Theorem 2.1) that any (2k−1)-replacement of an edge in a cubic graph still has a 2-factor.
Lemma 3.3. If G is the (2k − 1)-replacement of the edge e in a 2-connected cubic graph
G′, then `(G) ≥ `(G′, e) + (2k − 1) when k ≥ 1. If k ≥ 2, then also `(G) ≥ `(G′).
Proof. A 2-factor in G′ that contains a cycle C through e can be extended to a 2-factor of
G by including the new vertices in C, immediately yielding the first bound. If a longest
2-factor of G′ does not use the edge e, then, when k ≥ 2, it can still be extended to a
2-factor of G by including a new cycle consisting of all the replacement vertices.
Given disjoint induced subgraphs H,K of a graph G so that V (G) = V (H) ∪ V (K),
we use [H,K] to denote the set of edges having one end in each of H and K, that is, the
(edge) cut that separates H from K. Moreover, [H,K] is a k-cut, provided that its size
|[H,K]| is k.
A k-cut [H,K] in a 2-connected near-cubic graph is cyclic if both H and K contain a
cycle; otherwise it is non-cyclic. It is easy to see that if [H,K] is a non-cyclic 2- or 3-cut,
with H not containing a cycle, then H is either a single vertex of degree |[H,K]| or H
consists of two adjacent vertices, one of which is the degree 2 vertex t of G. In general the
edges in a cyclic cut of minimum size in a near-cubic graph G form a matching.
In order to deal with 2-cuts, we need to understand their structure in more detail. Let
(u0, u1, . . . , uk) and (v0, v1, . . . , vk) be disjoint paths in G so that, for each i with 0 <
i < k, ui and vi are adjacent in G. Then the union of the two paths and the edges uivi,
i = 1, 2, . . . , k − 1 is a (u0, uk, v0, vk)-ladder in G. The two paths are the rails of the
ladder and the edges uivi are its rungs.
Let [H ′,K ′] be a 2-cut in G such that H ′ contains the degree 2 vertex t, if it exists.
If t is in a triangle, then our earlier remarks (see the paragraph following the case r = 2
in the proof of Theorem 2.1) show G is a (2k − 1)-replacement in some cubic graph, and
k ≥ 2. If G is cubic, then [9, Lemma 7.3.3.] shows there are induced subgraphs H and
K of H ′ and K ′, respectively, with distinct vertices uH , vH of H ′, not adjacent in H , and
uK , vK of K ′, not adjacent in K, and there is a (uH , uK , vH , vK)-ladder L in G so that
G = H∪L∪K. Moreover H and K have at least four vertices each. In the remaining case
that t exists and is not in a triangle, the preceding sentence applies to the graph obtained
by suppressing t, and we may restore t in H , by possibly shortening the ladder if t is in L.
The decomposition G = H ∪ L ∪K of G is a cyclic 2-cut ladder decomposition.
The graphs H(2) and K(2) are obtained from H and K, respectively by adding the edges
eH = uHvH and eK = uKvK , respectively. Observe that H(2) and K(2) are near-cubic
and 2-connected.
Lemma 3.4. Suppose G is a 2-connected near-cubic graph that has a cyclic 2-cut ladder
decomposition H ∪ L ∪K. Specifically, the vertex t, if it exists, is not in a triangle, but is
in H . Let the rails of L have length k.
1. `(G) ≥ `(H(2), eH) + `(K(2), eK) + 2k − 2.
2. `(G) ≥ `(H(2)).
86 Ars Math. Contemp. 4 (2011) 79–93
Proof. Suppose that F is a 2-factor of H(2) containing eH in the cycle C and that F ′ is a
2-factor of K(2) containing eK in the cycle C ′. Obtain a 2-factor of G from (F \ {eH}) ∪
(F ′\{eK}) by adding the rails of L. The cycle of this 2-factor of G that contains the ladder
rails has length |V (C)|+ |V (C ′)|+ 2k − 2.
For the second part, let F be a longest 2-factor of H(2). If some cycle C of F contains
eH , then consider any 2-factor of K(2) that contains eK and find a 2-factor for G as above.
Observe that the longest cycle in H(2) either remains unchanged or is extended, so we are
done.
Finally, suppose that eH is not in F . If k = 1, then let F ′ be a 2-factor of K(2) not
using eK , and now F ∪ F ′ is a 2-factor of G. If k > 1, then let F ′ be a 2-factor of K(2)
using eK in some cycle C, and convert F ′ into a 2-factor F ′′ of G − V (H) by including
the ladder vertices in C. Now F ∪ F ′′ is a 2-factor of G. In either case, the 2-factor of G
contains F and the second part follows.
The next lemma helps us to deal with cyclic 3-cuts [H,K].
Lemma 3.5. Suppose G is a 3-merge of a 2-connected near-cubic graph H(3) at vH and a
2-connected cubic graph K(3) at vK .
1. Then `(G) ≥ `(H(3)).
2. If there is a 2-factor F of H(3) so that the cycle of F through vH has length `(H(3)),
then `(G) ≥ `(H(3)) + 1.
Proof. Let F be a longest 2-factor of H(3) and suppose F does not use the edge e incident
with vH . There is a 2-factor F ′ of K(3) that does not contain the edge incident with vK
that corresponds to e. F and F ′ combine to produce a 2-factor of G, where the cycle C of
F through vH has merged with the cycle C ′ of F ′ through vK to produce a cycle of length
|V (C)| − 1 + |V (C ′)| − 1 ≥ |V (C)|+ 1; all other cycles of F remain unaffected, and the
results follow.
Lemma 3.6. Let G be a cyclically 4-connected near-cubic graph with |V (G)| ≥ 10 and a
4-cycle C = (v0, v1, v2, v3, v0). (Throughout, all indices are modulo 4.) Then:
1. G has no triangle;
2. each vertex vi in C has a distinct neighbor wi not in C;
3. for each i ∈ {1, 2}, G− {vivi+1, vi+2vi+3} is 2-connected;
4. for some i ∈ {1, 2}, suppressing the four degree 2 vertices v1, v2, v3, and v0 in
G−{vivi+1, vi+2vi+3} produces a 2-connected near-cubic graph G′ with new edges
E(G′)− E(G) = {wi+1wi+2, wi+3wi}.
5. `(G) ≥ `(G′) and if e is a new edge, then `(G) ≥ `(G′, e) + 2.
Proof. (1) Let H be the subgraph of G induced by the vertices in a triangle and let K =
G− V (H). Then [H,K] is a cyclic k-cut for some k ∈ {2, 3}, a contradiction.
(2) [C,G− V (C)] is a cyclic k-cut for some k ≤ 4. Since G is cyclically 4-connected,
k = 4 and the edges in the cut form a matching. Thus each vi has a distinct neighbor wi
not in C.
(3) Let ej = vjvj+1. Since ei and ei+2 are not both incident with t, G − {ei, ei+2} is
connected. If it is not 2-connected, then it must have a cut-edge f , and thus {ei, ei+2, f} is
A. Kündgen and R. B. Richter: On 2-factors with long cycles in cubic graphs 87
a 3-cut in G. Since G is cyclically 4-connected, this cut must be non-cyclic, contradicting
the fact that the vertices incident with ei and ei+2 are all distinct and have degree 3.
(4) Suppose the graph Gi obtained from G− {ei, ei+2} by suppressing the vertices in
C has a multiple edge. Then either wiwi+3 or wi+1wi+2 is an edge of G and, after sup-
pression, it is parallel to one of the paths (wi, vi, vi+3, wi+3) and (wi+1, vi+1, vi+2, wi+2).
If this happens for both G1 and G2, then, for some j ∈ {0, 1, 2, 3}, wj has the three
neighbours vj , wj+1 and wj−1. In this case, let H be the subgraph of G induced by
V (C) ∪ {wj , wj+1, wj−1} and let K be the subgraph of G induced by the remaining ver-
tices of G. The choice of H implies that [H,K] is a k-cut for some k ≤ 3, but since
|V (K)| ≥ 10 − 7 = 3 this cut is cyclic, a contradiction. Thus, we may assume that G1 is
a near-cubic graph. Suppressing degree 2 vertices does not decrease connectivity, so G1 is
2-connected.
(5) We assume that G1 is 2-connected and simple and let F be a 2-factor of G1. We
reconstruct a 2-factor of G in each of the three resulting cases.
If F uses neither of the new edges w0w1 and w2w3, then F ∪ {C} is a 2-factor in G.
If F uses precisely one new edge, say w0w1, then let C ′ be the cycle in F through this
edge. In this case, we get a 2-factor of G by replacing w0w1 in C ′ with (w0, v0, v3, v2,
v1, w1).
Finally, if F uses both w0w1 and w2w3, then we simply replace them with (w0, v0,
v1, w1) and (w2, v2, v3, w3), respectively.
Lemma 3.7. Let G be a cyclically 4-connected cubic graph.
1. Suppose G has a 5-cycle (v0, v1, v2, v3, v4, v0), and indices throughout are modulo
5. Then, for each i with 0 ≤ i ≤ 4, (G − vi) − vi+2vi+3 is 2-connected. If G has
no 4-cycles, then suppressing the four degree 2 vertices vi+1, vi+2, vi+3 and vi+4 in
(G− vi)− vi+2vi+3 produces a 2-connected near-cubic graph.
2. Suppose G has a 6-cycle (v0, v1, v2, v3, v4, v5, v0), and indices throughout are mod-
ulo 6. Then, for each i ∈ {0, 1}, the graph G − {vivi+1, vi+2vi+3, vi+4vi+5} is
2-connected. If G has no 4-cycles, then suppressing the six degree 2 vertices in
G− {vivi+1, vi+2vi+3, vi+4vi+5} produces a 2-connected cubic graph.
Proof. (1) Let C be the cycle (v0, v1, v2, v3, v4, v0) and let ei be the edge vivi+1. Since G
is cubic, and triangle-free by Lemma 3.6.1, each vi has a unique neighbor wi not in C.
As G is 3-connected, G − vi is 2-connected, so G − {vi, ei+2} is connected. If it
is not 2-connected, then it has a cut-edge f . Let H and K be the two components of
G − {vi, ei+2, f}. Choose the labelling of H and K so that vi has at most one neighbour
z in H . Consider the cut [H,K + vi] in G. Then [H,K + vi] ⊆ {ei+2, viz, f}; since G is
cubic and cyclically 4-connected, equality holds and all 3 edges must be incident with the
same vertex. Since vi is not incident with ei+2 this vertex can only be z, so that viz is a
chord of C, contradicting the fact that G is triangle-free.
Finally, if G has no 4-cycles, for each i = 0, 1, 2, 3, 4, the wi are distinct and there is
no edge of G joining wi and wi+1, which shows suppressing the four degree 2 vertices in
G− {vi, ei+2} results in a near-cubic 2-connected graph, with degree 2 vertex wi.
(2) Let C be the cycle (v0, v1, v2, v3, v4, v5, v0) and let ei be the edge vivi+1.
As G is 3-connected, if G − {ei, ei+2, ei+4} is not connected, then there is a 3-cut
[H,K] so that [H,K] = {ei, ei+2, ei+4}. As G has no cyclic 3-cuts, one of H and K is a
88 Ars Math. Contemp. 4 (2011) 79–93
single vertex. However, the edges ei, ei+2, and ei+4 have no incident vertex in common, a
contradiction. Thus, G− {ei, ei+2, ei+4} is connected.
If G− {ei, ei+2, ei+4} has a cut-edge e, then G− {e, ei, ei+2, ei+4} has precisely two
(cyclic) components H and K, and [H,K] = {e, ei, ei+2, ei+4}. Since G is cyclically
4-connected, the edges in this 4-cut form a matching. It follows that the edges ei+1, ei+3
and ei+5 are in G− [H,K] and so at least two of them are in the same one of H and K, say
ei+1 and ei+3 are in H . But this is impossible, as ei+1 and ei+3 are incident with different
ends of ei+2 and one of these is in K. Thus, G− {ei, ei+2, ei+4} is 2-connected.
If G has no 3- or 4-cycles, then C is an induced cycle and we let wj be the neighbour of
vj not in C. Then wj and wj+1 are distinct and not adjacent in G. This is enough to con-
clude that the paths (wj , vj , vj+1, wj+1) do not become multiple edges after suppressing
the vertices in C from G − {ei, ei+2, ei+4}, and hence the resulting graph is 2-connected
and cubic.
Let C be a cycle in a graph G. A partial 2-factor of G with respect to C is a 2-regular
subgraph F of G such that V (G)− V (F ) ⊆ V (C), and E(F ) ∩ E(C) is a matching.
Lemma 3.8. Suppose a near-cubic 2-connected graph G has a partial 2-factor F with
respect to a cycle C. Let |E(C) ∩ E(F )| = k and let s be the number of vertices in the
subgraph induced by C and the cycles in F that meet C. If some longest cycle in F misses
V (C) (for example when k = 0) or |V (C)| = 2k, then `(G) ≥ `(F ). If k > 0, then
`(G) ≥ s/k.
Proof. If |V (C)| = 2k, then F is a 2-factor of G, and the result is obvious. Otherwise
|V (C)| > 2k and we consider F ′ such that E(F ′) is the symmetric difference of E(F )
and E(C): in F ′ each vertex in V (F ) − V (C) is incident with 2 edges from F and each
vertex in V (C)−V (F ) is incident with 2 edges from C; each vertex in V (C)∩V (F ) must
be incident with exactly one edge from E(C) ∩E(F ) (since these form a matching and G
is near-cubic). It follows that F ′ is a 2-factor of G. When k = 0, F ′ = F ∪ {C} and thus
`(G) ≥ `(F ′) ≥ `(F ).
When k > 0, let C1, C2, . . . , Cr be the cycles of F that meet C and let G′ = C ∪C1∪
C2 ∪ · · · ∪ Cr. Then G′ is a 2-connected sub-cubic graph on s vertices with exactly 2k
vertices of degree 3. Observe that F ′′ = F ′ ∩ V (G′) = G′ − (E(C)∩E(F )) is a 2-factor
of G′. Since G′ is 2-connected each component of F ′′ has at least 2 vertices of degree 3
in G′, and thus F ′′ has at most k components. Thus one of the cycles in F ′′ has length at
least s/k, and hence `(G) ≥ `(F ′) ≥ `(F ′′) ≥ s/k.
We are now ready for the proof of the main result of this section. A 2-factor F in a
graph G has a long cycle if one of the components of F has length at least 7.
Proof of Theorem 3.1. We proceed by induction, with the base cases |V (G)| ≤ 10 covered
by Lemma 3.2. For the induction step, we may suppose |V (G)| ≥ 11. Let t be the degree
2 vertex, if G has one.
Claim 1. If t is in a triangle of G, then `(G) ≥ 7.
Proof. There is a k ≥ 2 so that G is a (2k−1)-replacement of some edge e in a 2-connected
cubic graph G′. By Lemma 3.3, `(G) ≥ `(G′), so the result follows unless G′ either is
P or has at most 6 vertices. In these cases, Lemma 3.2 implies `(G′, e) = `(G′) ≥ 4, so
Lemma 3.3 implies `(G) ≥ `(G′, e) + (2k − 1) ≥ 4 + 3 = 7. 4
A. Kündgen and R. B. Richter: On 2-factors with long cycles in cubic graphs 89
Claim 2. If G has a cyclic 2-cut, then `(G) ≥ 7.
Proof. From Claim 1, we may assume that either G is cubic, or obtained by subdividing
an edge of a cubic graph.
Since G has a cyclic 2-cut, there are disjoint subgraphs H and K of G and a ladder L
so that G = H ∪ L ∪ K, and t, if it exists, is in H . If `(H(2)) ≥ 7, then Lemma 3.4.2
shows that `(G) ≥ 7, as required. Thus, we may assume `(H(2)) < 7.
We know that H(2) is either P or P∗, or has at most 6 vertices. In any of these cases
Lemma 3.2 implies that `(H(2), eH) = `(H(2)) ≥ 4. Thus Lemma 3.4.1 implies `(G) ≥
`(H(2), eH) + `(K(2), eK) + 2k − 2 ≥ 4 + 3 + 0 = 7. 4
Claim 3. If G is not cyclically 4-connected, then `(G) ≥ 7.
Proof. From Claims 1 and 2, we may assume G is cyclically 3-connected. Since G is not
cyclically 4-connected, G has a cyclic 3-cut [H,K], with the labelling chosen so that t, if it
exists, is in H . Since [H,K] is a minimum size cyclic cut it must be a matching, and thus
the graph H(3) obtained from H by adding a new degree 3 vertex vH adjacent to the vertices
in H that are incident with edges in [H,K] is simple near-cubic and 2-connected. Similarly
the graph K(3) obtained from K by introducing a new vertex vK is cubic 2-connected, and
G is the 3-merge of H(3) and K(3).
If `(H(3)) ≥ 7, then Lemma 3.5.1 implies that `(G) ≥ 7, as required. Thus, we may
assume `(H(3)) < 7. If H(3) is either P∗, or has 6 vertices, then Lemma 3.5.2 implies (in
the case of P∗ because any vertex and any edge of P are in a 5-cycle in P) `(G) ≥ 6+1 = 7.
Thus, H(3) is P, K4 or K∗4 . If H(3) is cubic, then the roles of H and K can be reversed, so
that K(3) must also be K4 or P. So, since |V (G)| ≥ 11, it follows that G is the 3-merge of
P and either K4 or P, whence `(G) ≥ 9. Hence it remains to consider the case H(3) = K∗4 .
In this case, let u1, u2, u3 be the neighbors of vH in H(3), and let v1, v2, v3 be their
corresponding neighbors in K. Suppose the neighbors of vH in a Hamilton cycle D in
H(3) are ui, uj . Let Fk be a 2-factor of K(3) avoiding vKvk, where k ∈ {1, 2, 3} \ {i, j}
and let Ck be the cycle of Fk through vK . Then Fk − Ck together with the cycle C =
(D − vH) ∪ (Ck − vK) ∪ {uivi, ujvj} is a 2-factor of G. As long as Ck has length at
least 4, C has length at least 7. Thus, we may assume Ck is the 3-cycle (vK , vi, vj , vK). In
particular, vivj is an edge of G.
However H(3) has two different Hamilton cycles D, so we can assume that, say v1v2
and v2v3 are edges of G. There are at least three cubic vertices of G not in H∪{v1, v2, v3},
so the 2-cut [H∪{v1, v2, v3},K−{v1, v2, v3}] is cyclic, contradicting the assumption that
G is cyclically 3-connected. 4
From now on we may assume that G is cyclically 4-connected. In particular, G is
triangle-free by Lemma 3.6.1.
Claim 4. If G has a 4-cycle, then `(G) ≥ 7.
Proof. Let C be a 4-cycle (v0, v1, v2, v3, v0) in G. Since G is cyclically 4-connected,
Lemma 3.6.2 implies that, for every i ∈ {0, 1, 2, 3}, vi has a unique neighbor wi not in C.
Note that, for i = 0, 1, 2, 3, wi 6= wi+1 (indices being read modulo 4). By Lemma 3.6.4,
for some i ∈ {0, 1}, the result of suppressing the four degree 2 vertices v0, v1, v2, and v3
in G− {vivi+1, vi+2vi+3} is a 2-connected graph G′.
90 Ars Math. Contemp. 4 (2011) 79–93
Obviously |V (G′)| = |V (G)| − 4 ≥ 7. If `(G′) ≥ 7, then the result follows from the
first part of Lemma 3.6.5. Otherwise G′ is P or P∗, and Lemmas 3.2.2 and 3.6.5 imply
`(G) ≥ `(G′) + 2 ≥ 7. 4
Perhaps surprisingly, we next treat two cases in which G has a 6-cycle. Because there
are no 3- or 4-cycles, any 6-cycle is induced.
Claim 5. If there is a 6-cycle C in G containing t, then G = P∗ or `(G) ≥ 7.
Proof. Let C = (v0, v1, v2, v3, v4, v5, v0), with the labelling chosen so that v0 = t. For
1 ≤ i ≤ 5, let wi be the neighbour of vi not in C. Since G has no 3- or 4-cycles, if
wi = wj , then either i = j or i = j ± 3. Furthermore, we cannot have both w1 = w4
and w2 = w5, as then there is a cyclic 3-cut with V (H) = V (C) ∪ {w1, w2}. So we may
assume w2 6= w5. Also, for i = 1, 2, 3, 4, wi and wi+1 are not adjacent in G.
Let G′′ = G− {v0, v3}. Suppressing v0 in G produces a graph to which Lemma 3.7.1
applies, showing G′′ is 2-connected. Furthermore, suppressing the four degree 2 vertices
v1, v2, v4, v5 in G′′ yields a 2-connected near-cubic graph G′ (since consecutive wi’s are
not adjacent) with degree 2 vertex w3.
We note that |V (G′)| = |V (G)| − 6 ≥ 5. As G′ is not cubic, by induction either
G′ = K∗4 or G
′ = P∗ or `(G′) ≥ 7.
Suppose first that |V (G′)| = 5. If w1 6= w4, then the five vertices of G′ are w1, w2,
w3, w4, and w5. As w3 is the degree 2 vertex and w3 is not adjacent to either w2 or w4, the
edges in G − V (C) must be w3w5, w3w1, w4w2, w4w1 and w2w5, and thus G = P∗. If
w1 = w4, then neither w1 = w4 nor w2 is adjacent to w3 in G′. Thus, the neighbors of w3
are w5 and some other vertex x. But then w4 = w1 is adjacent to w5 in G, a contradiction.
In the remaining case, either G′ = P∗ or `(G′) ≥ 7. If the latter, then let F ′ be any
longest 2-factor of G′. If G′ = P∗, then we claim there is a 2-factor F ′ of G′ with a cycle
C ′ through exactly one of w4w5 and w1w2. Indeed, if w1 = w4, then observe that any F ′
containing the third edge incident with w1 will avoid exactly one of these edges altogether.
If w1 6= w4, then w1w2 and w4w5 are not incident with the same vertex of G′ and so it
is possible either to find a 6-cycle containing exactly one of these and w3, or a 5-cycle
containing only one of these together with a 6-cycle containing w3.
Expanding F ′ back to G, we obtain a partial 2-factor F of G with respect to C. Set
k = |E(C) ∩E(F )| and let s be the number of vertices in the subgraph induced by C and
the cycles in F that meet C. Then k = 1 when G′ = P∗. By Lemma 3.8, `(G) ≥ `(F ) ≥
`(F ′) ≥ 7, unless 1 ≤ k ≤ 2 and a longest cycle C ′ of F ′ contains a new edge. Since
s ≥ |V (C)|+ |V (C ′)|, it follows that, for `(G′) ≥ 7, we obtain `(G) ≥ (6+ 7)/k > 6, as
desired. If G′ = P∗, then `(G) ≥ (6 + 5)/1 = 11. 4
Claim 6. If G is cubic and has a 6-cycle, then `(G) ≥ 7.
Proof. Let C be the 6-cycle (v0, v1, v2, v3, v4, v5, v0) in G. Note that each vi has a neigh-
bour wi not in C. For 0 ≤ i ≤ 5, let ei be the edge vivi+1 (all indices being read modulo 6).
Let G′ be the graph obtained from G−{e1, e3, e5} by suppressing the 6 vertices in C which
are now of degree 2. By Lemma 3.7.2, G′ is 2-connected and cubic, in particular, G′ 6= P∗.
As G is cubic and |V (G)| ≥ 11, we see that |V (G)| ≥ 12 and |V (G′)| = |V (G)| − 6 ≥ 6.
It is important to note that, since G has no 3- or 4-cycles, if i and j are distinct and wi = wj ,
A. Kündgen and R. B. Richter: On 2-factors with long cycles in cubic graphs 91
then j = i+3. Thus, the three new edges w0w1, w2w3, w4w5 can’t all be incident with the
same vertex in G′.
If `(G′) ≥ 7, then let F ′ be a 2-factor of G′ having a cycle of length `(G′). If `(G′) ≤
6, then G′ is one of K3,3, K3K2 or P. When G′ is P, F ′ may be chosen to contain exactly
one or two new edges, and no more than one in each component. Since w0w1, w2w3, w4w5
don’t have a common vertex, when G′ = K3,3, we can let F ′ be a 6-cycle containing all
three of them.
When G′ = K3K2 we observe that, since G is triangle-free, each of the triangles in
G′ must contain one of the new edges. However, no triangle can contain two new edges, say
w0w1 and w2w3, since then w0 = w3, making w1 and w2 adjacent. Up to symmetry, there
are two ways to pick one edge from each triangle. In both cases, there is (up to symmetry)
only one way to choose the third edge not from the triangles to also eliminate all 4-cycles.
In either case, we can let F ′ be a 6-cycle containing all 3 new edges.
Expanding F ′ back to G, we obtain a partial 2-factor F of G with respect to C. Set
k = |E(C) ∩ E(F )| and let s be the number of vertices in the subgraph induced by C
and the cycles in F that meet C. If |V (G′)| = 6, then |V (C)| = 6 = 2k and F consists
of one cycle, so `(G) ≥ `(F ) = 12. If G′ = P, then either k = 1 and s = 6 + 5, or
k = 2 and s = 6 + 10, and in either case `(G) ≥ 8. If `(G′) ≥ 7, then, by Lemma 3.8,
`(G) ≥ `(F ) ≥ `(F ′) ≥ 7, unless 1 ≤ k ≤ 2 and a longest cycle C ′ of F ′ contains a new
edge. Since s ≥ |V (C)|+ |V (C ′)| ≥ 6 + 7, we get `(G) ≥ 13/k > 6, as desired. 4
The next two claims will now complete the proof.
Claim 7. If G has a vertex of degree 2, then G = P∗ or `(G) ≥ 7.
Proof. If the vertex t of degree 2 in G is not in a 5- or 6-cycle in G, then any 2-factor
F of G suffices, as the cycle of F through t is long. If t is in a 6-cycle, then Claim 5
shows either G = P∗ or `(G) ≥ 7. The remaining case is that t is in a 5-cycle C =
(v0, v1, v2, v3, v4, v0), with the labelling chosen so that v0 = t. For 1 ≤ i ≤ 4, let wi be
the neighbour of vi not in C. As G has no 3- or 4-cycles, these four wi are distinct.
Contracting v0v1 to apply Lemma 3.6.3, we deduce that the graph (G − v0) − v2v3 is
2-connected. As G has no 4-cycles, suppressing the four vertices v1, v2, v3, v4 of degree 2
in (G − v0) − v2v3 results in a graph G′ with new edges w1w2 and w3w4. Obviously, G′
is 2-connected and cubic and |V (G′)| = |V (G)| − 5 ≥ 6. If G′ = K3,3, then G′ contains
a 4-cycle avoiding the new edges, which is thus a 4-cycle in G, a contradiction. Similarly,
if G′ = K3K2, then G′ contains either a 3-cycle or a 4-cycle without a new edge, a
contradiction. Thus |V (G′)| ≥ 8, so by induction G′ = P or `(G′) ≥ 7.
If G′ is P, then it has a 2-factor F ′ that contains exactly one of the two new edges w1w2
and w3w4. If `(G′) ≥ 7, we let F ′ be any longest 2-factor of G′.
Expanding F ′ back to G, we obtain a partial 2-factor F of G with respect to C. Set
k = |E(C) ∩ E(F )| and let s be the number of vertices in the subgraph induced by C
and the cycles in F that meet C. Then k = 1 when G′ = P. By Lemma 3.8, `(G) ≥
`(F ) ≥ `(F ′) ≥ 7, unless 1 ≤ k ≤ 2 and a longest cycle C ′ of F ′ contains a new edge.
Since s ≥ |V (C)| + |V (C ′)| it follows that for `(G′) ≥ 7 we obtain `(G) ≥ 12/k ≥ 6,
but observe that equality can only hold if k = 2 and V (C) ∪ V (C ′) yields two 6-cycles.
One of these 6-cycles contains v0 = t, and the result follows by Claim 5. If G′ = P, then
`(G) ≥ (5 + 5)/1 = 10. 4
92 Ars Math. Contemp. 4 (2011) 79–93
Claim 8. If G is cubic, then `(G) ≥ 7.
Proof. Again, we may assume G is cyclically 4-connected and has no 3- or 4-cycles.
Claim 6 allows us to assume that G has no 6-cycles. We may further assume (v0, v1, v2, v3,
v4, v0) is a 5-cycle C in G, as otherwise we are done: every 2-factor has a long cycle.
Let wi be the neighbour of vi that is not in C, and let W = {w0, w1, w2, w3, w4}. As G
has no 3- or 4-cycles, the vertices v0, v1, . . . , v4, w0, w1, . . . , w4 are distinct. Furthermore,
the vertices in W are pairwise non-adjacent, since G has no 4- or 6-cycles.
Now let G′ be obtained from (G− v0)− v2v3 by suppressing the four vertices v1, v2,
v3, v4 of degree 2. By Lemma 3.7.1, G′ is a 2-connected near-cubic graph with degree 2
vertex w0. Clearly |V (G′)| ≥ 6, so by induction either G′ = P∗ or `(G′) ≥ 7. There are
four different 6-cycles through w0 in P∗; no set of two edges not incident with either w0 or
its neighbors meets all four of these. Thus, if G′ = P∗, then we can find a 6-cycle of G′
containing w0 that avoids w1w2 and w3w4. This is a 6-cycle in G, contradicting the fact
that G has no 6-cycles. Therefore G′ 6= P∗, and it remains to consider `(G′) ≥ 7.
Let F ′ be a longest 2-factor of G′. Expanding F ′ back to G, we obtain a partial 2-
factor F of G with respect to C. Set k = |E(C) ∩ E(F )| and let s be the number of
vertices in the subgraph induced by C and the cycles in F that meet C. By Lemma 3.8,
`(G) ≥ `(F ) ≥ `(F ′) ≥ 7, unless 1 ≤ k ≤ 2 and a longest cycle C ′ of F ′ contains a new
edge. Since s ≥ |V (C)|+ |V (C ′)| ≥ 5 + 7 we obtain `(G) ≥ 12/k ≥ 6, but observe that
equality can only hold if G contains a 6-cycle, in which case Claim 6 finishes the proof. 4
Obviously Theorem 3.1 follows from Claims 7 and 8. 2
4 Infinite Graphs
In this section, we indicate the connections to 2-factors in infinite cubic graphs. The graphs
J(k) from Section 2 have a natural limit version J(∞) (let k go to infinity). This graph is
3-connected, 1-ended, and cubic and every 2-factor in J(∞) contains only cycles of length
at most 16.
In a slightly different direction, we show how to construct a 3-connected, 1-ended,
cubic graph so that every 2-factor is a 2-way infinite Hamilton path. The construction starts
by noting that the edges of P partitions into five sets of three edges each with the property
that every 2-factor of P contains precisely two edges from each of the five sets, and these
two edges are in different components of the 2-factor.
Let P+ be the 3-connected cubic graph obtained from P by subdividing the three edges
in one of the five sets and then adding a new vertex n adjacent to the three vertices of
subdivision. Let u be any vertex of P not incident with any of the three original edges.
The key properties of P+, easily proved from properties of P, are: its only 2-factors are
Hamilton cycles; and P+ − n has no 2-factor.
Let G1, G2, . . . be disjoint copies of P+, with ni and ui being the copies of n and u,
respectively, in Gi. Iteratively 3-merge the Gi, starting with G1 at n1 and G2 at u2. Then
this new graph is 3-merged, at n2, with G3 at u3, and so on. The infinite graph thus created
is easily seen to have 2-way infinite Hamilton paths as its only 2-factors.
5 Open Questions
Several open questions naturally arise. We mention only a few here.
A. Kündgen and R. B. Richter: On 2-factors with long cycles in cubic graphs 93
Naturally, we wonder what the exact values of L2(n) and L3(n) are and we conjecture
that Lk(n) is unbounded for sufficiently large k. This can be viewed as a weaker version
of the following unpublished question Thomassen first asked in the 1970’s: Is every graph
in Ck(n) Hamiltonian when k is sufficiently large?
Kochol (personal communication, based on [4, 5]) has examples of cyclically 6-con-
nected cubic graphs on 2n vertices for which every 2-factor has cn components, for some
c > 0. Of course this does not imply that L6(n) is bounded.
On the other hand, Fleischner [1] conjectures that every cyclically 4-connected Class
2 graph has a dominating cycle. This might suggest that there is always a 2-factor with a
long cycle for cyclically 4-connected cubic graphs.
Two other natural questions are: what is the average value of `(G) over all graphs in
either C2(n) or C3(n)? and what is `(R), where R is the random cubic graph?
6 Acknowledgements
We would like to thank Ron Gould, Martin Kochol and Carsten Thomassen for useful
discussions regarding this paper. We are also grateful to the referees for their helpful com-
ments.
References
[1] H. Fleischner, Cycle decompositions, 2-coverings, removable cycles, and the four-color-disease,
Progress in graph theory, Waterloo, Ont., 1982, 233–246, Academic Press, Toronto, ON, 1984.
[2] D. A. Holton and J. Sheehan, The Petersen Graph, Australian Mathematical Society Lecture
Series, 7, Cambridge University Press, Cambridge, 1993.
[3] B. Jackson and K. Yoshimoto, Spanning even subgraphs of 3-edge-connected graphs, J. Graph
Theory 62 (2009), 37–47.
[4] M. Kochol, Superposition and constructions of graphs without nowhere-zero k-flows, Europ. J.
Combin. 23 (2002), 281–306.
[5] M. Kochol, Equivalences between hamiltonicity and flow conjectures, and the sublinear defect
property, Discrete Math. 254 (2002), 221–230.
[6] J. Petersen, Die Theorie der regulären Graphen, Acta Math. 15 (1891), 193–220.
[7] T. Schönberger, Ein Beweis des Petersenschen Graphensatzes, Acta Scientia Mathematica
Szeged 7 (1934), 51–57.
[8] W. T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952), 314–328.
[9] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, Upper Saddle River, NJ, 2001.