# All longest cycles intersect in partial 3-trees

Juan Gutiérrez1
1Departamento de Ciencia de la Computación
Universidade de Ingeniería y Tecnología, Perú ††A previous version of this
paper was supported by FAPESP (Proc. 2015/08538-5). E-mail:
<EMAIL_ADDRESS>
###### Abstract

We show that all longest cycles intersect in 2-connected partial 3-trees.

##  1 Introduction

It is known that, in a 2-connected graph, every pair of longest cycles
intersect each other in at least two vertices. A natural question is whether
all longest cycles have a vertex in common in 2-connected graphs (if the graph
is not 2-connected, two longest cycles can be disjoint). This has in general a
negative answer, as the Petersen’s graph shows. However, there are some graph
classes for which this question has a positive answer, such as dually chordal
graphs [10] (a class of graphs that includes doubly chordal, strongly chordal,
and interval graphs) and 3-trees [6]. In this paper, we generalize the later
result by showing that all longest cycles intersect in 2-connected graphs with
treewidth at most 3, also known as partial 3-trees. A previous extended
abstract containing this result was presented at LATIN 2018 [8]. A similar
question for paths instead of cycles has been approached in [3].

This paper is organized as follows. In Section 2, we establish basic concepts
on paths and cycles. In Section 3, we give definitions on tree decompositions
and branches. In Section 4, we state the main lemma (Lemma 4.1) and proceed to
the proof of the main result (Theorem 4.2). The other two sections contain the
most technical parts of the proof. Section 5 contains the proof of the main
lemma, using auxiliary results proved in the Section 6. Finally, in Section 7
we present some concluding remarks. In this paper, all graphs considered are
simple and the notation used is standard [2, 5].

##  2 Paths and Cycles

Given paths $C^{\prime}$ and $C^{\prime\prime}$, if $(V(C^{\prime})\cup
V(C^{\prime\prime}),E(C^{\prime})\cup E(C^{\prime\prime}))$ is a path or a
cycle, it is denoted by $C^{\prime}\cdot C^{\prime\prime}$. For a vertex $v$
in a path $P$, let $P^{\prime}$ and $P^{\prime\prime}$ be the paths such that
$P=P^{\prime}\cdot P^{\prime\prime}$ with $V(P^{\prime})\cap
V(P^{\prime\prime})=\\{v\\}$. We refer to these two paths as the _$v$ -tails_
of $P$. For a pair of vertices $\\{a,b\\}$ in a cycle $C$, let $C^{\prime}$
and $C^{\prime\prime}$ be the paths such that $C=C^{\prime}\cdot
C^{\prime\prime}$ and $V(C^{\prime})\cap V(C^{\prime\prime})=\\{a,b\\}$. We
refer to these paths as the _$ab$ -parts_ of $C$. Moreover, we can extend this
notation and define, for a triple of vertices $\\{a,b,c\\}$ in a cycle $C$,
the _$abc$ -parts_ of $C$; and, when the context is clear, we denote by
$C_{ab}$, $C_{bc}$, and $C_{ac}$ the corresponding $abc$-parts of $C$. A
similar notation is used to define the the _$abcd$ -parts_ of $C$ for a given
subset of four vertices $\\{a,b,c,d\\}$ in $C$.

Let $G$ be a graph and let $S\subseteq V(G)$. We say that $S$ _separates_
vertices $u$ and $v$ if $u$ and $v$ are in different components of $G-S$. Let
$X\subseteq V(G)$. We say that $S$ separates $X$ if $S$ separates at least two
vertices of $X$.

We say that a path or cycle $C^{\prime}$ _$k$ -intersects_ $S$ if
${|V(C^{\prime})\cap S|=k}$. Moreover, we also say that $C^{\prime}$
$k$-intersects $S$ at $V(C^{\prime})\cap S$. A path or cycle $C^{\prime}$
_crosses_ $S$ if $S$ separates $V(C^{\prime})$ in $G$. Otherwise, $S$ _fences_
$C^{\prime}$. If $C^{\prime}$ crosses $S$ and $k$-intersects $S$, then we say
that $C^{\prime}$ $k$-_crosses_ $S$. We also say that $C^{\prime}$ $k$-crosses
$S$ at $V(C^{\prime})\cap S$. If $C^{\prime}$ is fenced by $S$ and
$k$-intersects $S$, then we say that $C^{\prime}$ is $k$-_fenced_ by $S$. Two
cycles are $S$-equivalent if they intersect $S$ at the same set of vertices.
(Figure 1). 222The terms fenced and crossing were first coined at [4].

$c$$d$$b$$v_{1}$$v_{2}$$v_{3}$$a$$v_{4}$$v_{5}$

(a)

$c$$d$$b$$v_{1}$$v_{2}$$v_{3}$$a$$v_{4}$$v_{5}$

(b)

Figure 1: (a) A graph $G$ with $S=\\{a,b,c,d\\}$. (b) Consider paths
$P_{1}=v_{1}av_{5}$ and $P_{2}=v_{3}cdbv_{4}$, and cycles
$C_{1}=v_{1}bv_{2}dv_{1}$ and $C_{2}=v_{3}v_{4}cabv_{3}$. Then $P_{1}$ and
$C_{1}$ cross $S$, and $P_{2}$ and $C_{2}$ are fenced by $S$. Moreover,
$P_{1}$ 1-crosses $S$, $P_{2}$ is $3$-fenced by $S$, $C_{1}$ 2-crosses $S$ and
$C_{2}$ is 3-fenced by $S$. (Also note that path $cd$ and cycle $abda$ are
fenced by $S$.) Paths $P_{2}$ and $v_{1}bcdv_{2}$ are $S$-equivalent. Cycles
$C_{2}$ and $v_{1}bcv_{5}av_{1}$ are $S$-equivalent.

A cycle in a graph $G$ is called a _longest cycle_ if it has maximum length
over all cycles in $G$. Let $S\subseteq V(G)$. The next proposition is well
known. We use it several times through the text without making any reference
to it.

######  Proposition 2.1.

Let $C$ and $D$ be a pair of longest cycles in a 2-connected graph $G$. Then
${|V(C)\cap V(D)|\geq 2}$.

##  3 Tree Decomposition and Branches

A _tree decomposition_ [5, p. 337] of a graph $G$ is a pair $(T,\mathcal{V})$,
consisting of a tree $T$ and a collection $\mathcal{V}=\\{V_{t}:t\in V(T)\\}$
of (different) _bags_ $V_{t}\subseteq V(G)$, that satisfies the following
three conditions:

  * •

$\bigcup_{t\in V(T)}V_{t}=V(G);$

  * •

for every $uv\in E(G)$, there exists a bag $V_{t}$ such that $u,v\in V_{t};$

  * •

if a vertex $v$ is in two different bags $V_{t_{1}},V_{t_{2}}$, then $v$ is
also in any bag $V_{t}$ such that $t$ is on the (unique) path from $t_{1}$ to
$t_{2}$ in $T$.

The _treewidth_ $tw(G)$ is the number $\min\\{\max\\{|V_{t}|-1:t\in
V(T)\\}:(T,\mathcal{V})$ is a tree decomposition of $G\\}$. We refer to the
vertices of $T$ as _nodes_.

If $G$ is a graph with treewidth $k$, then we say that $(T,\mathcal{V})$ is a
_full tree decomposition_ of $G$ if $|V_{t}|=k+1$ for every $t\in V(T)$, and
$|V_{t}\cap V_{t^{\prime}}|=k$ for every $tt^{\prime}\in E(T)$.

######  Proposition 3.1 ([1, Lemma 8][7, Theorem 2.6]).

Every graph has a full tree decomposition.

Let $G$ be a graph and $(T,\mathcal{V})$ be a tree decomposition of $G$. Given
two different nodes $t,t^{\prime}\in V(T)$, we denote by
$\mathrm{Br}_{t}(t^{\prime})$ the component of $T-t$ where $t^{\prime}$ lies.
We say that such component is a _branch_ of $T$ at $t$ and that the components
of $T-t$ are the _branches_ of $T$ at $t$ [9]. Similarly, for a vertex
${v\notin V_{t}}$, it is denoted by $\mathrm{Br}_{t}(v)$ the branch
$\mathrm{Br}_{t}(t^{\prime})$ of $T$ at $t$ such that $v\in V_{t^{\prime}}$.
In that case, we also say that ${v\in\mathrm{Br}_{t}(t^{\prime})}$ or that $v$
is _in_ $\mathrm{Br}_{t}(t^{\prime})$.

Let $t\in V(T)$. Let $C^{\prime}$ be a path or cycle in $G$ fenced by $V_{t}$.
It is easy to see that, for every $u,v\in V(C^{\prime})$, we have
$\mathrm{Br}_{t}(u)=\mathrm{Br}_{t}(v)$. Hence, when
$V(C^{\prime})\not\subseteq V_{t}$, we say that
$\mathrm{Br}_{t}(C^{\prime})=\mathrm{Br}_{t}(v)$. And, if
$V(C^{\prime})\subseteq V_{t}$, we say that
$\mathrm{Br}_{t}(C^{\prime})=(\emptyset,\emptyset)$, that is, a subtree of $T$
with empty set of nodes and edges.

The next proposition relates the concepts of separation and branches.

######  Proposition 3.2 ([5, Lemma 12.3.1]).

Let $tt^{\prime}\in E(T)$. Let $u,v\in V(G)$ be such that ${u\notin V_{t}}$
and ${v\notin V_{t^{\prime}}}$. If $u\in\mathrm{Br}_{t}(t^{\prime})$ and
$v\in\mathrm{Br}_{t^{\prime}}(t)$, then $V_{t}\cap V_{t^{\prime}}$ separates
$u$ and $v$.

