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 [1] 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.

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.