The Isolation Lemma
Imagine you want to find a long cycle in a polyhedral graph G on n>=6
vertices, which is one of the classic problems on graphs. Here is a polyhedral graph with a red cycle that is
already quite long, but not longest (can you see why?).
A very natural approach to find a long cycle is to start with a small cycle C and attempt to extend it to a longer
one. This is exactly what we do in this new result
 about the
dynamics of cycles in polyhedra (joint-work with Jan Kessler).
more detail, let C be an isolating cycle (i.e. every component of G-V(C) consists of an isolated vertex) of G, such
as the one containing the horizontal line in the picture above. As long as C has less than 2(n+4)/3 (rounded down)
vertices, then C can always be extended to a larger isolating cycle L that still contains the vertices of the old
cycle. The picture shows how: replacing the horizontal line with the yellow fat path gives the next larger cycle
(here, exceeding the previous cycle by exactly the vertex vg
). The red arrows depict a discharging scheme
that reflects the length of C. This is a first step to capture the dynamics of cycles in polyhedra and can be used
to prove a conjecture about longes cycles in essentially 4-connected polyhedral graphs, and much more. Here is an
incomplete list of implications and remarks.
- Every essentially 4-connected polyhedral graph has an isolating Tutte cycle.
- Hence, by iterative application of the Isolation Lemma, these graphs contain an isolating Tutte cycle of
length at least 2(n+4)/3 (rounded down). This also gives an efficent algorithm computing such a long
cycle in time O(n 2).
- This bound is tight by a result of Fabrici, Harant and Jendrol.
- 16.04.2020, Thomas Madaras: This subresult on essentially
4-connected polyhedral graphs (without the algorithmic part) was also proven by Wigal and Yu in , using
- V(L) <= V(C)+3+d, where d is the number of faces of size 5 in G.
- This implies many results for the cycle spectrum of polyhedral graphs such as the following.
- This implies V(L) <= V(C)+2 for bipartite graphs. Hence, bipartite polyhedral graphs contain a cycle of
every cycle length between V(C) and 2(n+4)/3.
- This gives also hard evidence for the long used argument that faces of size five are key to obstruct long
cycles in many polyhedral graph classes (confer e.g. the Tutte fragment or the fragment of Faulkner and
Younger for classic examples).
- The Isolation Lemma is a polyhedral relative of Woodall’s Hopping Lemma  that allows cycle extensions
through common neighbors of cycle vertex pairs, even when none of these pairs have distance two in C. Despite
this relation, itmakes inherently use of planarity; in fact, it fails hard for non-planar graphs, as the
complete bipartite graphs show.
If you know more implications of the Isolation Lemma (or suspect one and want to work on it), let me know by
 Jan Kessler and Jens M. Schmidt. Dynamics of Cycles in Polyhedra I: The Isolation Lemma. arXiv
 Michael Wigal and Xingxing Yu. Large
cycles in essentially 4-connected graphs. arXiv
Douglas R. Woodall. The binding number of a graph and its Anderson number. Journal of Combinatorial Theory, Series
B, 15(3):225–255, 1973.