A $k$-_clique_ in a graph is a set of $k$ pairwise adjacent vertices. A
$k$-_tree_ is defined recursively as follows. The complete graph on $k$
vertices is a $k$-tree. Any graph obtained from a $k$-tree by adding a new
vertex and making it adjacent to exactly all the vertices of an existing
$k$-clique is also a $k$-tree. A graph $G$ is a _partial_ $k$-_tree_ if and
only if $G$ is the subgraph of a $k$-tree. Partial $k$-trees are closely
related to the definition of tree decomposition. In fact, a graph $G$ is a
partial $k$-tree if and only if ${\mathrm{tw}(G)\leq k}$ [1, Theorem 35].

In what follows, we fix a 2-connected partial 3-tree $G$ such that
$\mathrm{tw}(G)=3$, and a full tree decomposition $(T,\mathcal{V})$ of $G$.

For every $t\in V(T)$, and for every triple of vertices $\Delta$ in $V_{t}$,
it is denoted by ${\mathscr{B}\\!}_{t}(\Delta)$ the union of the branches of
the neighbors of $t$ in $T$ such that the corresponding bag contains $\Delta$.
That is,

${\mathscr{B}\\!}_{t}(\Delta)=\bigcup\\{\mathrm{Br}_{t}(t^{\prime}):tt^{\prime}\in
E(T)\mbox{ and }\Delta\subseteq V_{t^{\prime}}\\}.$

For a vertex $v\in V(G)$, we say that $v$ is $t$-_inside_ $\Delta$ if $v\in
V_{t^{\prime}}$ for some $t^{\prime}\in V(T)$ with
$\mathrm{Br}_{t}(t^{\prime})\subseteq{\mathscr{B}\\!}_{t}(\Delta)$. Otherwise,
we say that $v$ is $t$-_outside_ $\Delta$. When the context is clear, we just
say that $v$ is inside or outside $\Delta$ (Figure 2).

Figure 2: A partial 3-tree of treewidth 3 and a corresponding full tree
decomposition. The dashed lines imply that there is no edge between the
corresponding vertices. If $t$ is the node with
$V_{t}=\\{v_{2},v_{3},v_{4},v_{5}\\}$ and $\Delta=\\{v_{2},v_{4},v_{5}\\}$,
then the vertices $v_{2},v_{4},v_{5},v_{8},v_{9},v_{10},v_{11},v_{12}$ are
$t$-inside $\Delta$ and all the other vertices are $t$-outside $\Delta$. Also,
the cycles $v_{2}v_{5}v_{8}v_{2}$ and $v_{4}v_{12}v_{5}v_{11}v_{4}$ are
$t$-inside $\Delta$, the cycle $v_{5}v_{7}v_{3}v_{4}v_{6}v_{5}$ is $t$-outside
$\Delta$, and the cycles $v_{2}v_{5}v_{14}v_{2}$ and
$v_{3}v_{4}v_{11}v_{5}v_{6}v_{3}$ $t$-jump $\Delta$.

Given a path $C^{\prime}$ that 2-intersects $\Delta$ at the extremes of
$C^{\prime}$, we say that $C^{\prime}$ is $t$-_inside_ $\Delta$ if every
vertex of $C^{\prime}$ is $t$-inside $\Delta$, and $C^{\prime}$ is
$t$-_outside_ $\Delta$ otherwise. Given a cycle $C$ that intersects $\Delta$
at least twice, we say that $C$ is $t$-_inside_ $\Delta$ if every
$\Delta$-part of $C$ is $t$-_inside_ $\Delta$, $C$ is $t$-_outside_ $\Delta$
if every $\Delta$-part of $C$ is $t$-_outside_ $\Delta$, and $C$ $t$-_jumps_
$\Delta$ if $C$ has a $\Delta$-part $t$-inside $\Delta$ and a $\Delta$-part
$t$-outside $\Delta$.

Again, if the context is clear, we just say that $C$ is inside, outside, or
_jumps_ $\Delta$ (Figure 2). Furthermore, we abuse notation and, when the
context is clear, for a cycle $C$ that jumps $\Delta$, we say that $C$
$\ell$-jumps $\Delta$ if $|V(C)\cap\Delta|=\ell$. Observe that
$\ell\in\\{2,3\\}$. Moreover, if $C$ $\ell$-jumps $\Delta$, we say that $C$
$\ell$-jumps $\Delta$ at $V(C)\cap\Delta$. Throughout this chapter, we
abbreviate a triple of vertices $\\{a,b,c\\}$ by $abc$.

##  4 Proof of the main theorem

The next lemma conceals the heart of the proof of Theorem 4.2. The proof of
that lemma is presented in Section 5. Throughout this and the following
sections, for a graph $G$, we let $L(G)$ be the length of a longest cycle in
$G$.

######  Lemma 4.1.

Let $G$ be a 2-connected graph with treewidth $3$. Let $(T,\mathcal{V})$ be a
full tree decomposition of $G$ and $V_{t}\in\mathcal{V}$. Then either
$\mathrm{lct}(G)=1$ or there exists a longest cycle in $G$ that is fenced by
$V_{t}$ and intersects $V_{t}$ at most three times.

Using this lemma, we derive the main result of this section.

######  Theorem 4.2.

If $G$ is a 2-connected partial 3-tree, then $\mathrm{lct}(G)=1$.

###### Proof.

If $\mathrm{tw}(G)\leq 2$ then ${\mathrm{lct}(G)=1}$ by [8, Theorem 2].
Therefore, we may assume that ${\mathrm{tw}(G)=3}$. Assume by contradiction
that ${\mathrm{lct}(G)>1}$. It is straightforward to see that ${L:=L(G)\geq
5}$. Let $(T,\mathcal{V})$ be a full tree decomposition of $G$, which exists
by Proposition 3.1. For every ${t\in V(T)}$, let $\mathcal{F}(t)$ be the set
of longest cycles in $G$ that are fenced by $V_{t}$ and intersect $V_{t}$ at
most three times. By Lemma 4.1, ${\mathcal{F}(t)\neq\emptyset}$ for every
${t\in V(T)}$. Observe that, as $L\geq 5$, for every such $t$, no cycle in
$\mathcal{F}(t)$ is contained in $G[V_{t}]$.

We direct some of the edges of $T$ to create an auxiliary directed forest
$T^{\prime}$ in the following way: $tt^{\prime}\in E(T^{\prime})$ if and only
if $tt^{\prime}\in E(T)$ and there exists a cycle $C\in\mathcal{F}(t)$ with
$\mathrm{Br}_{t}(C)=\mathrm{Br}_{t}(t^{\prime})$. By taking the last arc
$tt^{\prime}$ of a maximal directed path in $T^{\prime}$, we will have two
longest cycles ${C\in\mathcal{F}(t)}$ and ${D\in\mathcal{F}(t^{\prime})}$ such
that ${\mathrm{Br}_{t}(C)=\mathrm{Br}_{t}(t^{\prime})}$ and
${\mathrm{Br}_{t^{\prime}}(D)=\mathrm{Br}_{t^{\prime}}(t)}$.

Note that the bags containing vertices of $C$ are in
$\mathrm{Br}_{t}(t^{\prime})\cup\\{t\\}$, and the bags containing vertices of
$D$ are in $\mathrm{Br}_{t^{\prime}}(t)\cup\\{t^{\prime}\\}$. Since
$\mathrm{Br}_{t}(t^{\prime})$ and $\mathrm{Br}_{t^{\prime}}(t)$ are disjoint,
${V(C)\cap V(D)\subseteq V_{t}\cup V_{t^{\prime}}}$. Let
${V_{t}=\\{a,b,c,u\\}}$ and ${V_{t^{\prime}}=\\{a,b,c,w\\}}$.

It is straightforward to see that $u\notin V(C)$ and that $w\notin V(D)$. and
therefore $V(C)\cap V(D)\subseteq V_{t}\cap V_{t^{\prime}}$. As ${|V(C)\cap
V(D)|\geq 2}$, this implies that ${|V(C)\cap V_{t}|\geq 2}$ and ${|V(D)\cap
V_{t^{\prime}}|\geq 2}$. Observe that any other longest cycle intersects
${V_{t}\cap V_{t^{\prime}}}$ at least twice. Otherwise it would intersect $C$
or $D$ at most once, a contradiction. As $\mathrm{lct}(G)>1$, there exists a
longest cycle $F$ that does not contain $a$ and a longest cycle $H$ that does
not contain $c$. By the previous observation, $F$ intersects ${V_{t}\cap
V_{t^{\prime}}}$ at $\\{b,c\\}$ and $H$ intersects ${V_{t}\cap
V_{t^{\prime}}}$ at $\\{a,b\\}$. Let $F^{\prime}$ and $F^{\prime\prime}$ be
the two $bc$-parts of $F$, with $|F^{\prime}|\geq|F^{\prime\prime}|$. Let
$H^{\prime}$ and $H^{\prime\prime}$ be the two $ab$-parts of $H$, with
$|H^{\prime}|\geq|H^{\prime\prime}|$. The rest of the proof is divided into
whether $C$ and $D$ 2-intersect or 3-intersect ${V_{t}\cap V_{t^{\prime}}}$.

######  Case 1:

$C$ 2-intersects $V_{t}\cap V_{t^{\prime}}$.

