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?).

In 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 v

- 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 [2], using different methods.

- 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

- 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).

- This implies many results for the cycle spectrum of polyhedral graphs such as the following.

- The Isolation Lemma is a polyhedral relative of Woodall’s Hopping Lemma [3] 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 mail!

[1] Jan Kessler and Jens M. Schmidt. Dynamics of Cycles in Polyhedra I: The Isolation Lemma. arXiv, 18.02.2020.

[2] Michael Wigal and Xingxing Yu. Large cycles in essentially 4-connected graphs. arXiv, 21.03.2020.

[3] Douglas R. Woodall. The binding number of a graph and its Anderson number. Journal of Combinatorial Theory, Series B, 15(3):225–255, 1973.