加载中…
Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but there are 3-connected -vertex planar graphs whose longest cycles have length . On the other hand, Jackson and Wormald in 1992 proved that an essentially 4-connected -vertex planar graph contains a cycle of length at least , which was recently improved to by Fabrici {\it et al}. In this paper, we improve this bound to $\lceil (2n+6)/3\rceiln\ge 6$, which is best possible, by proving a quantitative version of a result of Thomassen on Tutte paths.

生成讲解博客的中文版本

生成AI智能校验的中文版本