Without loss of generality, assume that $C$ 2-intersects $V_{t}\cap
V_{t^{\prime}}$ at $\\{a,b\\}$. Suppose for a moment that $F^{\prime}$ is
internally disjoint from $C$. As $F$ and $C$ intersect each other at least
twice, $F^{\prime\prime}$ and $C$ intersect each other at a vertex $x$
different from $b$. Let $F^{\prime\prime}_{cx}$ be the subpath of
$F^{\prime\prime}$ that is internally disjoint from $C$, starts at $c$ and
ends at $x$. Let $C_{xb}$ be the subpath of $C$ with extremes $x$ and $b$ such
that ${|C_{bx}|\geq L/2}$. Then ${F^{\prime}\cdot F^{\prime\prime}_{cx}\cdot
C_{xb}}$ is a cycle longer than $L$, a contradiction (Figure 3(a)). We
conclude that $F^{\prime}$ is internally disjoint from $D$. If $D$
2-intersects $V_{t}\cap V_{t^{\prime}}$, then, as $|V(C)\cap V(D)|\geq 2$, we
must have that $D$ intersects $V_{t}\cap V_{t^{\prime}}$ at $\\{a,b\\}$. But
then we obtain a contradiction as before, with $D$ instead of $C$. So $D$
3-intersects $V_{t}\cap V_{t^{\prime}}$ (at $\\{a,b,c\\}$). Let
$D_{ab},D_{ac},D_{bc}$ be the $abc$-parts of $D$. As ${C^{\prime\prime}\cdot
D_{ab}}$ and ${(D-D_{ab})\cdot C^{\prime}}$ are both longest cycles, we have
that ${|C^{\prime}|=|D_{ab}|}$. Similarly, ${|C^{\prime\prime}|=|D_{ab}|}$.
Hence ${|C^{\prime}|=|C^{\prime\prime}|=|D_{ab}|=L/2}$. As $F^{\prime}$ is
internally disjoint from $D$, ${D_{ab}\cdot F^{\prime}\cdot D_{ca}}$ is a
cycle longer than $L$, again a contradiction (Figure 3(b)).

######  Case 2:

Both $C$ and $D$ 3-intersect $V_{t}\cap V_{t^{\prime}}$.

Let $C_{ab},C_{ac},C_{bc}$ be the $abc$-parts of $C$. Let
$D_{ab},D_{ac},D_{bc}$ be the $abc$-parts of $D$. Assume without loss of
generality that $F^{\prime}$ is internally disjoint from $C$. Observe that
both $(C-C_{bc})\cdot F^{\prime}$ and $C_{bc}\cdot F^{\prime}$ are cycles. We
conclude that
$|C_{bc}|=|C_{ab}|+|C_{ac}|=|F^{\prime}|=|F^{\prime\prime}|=L/2$. As
$(C-C_{bc})\cdot D_{bc}$ and $(D-D_{bc})\cdot C_{bc}$ are cycles,
$|C_{bc}|=|D_{bc}|=L/2$. A similar analysis with $H$ instead of $F$ shows us
that $|C_{ab}|=|D_{ab}|=L/2$. This implies that $|C_{ac}|=0$, a contradiction
(Figure 3(c)).

This concludes the proof of the theorem. ∎

$V_{t}$$V_{t^{\prime}}$$a$$b$$c$$C$$F^{\prime}$$x$ (a)

$V_{t}$$V_{t^{\prime}}$$a$$b$$c$$C$$D$$F^{\prime}$ (b)

$V_{t}$$V_{t^{\prime}}$$a$$b$$c$$C$$D$$F^{\prime}$$H^{\prime}$ (c)

Figure 3: Cycles $C,D,F$ and $H$ as in the proof of Theorem 4.2. (a) $C$
2-intersects $V_{t}\cap V_{t^{\prime}}$ and $F^{\prime}$ is internally
disjoint from $C$. (b) $C$ 2-intersects $V_{t}\cap V_{t^{\prime}}$ and
$F^{\prime}$ is internally disjoint from $D$. (c) $C$ 3-intersects $V_{t}\cap
V_{t^{\prime}}$.

##  5 Proof of the main lemma

For all lemmas in this subsection, we fix a graph $G$ with $\mathrm{tw}(G)=3$
and ${\mathrm{lct}(G)>1}$, a full tree decomposition $(T,\mathcal{V})$ of $G$,
and a node $t\in V(T)$. We let $\mathcal{X}_{2}$ be the set of all longest
cycles in $G$ that 2-cross $V_{t}$, and let $\mathcal{F}$ be the set of all
longest cycles in $G$ that are fenced by $V_{t}$ and intersect $V_{t}$ at most
three times. Therefore, proving Lemma 4.1 reduces to prove that
$\mathcal{F}\neq\emptyset$.

###### Proof of Lemma 4.1.

Suppose that $\mathcal{X}_{2}\neq\emptyset$. If there are two non
$V_{t}$-equivalent longest cycles in $\mathcal{X}_{2}$, then we are done by
Lemma 5.1. If all cycles in $\mathcal{X}_{2}$ are $V_{t}$-equivalent, then we
are done by Lemma 5.2. Hence $\mathcal{X}_{2}=\emptyset$, and we are done by
Lemma 5.3. ∎

Next we prove Lemmas 5.1, 5.2 and 5.3. We depend on an auxiliary result
(Corollary 6.3) presented and proved ahead, in Section 6.

######  Lemma 5.1.

If there are two non $V_{t}$-equivalent longest cycles in $\mathcal{X}_{2}$,
then ${\mathcal{F}\neq\emptyset}$.

###### Proof.

Let $V_{t}=\\{a,b,c,d\\}$. Suppose by contradiction that
${C,D\in\mathcal{X}_{2}}$, ${V(C)\cap V_{t}=\\{a,b\\}}$ and ${V(D)\cap
V_{t}\neq\\{a,b\\}}$. Let $C^{\prime}$ and $C^{\prime\prime}$ be the
corresponding $ab$-parts of $C$. If $D$ 2-crosses $V_{t}$ at $\\{c,d\\}$, then
$V(C)\cap V(D)=\emptyset$, a contradiction. Hence, we may assume that $D$
2-crosses $V_{t}$ at $\\{a,c\\}$. Let $D^{\prime}$ and $D^{\prime\prime}$ be
the corresponding $ac$-parts of $D$. As both $C$ and $D$ cross $V_{t}$, we may
assume, without loss of generality, that $C^{\prime}$ is internally disjoint
from $D^{\prime}$ and that $C^{\prime\prime}$ is internally disjoint from
$D^{\prime\prime}$. As $\mathrm{lct}(G)>1$, there exists a longest cycle $F$
that does not contain $a$. If $F$ is fenced by $V_{t}$, we are done, so let us
assume that $F$ crosses $V_{t}$.

First consider the case in which $F$ 2-intersects $V_{t}$. As $F$ intersects
both $C$ and $D$, we have that $F$ 2-intersects $V_{t}$ at $\\{b,c\\}$. Let
$F^{\prime}$ and $F^{\prime\prime}$ be the corresponding $bc$-parts of $F$.
Suppose that $C$, $D$ and $F$ are $t$-inside $abc$. As $G$ is 2-connected,
there exist two internally disjoint paths starting at $d$ and ending at
distinct vertices in $\\{a,b,c\\}$. Let $P$ and $Q$ be these two paths, and
suppose without loss of generality that $b$ is an extreme of $P$ and that $c$
is an extreme of $Q$. By Proposition 3.2, both $P$ and $Q$ are internally
disjoint from $C$ and $D$. But then ${P\cdot Q\cdot D^{\prime}\cdot
C^{\prime}}$ and ${P\cdot Q\cdot D^{\prime\prime}\cdot C^{\prime\prime}}$ are
both cycles, at least one of them longer than $L$, a contradiction (Figure
4(a)). Hence, at least one of $\\{C,D,F\\}$, say $C$, is not $t$-inside $abc$.
We may assume that $C^{\prime\prime}$ is internally disjoint from both $D$ and
$F$. As $D$ and $F$ 2-cross $V_{t}$, we may assume that $D^{\prime}$ is
internally disjoint from $F^{\prime}$ and that $D^{\prime\prime}$ is
internally disjoint from $F^{\prime\prime}$. But then ${C^{\prime\prime}\cdot
D^{\prime}\cdot F^{\prime}}$ and ${C^{\prime\prime}\cdot D^{\prime\prime}\cdot
F^{\prime\prime}}$ are both cycles, at least one of them longer than $L$, a
contradiction (Figure 4(b)).

$c$$d$$b$$a$$C$$D$$P$$Q$

(a)

$c$$d$$b$$a$$C$$D$$F$

(b)

Figure 4: $(a)$ $C,D$ and $F$ are $t$-inside $abc$. $(b)$ At least one of
$\\{C,D,F\\}$ is not $t$-inside $abc$.

Now suppose that $F$ 3-intersects $V_{t}$ (at $\\{b,c,d\\}$). If both $C$ and
$D$ are $t$-inside $abc$, then we can proceed as in the previous paragraph
with $F_{bd}$ and $F_{cd}$ instead of $P$ and $Q$ respectively. If both $C$
and $D$ are $t$-outside $abc$, then $V(C)\cap V(D)=\\{a\\}$, a contradiction.
Hence, at least one of $\\{C,D\\}$ $t$-jumps $abc$. Without loss of
generality, suppose that $C$ $t$-jumps $abc$ and that
$\mathrm{Br}_{t}(C^{\prime\prime})\subseteq{\mathscr{B}\\!}_{t}(abd)$. Let $R$
be the subpath of $F_{bd}$ that starts at $d$, ends at a vertex of
$C^{\prime\prime}$ and is internally disjoint from $C^{\prime\prime}$. Suppose
that the other extreme of $R$ is $x$. First consider the case in which $D$
also $t$-jumps $abc$, and without loss of generality suppose that
$\mathrm{Br}_{t}(D^{\prime})\subseteq{\mathscr{B}\\!}_{t}(acd)$. Let $S$ be
the subpath of $F_{cd}$ that starts at $d$, ends at $D^{\prime}$ and is
internally disjoint from $D^{\prime}$. Suppose that the other extreme of $S$
is $y$. Let $C^{\prime\prime}_{ax}$ and $C^{\prime\prime}_{bx}$ be the two
$x$-tails of $C^{\prime\prime}$. Let $D^{\prime}_{ay}$ and $D^{\prime}_{cy}$
be the two $y$-tails of $D^{\prime}$. Then $C^{\prime}\cdot
C^{\prime\prime}_{bx}\cdot R\cdot S\cdot D^{\prime}_{ya}$ and
$D^{\prime\prime}\cdot D^{\prime}_{cy}\cdot S\cdot R\cdot
C^{\prime\prime}_{xa}$ are cycles, at least one of them longer than $L$, a
contradiction (Figure 5(a)). Finally consider the case in which $D$ is
$t$-inside $abc$. Then $C^{\prime}\cdot C^{\prime\prime}_{bx}\cdot R\cdot
F_{dc}\cdot D^{\prime}$ and $D^{\prime\prime}\cdot C^{\prime\prime}_{ax}\cdot
R\cdot F_{dc}$ are cycles, at least one of them longer than $L$, a
contradiction (Figure 5(b)). ∎

