Relative length of longest paths and cycles in 3-connected graphs (Q2746207)

Let \(G\) be a 3-connected graph on \(n\) vertices. Denote by \(p(G)\) and \(c(G)\) the orders of a longest path and a longest cycle in \(G\), respectively. If, for every independent set \(S\) of 4 vertices, \(\sum _{x \in S} \text{ deg}_G x \geq (3/2)n+1\), the authors show that \(p(G)-c(G) \leq 1\). They demonstrate the usefulness of this result by deriving various lower bounds for \(c(G)\) and other properties of longest cycles of \(G\).