Circumference of essentially 4-connected planar triangulations

Igor Fabrici, Jochen Harant, Samuel Mohr, Jens M. Schmidt

Published 2021-01-11Version 1

A $3$-connected graph $G$ is essentially $4$-connected if, for any $3$-cut $S\subseteq V(G)$ of $G$, at most one component of $G-S$ contains at least two vertices. We prove that every essentially $4$-connected maximal planar graph $G$ on $n$ vertices contains a cycle of length at least $\frac{2}{3}(n+4)$; moreover, this bound is sharp.