$c$$d$$b$$a$$C$$D$$F$$x$$y$

(a)

$c$$d$$b$$a$$C$$D$$F$$x$

(b)

Figure 5: Cases in the proof of Lemma 5.1. $F$ 3-intersects $V_{t}$. $(a)$ $D$
$t$-jumps $abc$. $(b)$ $D$ is $t$-inside $abc$.

######  Lemma 5.2.

If $\mathcal{X}_{2}\neq\emptyset$ and all cycles in $\mathcal{X}_{2}$ are
$V_{t}$-equivalent, then $\mathcal{F}\neq\emptyset$.

###### Proof.

Let $V_{t}=\\{a,b,c,d\\}$. Let $C\in\mathcal{X}_{2}$. Assume without loss of
generality that ${V(C)\cap V_{t}=\\{a,b\\}}$. As ${\mathrm{lct}(G)>1}$, there
exists a longest cycle $D$ that does not contain $a$, and a longest cycle $F$
that does not contain $b$. If either $D$ or $F$ is fenced by $V_{t}$,
$\mathcal{F}\neq\emptyset$. So, as all cycles in $\mathcal{X}_{2}$ are
$V_{t}$-equivalent, both $D$ and $F$ 3-intersect $V_{t}$.

Observe that $C$ must-jump both $abc$ and $abd$. Indeed, otherwise, we can
join $D$ and $F$ with a $ab$-part of $C$. In fact, this is valid to any cycle
equivalent to $C$, thus we have the following Claim.

######  Claim 1.

Every cycle that 2-crosses $V_{t}$ at $\\{a,b\\}$ jumps both $abc$ and $abd$.

Let $C^{\prime}$ and $C^{\prime\prime}$ be the two $ab$-parts of $C$. By Claim
1, we may assume that $C^{\prime}$ is $t$-inside $abc$ and that
$C^{\prime\prime}$ is $t$-inside $abd$.

Moreover, we have the following Claim regarding cycles $D$ and $F$.

######  Claim 2.

$D$ and $F$ jump both $abc$ and $abd$.

###### Proof of Claim 2.

If $D$ does not jump at least one of $\\{abc,abd\\}$, then $C$ and $D$ only
intersect at $b$, a contradiction to the fact that $G$ is 2-connected. Hence
$D$ jumps at least one of $\\{abc,abd\\}$. Analogously, $F$ jumps at least one
of $\\{abc,abd\\}$. Suppose by contradiction that the claim is not true. Then,
one of $\\{D,F\\}$, say $D$, jumps exactly one of $\\{abc,abd\\}$, say $abc$.
First suppose that $F$ jumps both of $\\{abc,abd\\}$. Recall that
$C^{\prime\prime}$ is the $ab$-part of $C$ that is $t$-inside $abd$. Let $R$
be the subpath of $C^{\prime\prime}$ that is internally disjoint from $F$,
starts at $b$ and ends at a vertex $x$ of $F$ (possibly $x=a$). Then
${F_{cd}\cdot F_{dx}\cdot R\cdot D_{bc}}$ and ${D_{cd}\cdot D_{db}\cdot R\cdot
F_{xa}\cdot F_{ac}}$ are cycles, one of them longer than $L$, a contradiction
(Figure 6(a)).

The rest of the proof follows by similar analysis to the previous case, we
show the cases in Figures 6(b) to (d). ∎

$c$$d$$b$$a$$C^{\prime\prime}$$C^{\prime}$$F$$D$$x$

(a)

$c$$d$$b$$a$$C^{\prime\prime}$$C^{\prime}$$F$$D$

(b)

$c$$d$$b$$a$$C^{\prime\prime}$$C^{\prime}$$D$$x$$F$

(c)

$c$$d$$b$$a$$C^{\prime\prime}$$C^{\prime}$$F$$D$

(d)

Figure 6: Cases in the proof of Claim 2 of Lemma 5.2. (a) $F$ jumps both $abc$
and $abd$. (b) $F$ jumps only $abd$ and $F_{cd}$ does not jump $acd$. In this
case, $D_{cd}\cdot F_{cd}\in\mathcal{X}_{2}$. (c) $F$ jumps only $abd$ and
$F_{cd}$ jumps $acd$. We consider a subpath $R$ of $C$ that starts at $b$ and
finishes at $D$ and proceed similar to Case $a$. (d) $F$ jumps only $abc$. We
can join parts of $F$ and $D$ with $C^{\prime\prime}$ and obtain longer
cycles.

By Claim 2 we have
${\mathrm{Br}_{t}(F_{ac}),\mathrm{Br}_{t}(D_{bc})\subseteq{\mathscr{B}\\!}_{t}(abc)}$
and
${\mathrm{Br}_{t}(F_{ad}),\mathrm{Br}_{t}(D_{bd})\subseteq{\mathscr{B}\\!}_{t}(abd)}$
(Figure 7).

$c$$d$$b$$a$$C^{\prime\prime}$$C^{\prime}$$F$$D$

Figure 7: The structure given by Claim 2 of Lemma 5.2.

Now, by Corollary 6.3, as ${\mathrm{lct}(G)>1}$, there exists a longest cycle
$H$ that does not $t$-jump $abc$. If $H$ intersects $V_{t}$ at most once, then
$H$ is fenced by $V_{t}$ and $\mathcal{F}\neq\emptyset$. Also, by Claim 1, $H$
can not 2-intersect $V_{t}$. So, $H$ intersects $V_{t}$ at least three times.

Suppose for a moment that $H$ 4-intersects $V_{t}$. As $H$ is a cycle, either
$H$ has a subpath from $a$ to $c$ that is disjoint from $b$ and $d$, or $H$
has a subpath from $b$ to $c$ that is disjoint from $a$ and $d$. Without loss
of generality assume the former. Let $H_{ac}$ be such subpath. Then there
exists a subpath $R$ of $H_{ac}$ from $a$ to $D_{cd}$ that is internally
disjoint from both $C$ and $D$. Let $x$ be its extreme in $D$. Then
${D_{bc}\cdot C^{\prime\prime}\cdot R\cdot D_{xc}}$ and ${C^{\prime}\cdot
D_{bd}\cdot D_{dx}\cdot R}$ are both cycles, one of them longer than $L$, a
contradiction (Figure 8(a)). We conclude that $H$ 3-intersects $V_{t}$. If $H$
is $t$-inside $abc$, then $H$ is fenced by $V_{t}$ by Corollary 6.3, so
$\mathcal{F}\neq\emptyset$ and we are done. Thus, $H$ is $t$-outside $abc$.

If $H$ contains both $a$ and $c$, then $H_{ac}$, the subpath of $H$ from $a$
to $c$, is internally disjoint from $C$ and we proceed as before. Hence,
either $H$ does not contain $a$ or $H$ does not contain $c$. Suppose for a
moment that $H$ does not contain $a$. Then $H_{bc}$, the subpath of $H$ from
$b$ to $c$, is internally disjoint from $C$ so we proceed as before (with $C$
and $F$ instead of $C$ and $D$). So, we may assume that $H$ does not contain
$c$. As $H$ is $t$-outside $abc$, we have that $H_{ab}$ is $t$-inside $abd$.
Moreover, observe that $H$ is $t$-inside $abd$. Indeed, if for example
$H_{bd}$ is $t$-outside $abd$ then we proceed as before. The same reasoning
applies if $H_{ad}$ is $t$-outside $abd$. Thus, as ${(F-F_{ad})\cdot H_{ad}}$
and ${(F-F_{ad})\cdot H_{ab}\cdot H_{bd}}$ are cycles, we have that
${|F_{ad}|\geq L/2}$. Now, repeating the argument with $abd$ instead of $abc$,
we deduce that there exists a longest cycle $J$ that 3-intersects $V_{t}$ at
$abc$ and is $t$-inside $abc$. Hence ${|F_{ac}|\geq L/2}$. This implies that
$|F_{cd}|=0$, a contradiction (Figure 8(b)). ∎

$c$$d$$b$$a$$C^{\prime\prime}$$C^{\prime}$$H$$x$$D$$x$

(a)

$c$$d$$b$$a$$F$$H$$J$

(b)

Figure 8: Cases in the last part of the proof of Lemma 5.2. (a) $H$
4-intersects $V_{t}$. (b) $H$ 3-intersects $V_{t}$.

The next lemma is the most technical. Its proof is organized into four claims.

######  Lemma 5.3.

If $\mathcal{X}_{2}=\emptyset$, then $\mathcal{F}\neq\emptyset$.

###### Proof.

As $\mathrm{lct}(G)>1$ and ${\mathcal{X}_{2}=\emptyset}$, for every triple of
vertices ${\Delta\subseteq V_{t}}$, there exists a nonempty collection
${\mathscr{C}\\!}_{\Delta}$ of longest cycles that 3-intersect $V_{t}$ at
$\Delta$. Suppose by contradiction that $\mathcal{F}=\emptyset$. Then, for
every ${\Delta\subseteq V_{t}}$, every cycle in ${\mathscr{C}\\!}_{\Delta}$
crosses $V_{t}$. Let
${\mathscr{C}\\!}=\\{{\mathscr{C}\\!}_{\Delta}:\Delta\subseteq V_{t}\\}$.

