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). 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 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 different methods.
• 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 mail!

 Jan Kessler and Jens M. Schmidt. Dynamics of Cycles in Polyhedra I: The Isolation Lemma. arXiv, 18.02.2020.
 Michael Wigal and Xingxing Yu. Large cycles in essentially 4-connected graphs. arXiv, 21.03.2020.
 Douglas R. Woodall. The binding number of a graph and its Anderson number. Journal of Combinatorial Theory, Series B, 15(3):225–255, 1973.