A cycle C of a graph G is isolating if every component of G-V(C) is a single vertex. We show that isolating cycles in polyhedral graphs can be extended to larger ones: every isolating cycle C of length 8 \leq |E(C)| < \left \lfloor 2{3}(|V(G)|+ 3)\right \rfloor implies an isolating cycle C' of larger length that contains V(C). By ``hopping'' iteratively to such larger cycles, we obtain a powerful and very general inductive motor for proving and computing long cycles (we will give an algorithm with running time O(n^2)). This provides a method to prove  lower bounds on  Tutte cycles, as C' will be a Tutte cycle of G if C is. We also prove that E(C') \leq E(C)  +3 if G does not contain faces of size five, which gives a new tool for proving results about cycle spectra and evidence that these face sizes obstruct long cycles . As a sample application, we test our motor on a conjecture on essentially 4-connected graphs. A planar graph is \emph{essentially 4-connected} if it is 3-connected and every of its 3-separators is the neighborhood of a single vertex. Essentially 4-connected graphs have been thoroughly investigated throughout literature as the subject of Hamiltonicity studies. Jackson and Wormald proved that every essentially 4-connected planar graph G on n vertices contains a cycle of length at least \frac{2}{5}(n+2), and this result has recently been improved multiple times, culminating in the lower bound \frac{5}{8}(n+2). However, the  best known upper bound is given by an infinite family of such graphs in which every graph G on n vertices has no cycle longer than\left \lfloor \frac{2}{3}(n+4) \right \rfloor ; this upper bound is still unmatched. Using isolating cycles, we improve the lower bound to match the upper (up to a summand +1). This settles the long-standing open problem of determining the circumference of essentially 4-connected planar graphs .
A cycle C of a graph G is isolating if every component of G-V(C) is a single vertex. We show that isolating cycles in polyhedral graphs can be extended to larger ones: every isolating cycle C of length 6 \leq |E(C)| < \left \lfloor 2{3}(|V(G)|+ 4)\right \rfloor implies an isolating cycle C' of larger length that contains V(C). By "hopping" iteratively to such larger cycles, we obtain a powerful and very general inductive motor for proving long cycles and computing them (we will give an algorithm with quadratic running time). This is the first step towards the so far elusive quest of finding a universal induction that captures longest cycles of polyhedral graph classes. Our motor provides also a method to prove linear lower bounds on the length of Tutte cycles, as C' will be a Tutte cycle of G if C is. We prove in addition that | E(C') | \leq | E(C) | +3 if G contains no face of size five, which gives a new tool for results about cycle spectra , and provides evidence that faces of size five may obstruct long cycles in many graph classes. We test our motor on the following conjecture about essentially 4-connected graphs. A planar graph is \emph{essentially 4-connected} if it is 3-connected and every of its 3-separators is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4-connected planar graph G on n vertices contains a cycle of length at least \frac{2}{5}(n+2), and this result has recently been improved multiple times, culminating in the lower bound \frac{5}{8}(n+2). However, the currently best known upper bound is given by an infinite family of such graphs in which no graph G contains a cycle that is longer than\left \lfloor \frac{2}{3}(n+4) \right \rfloor ; this upper bound is still unmatched. Using isolating cycles, we improve the lower bound to match the upper . All our results are tight .
R
8
6
R
3)
4)
R
``hopping''
"hopping"
R
and computing long cycles
long cycles and computing them
R
running time O(n^2)). This provides
quadratic running time). This is the first step towards the so far elusive quest of finding a universal induction that captures longest cycles of polyhedral graph classes. Our motor provides also
A
linear
A
the length of
R
also prove that
prove in addition that |
R
\leq
| \leq |
A
|
R
does not contain faces
contains no face
D
proving
R
and evidence that these face sizes
, and provides evidence that faces of size five may
R
. As a sample application, we
in many graph classes. We
R
a conjecture on
the following conjecture about
D
Essentially 4-connected graphs have been thoroughly investigated throughout literature as the subject of Hamiltonicity studies.
A
currently
R
every graph G on n vertices has no cycle longer than
no graph G contains a cycle that is longer than
R
(up to a summand +1). This settles the long-standing open problem of determining the circumference of essentially 4-connected planar graphs
. All our results are tight