######  Claim 3.

For every triple of vertices ${\Delta\subseteq V_{t}}$, at least one cycle in
${{\mathscr{C}\\!}\setminus{\mathscr{C}\\!}_{\Delta}}$ does not jump $\Delta$.

###### Proof of Claim 3.

Suppose by contradiction that all cycles in
${{\mathscr{C}\\!}\setminus{\mathscr{C}\\!}_{abc}}$ jump $abc$. (The other
cases are analogous.) Then, as
${{\mathscr{C}\\!}_{abd},{\mathscr{C}\\!}_{bcd},{\mathscr{C}\\!}_{acd}\neq\emptyset}$,
for every ${\\{i,j\\}\subseteq abc}$, there exists a longest cycle that
2-jumps $abc$ at $\\{i,j\\}$. Hence, by Corollary 6.3 applied to $abc$, there
exists a longest cycle $C$ that does not jump $abc$. If $C$ intersects $V_{t}$
at most once or is as item $(ii)$ or $(iii)$ of Corollary 6.3, then, as
$\mathcal{X}_{2}=\emptyset$, $C$ is fenced by $abc$, which implies that
$\mathcal{F}\neq\emptyset$, a contradiction. Thus, we may assume that $C$ is
as item $(i)$ of Corollary 6.3, that is, $C$ is outside $abc$.

The rest of the proof is divided on two cases, whether $C$ 3-intersects or
4-intersects $V_{t}$.

######  Case 1:

$C$ 3-intersects $V_{t}$.

As all cycles in ${{\mathscr{C}\\!}\setminus{\mathscr{C}\\!}_{abc}}$ jump
$abc$, we have ${C\in{\mathscr{C}\\!}_{abc}}$. Let
${D\in{\mathscr{C}\\!}_{abd}}$. We know that $D$ jumps $abc$. If $D$ jumps
both $acd$ and $bcd$, ${(D-D_{ab})\cdot C_{ab}}\in{\mathscr{C}\\!}_{abd}$ but
does not jump $abc$, a contradiction (Figure 9(a)). If $D$ jumps neither $acd$
nor $bcd$, then ${C_{ab}\cdot D_{ab}}$ is a longest cycle that 2-crosses
$V_{t}$, contradicting the fact that $\mathcal{X}_{2}=\emptyset$ (Figure
9(b)). Hence, $\mbox{every }D\in{\mathscr{C}\\!}_{abd}\mbox{ jumps exactly one
of }\\{acd,bcd\\}.$ Analogously, we can conclude that $\mbox{every
}F\in{\mathscr{C}\\!}_{acd}\mbox{ jumps exactly one of }\\{bcd,abd\\},$ and
that $\mbox{every }J\in{\mathscr{C}\\!}_{bcd}\mbox{ jumps exactly one of
}\\{abd,acd\\}.$

Let
${(D,F,J)\in{\mathscr{C}\\!}_{abd}\times{\mathscr{C}\\!}_{acd}\times{\mathscr{C}\\!}_{bcd}}$.
Suppose that $D$ jumps $acd$ and $F$ jumps $abd$. Then, both ${(D-D_{ab})\cdot
C_{bc}\cdot F_{ca}}$ and ${(F-F_{ac})\cdot C_{cb}\cdot D_{ba}}$ are cycles,
one of them longer than $L$, a contradiction (Figure 9(c)). Repeating the same
argument with $\\{D,J\\}$ and $\\{F,J\\}$, we conclude that, without loss of
generality, $D\mbox{ jumps }acd,F\mbox{ jumps }bcd,\mbox{ and }J\mbox{ jumps
}abd.$ But then, ${(D-D_{ab})\cdot F_{ac}\cdot C_{cb}}$, ${(F-F_{ac})\cdot
J_{cb}\cdot C_{ba}}$, and ${(J-J_{bc})\cdot D_{ba}\cdot C_{ac}}$ are cycles
(Figure 9(d)), a contradiction.

$a$$b$$c$$d$$C$$D$

(a)

$a$$b$$c$$d$$C$$D$

(b)

$a$$b$$c$$d$$C$$D$$F$

(c)

$a$$b$$c$$d$$C$$D$$F$$J$

(d)

Figure 9: Case 1 in the proof of Claim 3 of Lemma 5.3. (a) $D$ jumps both
$acd$ and $bcd$. (b) $D$ does not jump neither $acd$ nor $bcd$. (c) $D$ jumps
$acd$ and $F$ jumps $abd$. (d) $D$ jumps $acd$ and $F$ jumps $bcd$ and $J$
jumps $abd$.

######  Case 2:

$C$ 4-intersects $V_{t}$.

Without loss of generality, suppose that $C$ has $abdc$-parts. As $C$ is
outside $abc$, we have that $C_{ab}$ is inside $abd$ and $C_{ac}$ is inside
$acd$. By similar techniques to the previous cases, we can show that
$\mbox{every cycle in }{\mathscr{C}\\!}_{abd}\mbox{ does not jump }acd.$
(Figures 10(a) and (b)). And, by symmetry, we can also show that $\mbox{every
cycle in }{\mathscr{C}\\!}_{acd}\mbox{ does not jump }abd.$ Let
$(D,F)\in{\mathscr{C}\\!}_{abd}\times{\mathscr{C}\\!}_{acd}$. By the previous
discussion, $D_{ad}$ is outside $acd$, and $F_{ad}$ is outside $abd$. This
implies that $(D-D_{ad})\cdot F_{ad}\in{\mathscr{C}\\!}_{abd}$ and jumps
$acd$, a contradiction (Figure 10(c)).

This concludes the proof of the Claim. ∎

$a$$b$$c$$d$$C$$D$

(a)

$a$$b$$c$$d$$C$$D$

(b)

$b$$c$$d$$C$$D$$a$$F$

(c)

Figure 10: Case 2 in the proof of Claim 3. (a) $D$ jumps $acd$ and $D_{bd}$ is
outside $abd$. In this situation, ${(D-D_{ab})\cdot
C_{ab}\in{\mathscr{C}\\!}_{abd}}$ but does not jump $abc$. (b) $D$ jumps $acd$
and $D_{bd}$ is inside $abd$. In this situation, ${C_{ab}\cdot C_{bd}\cdot
D_{da}\in{\mathscr{C}\\!}_{abd}}$ but does not jump $abc$. (c) $D$ does not
jump $acd$ and $F$ does not jump $abd$.

The next claim is used in the proofs of Claims 5 and 6. It uses Claim 3.

######  Claim 4.

For every triple of vertices ${\Delta\subseteq V_{t}}$, every cycle in
${\mathscr{C}\\!}_{\Delta}$ jumps at least two of
${\\{abd,acd,bcd,abc\\}\setminus\\{\Delta\\}}$.

###### Proof of Claim 4.

Without loss of generality, suppose that $\Delta=abc$ and there exists a
cycle, say $C\in{\mathscr{C}\\!}_{abc}$, that jumps at most one of
$\\{abd,acd,bcd\\}$. If $C$ jumps no one of $\\{abd,acd,bcd\\}$, then $C$ is
inside $abc$. By Claim 3, there exists a longest cycle
$D\in{\mathscr{C}\\!}\setminus{\mathscr{C}\\!}_{abc}$ that does not jump
$abc$. By joining two parts of $C$ and $D$, we obtain a cycle in
$\mathcal{X}_{2}$, a contradiction.

So, without loss of generality suppose $C$ jumps $abd$. Let
$D\in{\mathscr{C}\\!}_{abd}$. If $D$ jumps $abc$, then, ${C_{ab}\cdot
D_{ab}}\in\mathcal{X}_{2}$, a contradiction. (Figure 11(a)). Hence, $D$ is
outside $abc$. Thus, as both ${(C-C_{ab})\cdot D_{ab}}$ and
${(C-C_{ab})\cdot(D-D_{ab})}$ are cycles, we conclude that $|C_{ab}|\geq L/2.$

$a$$b$$c$$d$$C$$D$

(a)

$a$$b$$c$$d$$C$$D$$F$

(b)

$a$$b$$c$$d$$C$$F$$x$

(c)

Figure 11: Cases in the proof of Claim 4 of Lemma 5.3. (a) $D$ jumps $abc$.
(b) $D$ is outside $abc$ and $F\in{\mathscr{C}\\!}_{abc}$. (c) $D$ is outside
$abc$ and $F\in{\mathscr{C}\\!}_{acd}$.

By Claim 3, there exists a longest cycle
$F\in{\mathscr{C}\\!}\setminus{\mathscr{C}\\!}_{abd}$ that is outside $abd$.
If ${F\in{\mathscr{C}\\!}_{abc}}$ then ${C_{ab}\cdot
F_{ab}}\in\mathcal{X}_{2}$, a contradiction. (Figure 11(b)). If
$F\in{\mathscr{C}\\!}_{acd}$ then there exists a subpath $R$ of $C_{bc}$
starting at $b$, that ends at a vertex $x$ of $F_{ac}$ and is internally
disjoint from $F$. Then, both ${C_{ab}\cdot R\cdot F_{xa}}$ and ${C_{ab}\cdot
R\cdot(F-F_{xa})}$ are cycles, a contradiction (Figure 11(c)).

The case in which $F\in{\mathscr{C}\\!}_{bcd}$ is symmetric to the case in
which $F\in{\mathscr{C}\\!}_{acd}$. ∎

######  Claim 5.

There exists a triple of vertices ${\Delta\subseteq V_{t}}$ such that every
cycle in ${\mathscr{C}\\!}_{\Delta}$ jumps exactly two of
${\\{abd,acd,bcd,abc\\}\setminus\\{\Delta\\}}$.

