Tutte cycles in circuit graphs (Q1379828): Difference between revisions

A Tutte cycle in a graph \(G\) is a cycle \(C\) such that each component \(H\) of \(G-C\) has at most three attachments on \(C\), i.e. at most three vertices of \(C\) have neighbours in \(H\). In the present paper, the authors prove that each 3-connected planar graph \(G\) contains a Tutte cycle \(C\) such that each component of \(G-C\) has less than \(| V(G) |/3\) vertices. This improves a former result of B. Jackson and N. C. Wormald who obtained the upper bound \(| V(G) |/2\). Such kinds of results are useful for obtaining lower bounds for the length of longest cycles in 3-connected planar graphs.