On April 26, 2024, Ryan Martin — one of the most renowned names in combinatorics, from Iowa State University — visited our campus to give a talk on counting cycles in planar graphs. He showed several results on short cycles, long cycles, the bounds that govern them. It was a beautiful talk.
Afterward, my advisor Zhiyu Wang had a question. Not for Ryan Martin — for himself, and eventually for me. What if we add a connectivity condition to the planar graphs? Will the bounds change? And if so, what kind of graphs actually achieve the bound?
That question became my dissertation.
We began by investigating $K_{1,t}$, $K_{2,t}$, and $C_5$. Alon and Caro had already given a complete characterization of the counts of $K_{1,t}$ and $K_{2,t}$ in planar graphs. With the connectivity condition (4,5-connectivity for $K_{1,t}$ and 4-connectivity for $K_{2,t}$) in hand, we were able to identify the bounds and the extremal graphs relatively quickly.
However, writing the proofs took a long time. In graph theory, one of the guiding principles is to minimize the amount of structural analysis — and especially the number of cases in a proof. The route we had originally agreed upon was leading us straight into a labyrinth of structural analysis, case after case branching into more cases.
Thanks to my advisor's induction idea, we scrapped the original proof entirely and rewrote a ten-page proof from scratch. It was a humbling experience — and an important lesson about when to abandon a path, even one you've already walked a long way down.
Our next target was $C_5$ — counting 5-cycles in planar graphs under a connectivity condition. We started by reading the paper by Győri et al. (arXiv:1909.13532) on counting $C_5$ in planar graphs. From there, we realized we needed to apply an inductive argument to the 5-connected case.
Induction on graphs comes with a fundamental constraint: whatever operation you use to reduce the graph must not destroy the properties you're working with. Maintaining planarity is trivial — standard operations preserve it easily. Preserving 5-connectivity was a different matter entirely.
We tried everything: contracting edges, deleting vertices, re-triangulation, various combinations of all three. Every approach broke 5-connectivity in some case we hadn't anticipated. Month after month, each promising idea collapsed under examination. It was one of the most frustrating stretches of my PhD.
The rescue came from an unexpected direction. Xiaonan Liu — then a postdoc at Vanderbilt University, and also my advisor's wife — found a clever trick: replace a subgraph with a smaller one that preserved 5-connectivity exactly. Once that piece was in place, the proof fell together. The paper was completed within a few months.