###### Proof of Claim 5.

By Claim 4, for each triple of vertices $\Delta\subseteq V_{t}$, every cycle
in ${\mathscr{C}\\!}_{\Delta}$ jumps two or three of
${\\{abd,acd,bcd,abc\\}\setminus\\{\Delta\\}}$. Suppose by contradiction that
for each $\Delta\subseteq V_{t}$ there exists a longest cycle in
${\mathscr{C}\\!}_{\Delta}$ that jumps the three of
${\\{abd,acd,bcd,abc\\}\setminus\\{\Delta\\}}$. Let $C$, $D$, and $F$ be
corresponding cycles in ${\mathscr{C}\\!}_{abc}$, ${\mathscr{C}\\!}_{abd}$,
and ${\mathscr{C}\\!}_{bcd}$ respectively. We can easily conclude that
$|F_{bc}|=|C_{bc}|$ and $|D_{bd}|=|F_{bd}|.$

$a$$b$$c$$d$$C$$D$$H$$F$

Figure 12: Situation in the proof of Claim 5 of Lemma 5.3.

Let $H$ be a corresponding cycle in ${\mathscr{C}\\!}_{acd}$. We have that
both ${F_{cb}\cdot C_{ba}\cdot D_{ad}\cdot H_{dc}}$ and ${F_{db}\cdot
D_{ba}\cdot C_{ac}\cdot H_{cd}}$ are cycles, and their lengths sum more than
$|F_{bc}|+|F_{bd}|+|C_{ab}|+|C_{ac}|+|D_{ab}|+|D_{ad}|$. By the last part of
the previous paragraph, this sum equals
$|C_{bc}|+|D_{bd}|+|C_{ab}|+|C_{ac}|+|D_{ab}|+|D_{ad}|=|C|+|D|=2L$, a
contradiction (Figure 12). ∎

Suppose that $abc$ is the triangle given by Claim 5. Let
${C\in{\mathscr{C}\\!}_{abc}}$ We may assume without loss of generality that
$C$ jumps $abd$ and $acd$, and is outside $bcd$. By Claim 3, there exist
cycles ${F,H,J\in{\mathscr{C}\\!}}$ such that $F$ 2-intersects $abd$ but does
not jump $abd$, $H$ 2-intersects $acd$ but does not jump $acd$, and $J$
2-intersects $abc$ but does not jump $abc$.

By similar arguments to the previous Claims, we can show the next claim.

######  Claim 6.

$F\in{\mathscr{C}\\!}_{bcd}$ and $H\in{\mathscr{C}\\!}_{bcd}$ (Figure 13).

$a$$b$$c$$d$$F$$C$$H$

Figure 13: Situation of Claim 6 of Lemma 5.3.

The rest of the proof of Lemma 5.3 is divided on two cases depending on $J$.
If $J\in{\mathscr{C}\\!}_{bcd}$ (Figure 14(a)), then ${(C-C_{bc})\cdot
J_{bc}}\in{\mathscr{C}\\!}_{abc}$ and jumps the three of $\\{abd,acd,bcd\\}$,
a contradiction to the choice of $abc$ as in Claim 5. Thus,
${J\in{\mathscr{C}\\!}_{abd}}$ (Figure 14(b)).

By Claim 4, $J$ jumps both $acd$ and $bcd$. By joining parts of cycles as in
the previous claims, we can show that $|F_{bd}|\geq L/2.$ Now, let $R$ be the
subpath of $F_{cd}$ that is internally disjoint from $C_{ac}$, starts at $d$
and ends at a vertex $x$ in $C_{ac}$. Let $S$ be the subpath of $C$ that
starts at $x$, ends at $b$, and is such that $|S|\geq L/2$. Then,
${F_{bd}\cdot R\cdot S}$ is a cycle longer than $L$, a contradiction. This
concludes the proof of the lemma. ∎

$a$$b$$c$$d$$F$$C$$H$$J$

(a)

$a$$b$$c$$d$$F$$C$$H$$J$

(b)

Figure 14: Cases in the last part of the proof of Lemma 5.3. (a)
$J\in{\mathscr{B}\\!}_{bcd}$ (Case 1). (b) $J\in{\mathscr{B}\\!}_{abd}$ (Case
2).

##  6 Proof of the auxiliary lemmas

The main result of this section is Corollary 6.3, which is used many times in
Section 5. For all lemmas, propositions and corollaries in this subsection, we
fix a graph $G$ with $\mathrm{tw}(G)=3$, a full tree decomposition
$(T,\mathcal{V})$ of $G$, and a node $t\in V(T)$ with $V_{t}=\\{a,b,c,d\\}$.
For every $ij\in\\{ab,bc,ac\\}$, we set ${\mathscr{C}\\!}_{ij}$ as the
collection of all longest cycles in $G$ that 2-jump $abc$ at $\\{i,j\\}$ and
put ${\mathscr{C}\\!}_{abc}$ as the collection of all longest cycles in $G$
that 3-jump $abc$. Finally, we set
${{\mathscr{C}\\!}={\mathscr{C}\\!}_{ab}\cup{\mathscr{C}\\!}_{bc}\cup{\mathscr{C}\\!}_{ac}\cup{\mathscr{C}\\!}_{abc}}$.

We begin by extending the definition of branch. Given a component $A$ of
$G-V_{t}$, we say that $\mathrm{Br}_{t}(A)=\mathrm{Br}_{t}(v)$, where $v$ is a
vertex in $A$. Observe that $\mathrm{Br}_{t}(A)$ is well defined, as every
pair of vertices in $A$ are not separated by $V_{t}$.

Given a triple of vertices ${\Delta\subseteq V_{t}}$, it is denoted by
$\mathcal{A}_{t}(\Delta)$ the set of components inside $\Delta$, that is,

${\mathcal{A}_{t}(\Delta)=\\{A:A\mbox{ is a component of }{G-V_{t}}\mbox{ and
}\mathrm{Br}_{t}(A)\subseteq{\mathscr{B}\\!}_{t}(\Delta)\\}}.$

(Recall the definition of ${\mathscr{B}\\!}_{t}(\Delta)$ in Section 3.)

######  Lemma 6.1.

If ${\mathscr{C}\\!}_{ij}\neq\emptyset$ for every $ij\in\\{ab,bc,ac\\}$, then
all longest cycles in ${\mathscr{C}\\!}$ pairwise intersect each other in a
component of $\mathcal{A}_{t}(abc)$.

###### Proof.

Let $(\bar{C},\bar{D})\in{\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{ac}$.
Let $\bar{C}^{\prime}$ and $\bar{C}^{\prime\prime}$ be the two $ab$-parts of
$\bar{C}$. Let $\bar{D}^{\prime}$ and $\bar{D}^{\prime\prime}$ be the two
$ac$-parts of $\bar{D}$. As $\bar{C}$ and $\bar{D}$ jump $abc$, we may assume
that $\bar{C}^{\prime}$ and $\bar{D}^{\prime}$ are inside $abc$ and that
$\bar{C}^{\prime\prime}$ and $\bar{D}^{\prime\prime}$ are outside $abc$.
Suppose for a moment that $\bar{C}^{\prime}$ and $\bar{D}^{\prime}$ are
internally disjoint. Let $F\in{\mathscr{C}\\!}_{bc}$, which exists by the
hypothesis of the lemma. Let $F^{\prime}$ and $F^{\prime\prime}$ be the two
$bc$-parts of $F$. As $F$ jumps $abc$, we may assume that $F^{\prime}$ is
inside $abc$ and that $F^{\prime\prime}$ is outside $abc$. Let $R$ be a
subpath of $F^{\prime}$ that is internally disjoint from $\bar{C}^{\prime}$
and $\bar{D}^{\prime}$ connecting $\bar{C}^{\prime}$ and $\bar{D}^{\prime}$.
Suppose that $V(R)\cap V(\bar{C})=\\{x\\}$ and that $V(R)\cap
V(\bar{D})=\\{y\\}$. Then
$\bar{C}^{\prime\prime}\cdot\bar{C}^{\prime}_{bx}\cdot
R\cdot\bar{D}^{\prime}_{ya}$ and
$\bar{D}^{\prime\prime}\cdot\bar{D}^{\prime}_{cy}\cdot
R\cdot\bar{C}^{\prime}_{xa}$ are both cycles, one of them longer than $L$, a
contradiction (Figure 15(a)).

Thus $\bar{C}^{\prime}$ and $\bar{D}^{\prime}$ internally intersect inside
$abc$. As $\bar{C}^{\prime}$ and $\bar{D}^{\prime}$ 2-intersects $abc$, they
are fenced by $abc$. Hence, as they internally intersect each other, there
exists a component $A\in\mathcal{A}_{t}(abc)$ such that all internal vertices
of $\bar{C}^{\prime}$ and $\bar{D}^{\prime}$ are in $A$. We show that $A$ is
the desired component. That is, all longest cycles in ${\mathscr{C}\\!}$
pairwise intersect each other in $A$.

$a$$b$$c$$d$$\bar{C}^{\prime}$$\bar{D}^{\prime}$$F^{\prime}$$x$$y$

(a)

$a$$b$$c$$d$$C^{\prime}$$D^{\prime}$$F^{\prime}$$x$$y$

(b)

Figure 15: Cases in the proof of Lemma 6.1. (a) Pair
$(\bar{C},\bar{D})\in{\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{ac}$ with
$\bar{C}^{\prime}$ and $\bar{D}^{\prime}$ inside $abc$ and the path
$F^{\prime}$. (b) Pair
$(C,D)\in{\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{ab}$ with $C^{\prime}$
and $D^{\prime}$ inside $abc$ and the path $F^{\prime}$.

Let $(C,D)\in{\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{ac}$. Let
$C^{\prime}$ and $C^{\prime\prime}$ be the two $ab$-parts of $C$. Let
$D^{\prime}$ and $D^{\prime\prime}$ be the two $ac$-parts of $D$. Analogously
to the previous paragraph, $C^{\prime}$ and $D^{\prime}$ internally intersect
inside $abc$. Also, $C^{\prime}$ and $\bar{D}^{\prime}$ internally intersect
inside $abc$. Hence the internal vertices of $C^{\prime}$ and $D^{\prime}$ are
in $A$. We conclude that $C^{\prime}$ and $D^{\prime}$ intersect in a vertex
of $A$. A similar proof shows that every pair of cycles in
$({\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{bc})\cup({\mathscr{C}\\!}_{bc}\times{\mathscr{C}\\!}_{ac})$
intersect each other in a vertex of $A$.

Let $(C,D)\in{\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{ab}$. Let
$C^{\prime}$ and $C^{\prime\prime}$ be the two $ab$-parts of $C$. Let
$D^{\prime}$ and $D^{\prime\prime}$ be the two $ab$-parts of $D$, with
$C^{\prime}$ and $D^{\prime}$ inside $abc$. By the previous paragraph,
$C^{\prime}$ and $\bar{D}^{\prime}$ internally intersect in $A$, and
$D^{\prime}$ and $\bar{D}^{\prime}$ internally intersect in $A$. Hence, all
internal vertices of $C^{\prime}$ and $D^{\prime}$ are in $A$. So, it suffices
to prove that $C^{\prime}$ and $D^{\prime}$ internally intersect inside $abc$.

Suppose for a moment that $C^{\prime}$ and $D^{\prime}$ are internally
disjoint. Let $F\in{\mathscr{C}\\!}_{bc}$, which exists by the hypothesis of
the lemma. Let $R$ be a subpath of $F$ that is inside $abc$, internally
disjoint from $C^{\prime}$ and $D^{\prime}$ and connecting $C^{\prime}$ and
$D^{\prime}$. Let ${\\{x\\}=V(R)\cap V(C^{\prime})}$ and ${\\{y\\}=V(R)\cap
V(D^{\prime})}$. Then ${C^{\prime\prime}\cdot C^{\prime}_{bx}\cdot R\cdot
D^{\prime}_{ya}}$ and ${D^{\prime\prime}\cdot D^{\prime}_{by}\cdot R\cdot
C^{\prime}_{xa}}$ are both cycles, one of them longer than $L$, a
contradiction (Figure 15(b)). A similar proof shows that every pair of cycles
in
${({\mathscr{C}\\!}_{bc}\times{\mathscr{C}\\!}_{bc})\cup({\mathscr{C}\\!}_{ac}\times{\mathscr{C}\\!}_{ac})}$
intersect in $A$.

Let $(C,D)\in{\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{ab}$. Let
$D^{\prime}$ and $D^{\prime\prime}$ be the two $ab$-parts of $D$, with
$D^{\prime}$ inside $abc$. By the previous paragraph, $D^{\prime}$ and
$\bar{C}^{\prime}$ internally intersect in $A$. Hence, all internal vertices
of $D^{\prime}$ are in $A$. So, it suffices to prove that $D^{\prime}$
internally intersects any of $\\{C_{ab},C_{bc},C_{ac}\\}$. Suppose not. As $C$
jumps $abc$, at least one of $\\{C_{ab},C_{bc},C_{ac}\\}$ is inside $abc$. If
$C_{ab}$ is inside $abc$ then ${C_{ac}\cdot C_{cb}\cdot D^{\prime}}$ and
${D^{\prime\prime}\cdot C_{ab}}$ are longest cycles. As
${D^{\prime\prime}\cdot C_{ab}\in{\mathscr{C}\\!}_{ab}}$, by the previous
paragraph, ${D^{\prime\prime}\cdot C_{ab}}$ intersects $D$ in a vertex of $A$.
As $D^{\prime\prime}$ is outside $abc$, $C_{ab}$ and $D^{\prime}$ internally
intersect in $A$, a contradiction. Hence $C_{ab}$ is outside $abc$. Let
${F\in{\mathscr{C}\\!}_{bc}}$. By considering a subpath $R$ of $F$ as in
Figure 16(a), we obtain two cycles ${C_{ab}\cdot D^{\prime}_{bx}\cdot R\cdot
C_{yc}\cdot C_{ca}}$ and ${D^{\prime\prime}\cdot C_{by}\cdot R\cdot
D^{\prime}_{xa}}$ a contradiction. Hence, every pair of cycles in
${\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{ab}$ intersect in $A$. A
similar proof shows that every pair of cycles in
$({\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{bc})\cup({\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{ac})$
intersect in $A$.

$a$$b$$c$$d$$D^{\prime}$$C_{bc}$$R$$x$$y$

(a)

$a$$b$$c$$d$$D_{ab}$$C_{bc}$$C_{ab}$$R$$D_{bc}$$y$$x$

(b)

Figure 16:  Cases in the proof of Lemma 6.1. (a) Pair
$(C,D)\in{\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{ab}$, with $C_{bc}$ and
$D^{\prime}$ inside $abc$, and the path $F^{\prime}$. (b) Pair
$(C,D)\in{\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{abc}$ with
$C_{ab},C_{bc}$, $D_{ab}$ and $D_{bc}$ inside $abc$, and the path
$F^{\prime}$.

Finally, let $(C,D)\in{\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{abc}$.
Suppose that only one of $\\{C_{ab},C_{ac},C_{bc}\\}$, say $C_{ab}$, is inside
$abc$. Let $F\in{\mathscr{C}\\!}_{ab}$, $F^{\prime}$ be the $ab$-part of $F$
that is inside $abc$, and $F^{\prime\prime}$ be the $ab$-part of $F$ that is
outside $abc$. Then $C_{ac}\cdot C_{cb}\cdot F^{\prime}$ and
$F^{\prime\prime}\cdot C_{ab}$ are longest cycles. By the previous paragraph,
as $F^{\prime\prime}\cdot C_{ab}\in{\mathscr{C}\\!}_{ab}$, $C_{ab}$ and $D$
intersect in a vertex of $A$. Hence, we may assume that two of
$\\{C_{ab},C_{ac},C_{bc}\\}$ are inside $abc$, and, analogously, two of
$\\{D_{ab},D_{ac},D_{bc}\\}$ are inside $abc$. Without loss of generality we
have two cases.

First suppose that $C_{ab}$, $C_{bc}$, $D_{ab}$, and $D_{bc}$ are inside
$abc$. Let $F\in{\mathscr{C}\\!}_{ac}$. By considering a subpath $R$ of $F$ as
in Figure 16(b), we obtain two cycles $(C-C^{\prime}_{bx})\cdot R\cdot
D^{\prime}_{yb}$ and $(D-D^{\prime}_{by})\cdot R\cdot C^{\prime}_{xb}$ are
cycles, a contradiction.

Now suppose that $\\{C_{ab},C_{bc}\\}$ and $\\{D_{ab},D_{ac}\\}$ are inside
$abc$. Let $F\in{\mathscr{C}\\!}_{ab}$. By considering a subpath $R$ of $F$
that starts at a vertex $x$ of $C$ and finishes at a vertex $y$ of $D$, we
have two cases as in Figure 17 In the former, we obtain two cycles
${(C-C_{ax})\cdot R\cdot D^{\prime}_{ya}}$ and ${(D-D^{\prime}_{ay})\cdot
R\cdot C_{xa}}$; in the later we obtain two cycles $(C-C_{cx})\cdot R\cdot
D_{yc}$ and $(D-D_{cy})\cdot R\cdot C_{xc}$, a contradiction.

$a$$b$$c$$d$$D_{ab}$$C_{bc}$$C_{ab}$$R$$D_{ac}$$y$$x$

(a)

$a$$b$$c$$d$$D_{ab}$$C_{bc}$$C_{ab}$$R$$D_{ac}$$y$$x$

(b)

Figure 17: Pair $(C,D)\in{\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{abc}$,
with $C_{ab},C_{bc},D_{ab}$ and $D_{ac}$ inside $abc$. (a) $x\in C_{ab}$ and
$y\in D_{ab}$. (b) $x\in C_{bc}$ and $y\in D_{ac}$.

As
${\mathscr{C}\\!}\times{\mathscr{C}\\!}=({\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{ab})\cup({\mathscr{C}\\!}_{ac}\times{\mathscr{C}\\!}_{ac})\cup({\mathscr{C}\\!}_{bc}\times{\mathscr{C}\\!}_{bc})\cup({\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{ac})\cup({\mathscr{C}\\!}_{ab}\times{\mathscr{C}\\!}_{bc})\cup{({\mathscr{C}\\!}_{bc}\times{\mathscr{C}\\!}_{ac})}\cup({\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{ab})\cup({\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{ac})\cup({\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{bc})\cup({\mathscr{C}\\!}_{abc}\times{\mathscr{C}\\!}_{abc})$,
the proof follows. ∎

Given a component $A$ of $G-V_{t}$, it is denoted by $t^{*}(A)$ the neighbor
of $t$ such that $\mathrm{Br}_{t}(A)=\mathrm{Br}_{t}(t^{*}(A))$.

######  Lemma 6.2.

If ${\mathscr{C}\\!}_{ij}\neq\emptyset$ for every $ij\in\\{ab,bc,ac\\}$, then
all cycles in ${\mathscr{C}\\!}$ intersect at a common vertex $t$-inside
$abc$.

###### Proof.

By Lemma 6.1, there exists a component $A\in\mathcal{A}_{t}(abc)$ such that
all cycles in ${\mathscr{C}\\!}$ pairwise intersect in $A$. Let
$t^{*}:=t^{*}(A)$. As ${\mathscr{C}\\!}_{ij}\neq\emptyset$ for every
${ij\in\\{ab,bc,ac\\}}$, there exists an $ij$-part $\bar{C}_{ij}$ of a cycle
in ${\mathscr{C}\\!}_{ij}$ such that all internal vertices of $\bar{C}_{ij}$
are in $A$, for every ${ij\in\\{ab,bc,ac\\}}$. Let $V_{t^{*}}=\\{a,b,c,f\\}$.
We proceed by induction on the number of vertices $t$-inside $abc$ different
from $a$, $b$, and $c$. If $f$ is the only vertex $t$-inside $abc$ different
from $a$, $b$, and $c$, then, as all cycles in ${\mathscr{C}\\!}$ pairwise
intersect in $A$, $f$ is in all cycles in ${\mathscr{C}\\!}$ and the proof
follows. So, there exist at least two vertices $t$-inside $abc$ different from
$a$, $b$, and $c$. Suppose by contradiction that there is no vertex in $A$
that belongs to all cycles in ${\mathscr{C}\\!}$. Then, there exists (at
least) one longest cycle in ${\mathscr{C}\\!}$ that does not contain $f$. Let
$C$ be such a cycle. Without loss of generality, assume that
$C\in{\mathscr{C}\\!}_{ab}$. The proof when $C\in{\mathscr{C}\\!}_{abc}$ is
similar.

Let $C$ be such a cycle. Without loss of generality, assume that
$C\in{\mathscr{C}\\!}_{ab}$. Let $C^{\prime}$ and $C^{\prime\prime}$ be the
two $ab$-parts of $C$, with $C^{\prime}$ $t$-inside $abc$. Let $A^{\prime}$ be
the component of $G-{V_{t^{*}}}$ where the internal vertices of $C^{\prime}$
lie. It is straightforward to see that
$A^{\prime}\in\mathcal{A}_{t^{*}}(\mathit{abf})$.

As every cycle in ${\mathscr{C}\\!}$ must intersect with $C$ in a vertex of
$A^{\prime}$, we can conclude that

$\mbox{ every cycle in }{\mathscr{C}\\!}\mbox{ }t^{*}\mbox{-}\mbox{ jumps
}\mathit{abf}.$ (1)

Note also that every cycle in ${\mathscr{C}\\!}_{ac}$ $t^{*}$-jumps
$\mathit{abf}$ at $\\{a,f\\}$, every cycle in ${\mathscr{C}\\!}_{bc}$
$t^{*}$-jumps $\mathit{abf}$ at $\\{b,f\\}$. We conclude that
${{\mathscr{C}\\!}}_{ij}^{{}^{\prime}}\neq\emptyset$ for every
$ij\in\\{ab,\mathit{bf},af\\}$, where ${{\mathscr{C}\\!}}^{{}^{\prime}}_{ij}$
is the collection of all longest cycles that 2-jumps $\mathit{abf}$ at
$\\{i,j\\}$.

Note that every vertex $t^{*}$-inside $\mathit{abf}$ is also $t$-inside $abc$.
Hence, as $c$ is $t$-inside $abc$ but not $t^{*}$-inside $\mathit{abf}$, by
induction hypothesis, there exists a common vertex to all cycles that
$t^{*}$-jump $\mathit{abf}$. Also, by (1), there exists a common vertex to all
cycles in ${\mathscr{C}\\!}$. Moreover, this vertex is $t$-inside $abc$.

This concludes the proof of the lemma. ∎

######  Corollary 6.3.

Let $\Delta$ be a triple of vertices in $V_{t}$. If $\mathrm{lct}(G){>1}$ and
for every pair of vertices $\\{i,j\\}$ in $\Delta$ there exists a longest
cycle that 2-jumps $\Delta~{}$ at $\\{i,j\\}$, then there exists a longest
cycle $C$ in $G$ such that either $C$ intersects $V_{t}$ at most once, or one
of the following possibilities is true:

  * $(i)$

$C$ is $t$-outside $\Delta$,

  * $(ii)$

$C$ is $t$-inside $\Delta$ and 2-intersects $\Delta$,

  * $(iii)$

$C$ is $t$-inside $\Delta$, 3-intersects $\Delta$, and is fenced by $\Delta$.

###### Proof.

Without loss of generality, let $\Delta=abc$. For every
${ij\in\\{ab,bc,ac\\}}$, let ${\mathscr{C}\\!}_{ij}$ be the collection of all
longest cycles in $G$ that 2-jump $abc$ at $\\{i,j\\}$. Let
${\mathscr{C}\\!}_{abc}$ be the collection of all longest cycles in $G$ that
3-jump $abc$. Let
${{\mathscr{C}\\!}={{\mathscr{C}\\!}_{ab}\cup{\mathscr{C}\\!}_{bc}\cup{\mathscr{C}\\!}_{ac}\cup{\mathscr{C}\\!}_{abc}}}$.
As ${{\mathscr{C}\\!}_{ij}\neq\emptyset}$ for every ${ij\in\\{ab,bc,ac\\}}$,
by Lemma 6.2, all longest cycles in ${\mathscr{C}\\!}$ intersect at a common
vertex, say $x$, that is $t$-inside $abc$. As ${\mathrm{lct}(G)>1}$, there
exists a longest cycle $C$ in $G$ that is not in ${\mathscr{C}\\!}$. Hence,
$C$ does not jump $abc$. We may assume that $C$ intersects $V_{t}$ at least
twice. If $C$ is $t$-outside $abc$, then $(i)$ holds and we are done. So,
assume that $C$ is $t$-inside $abc$. If $C$ 2-intersects $\Delta$, then $(ii)$
holds and we are done. Hence, we may assume that $C$ 3-intersects $\Delta$.

Suppose by contradiction that $C$ crosses $\Delta$. Let $C_{ab},C_{bc}$, and
$C_{ac}$ be the $abc$-parts of $C$. Let $A$ be the component of $G-\Delta$
where $x$ lies. As $C$ crosses $\Delta$, at least one of
$\\{C_{ab},C_{bc},C_{ac}\\}$, say $C_{ab}$, has all its internal vertices not
in $A$. Let ${D\in{\mathscr{C}\\!}_{ac}}$. Let ${F\in{\mathscr{C}\\!}_{bc}}$.
Let $D^{\prime}$ and $D^{\prime\prime}$ be the two $ac$-parts of $D$. Let
$F^{\prime}$ and $F^{\prime\prime}$ be the two $bc$-parts of $F$. As $D$ and
$F$ jump $abc$, we may assume that $D^{\prime}$ and $F^{\prime}$ are
$t$-inside $abc$, and that $D^{\prime\prime}$ and $F^{\prime\prime}$ are
$t$-outside $abc$. Moreover, as $D$ and $F$ contain $x$, and $x$ is in $A$,
both $D^{\prime}$ and $F^{\prime}$ have all its internal vertices in $A$. As
$C_{ab}$ has all its internal vertices not in $A$, $C_{ab}$ is internally
disjoint from $D^{\prime}$ and $F^{\prime}$. As $C$ is $t$-inside $abc$,
$C_{ab}$ is internally disjoint from $D^{\prime\prime}$ and
$F^{\prime\prime}$. Hence, ${D^{\prime}\cdot C_{ab}\cdot F^{\prime\prime}}$
and ${F^{\prime}\cdot C_{ab}\cdot D^{\prime\prime}}$ are both cycles, one of
them longer than $L$, a contradiction. ∎

##  7 Concluding remarks

In this paper, we showed all longest cycles in a 2-connected partial $3$-tree
intersect. This is not true for partial 4-trees. Indeed, there exists a
2-connected partial 4-tree $G$ given by Thomassen on 15 vertices [11, Figure
16] in which not all longest cycles intersect, but there is a pair of vertices
meeting all longest cycles Hence, we propose the following conjecture.

######  Conjecture 7.1.

For every 2-connected partial 4-tree, there exists a set of two vertices such
that all longest cycles has at least one vertex in this set.

## References

  * [1] H. L. Bodlaender.  A partial $k$-arboretum of graphs with bounded treewidth.  Theoretical Computer Science, 209(1):1–45, 1998.
  * [2] J. A. Bondy and U. S. R. Murty.  Graph theory, volume 244 of Graduate Texts in Mathematics.  Springer, New York, 2008.
  * [3] M.. Cerioli, C. G. Fernandes, R. Gómez, J. Gutiérrez, and P. Lima.  Transversals of longest paths.  Discrete Mathematics, 343(3):111717, 2020.
  * [4] S. F. de Rezende, C. G. Fernandes, D. M. Martin, and Y. Wakabayashi.  Intersecting longest paths.  Discrete Mathematics, 313:1401–1408, 2013.
  * [5] R. Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2010.
  * [6] C. G. Fernandes and J. Gutiérrez.  Hitting all longest cycles in a graph.  In Anais do XXXVII Congresso da Sociedade Brasileira de Computação, pages 87–90, 2017.
  * [7] J. L. Gross.  Embeddings of graphs of fixed treewidth and bounded degree.  ARS Mathematica Contemporanea, 7:379–403, 2014.
  * [8] J. Gutiérrez.  Transversals of longest cycles in chordal and bounded tree-width graphs.  In Michael A. Bender, Martín Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics, pages 558–571, Cham, 2018. Springer International Publishing.
  * [9] M. Heinz.  Tree-decomposition: Graph minor theory and algorithmic implications.  Master’s thesis, Technischen Universität Wien, 2013.
  * [10] A. S. Jobson, A. E. Kézdy, J. Lehel, and S. C. White.  Detour trees.  Discrete Applied Mathematics, 206:73–80, 2016.
  * [11] A. Shabbir, C. T. Zamfirescu, and T. I. Zamfirescu.  Intersecting longest paths and longest cycles: a survey.  Electronic Journal of Graph Theory and Applications, 1:56–76, 2013\.