On spanning subgraphs of 4-connected planar graphs (Q1262872)

A figure-eight based at v is a pair of cycles having only the single vertex v in common. The author proves that every 4-connected planar graph has a spanning figure-eight subgraph based at v for any \(v\in V(G)\). He provides examples showing that the hypothesis 4-connected is necessary, as is the planarity hypothesis. The author is motivated both by the well- known theorem of Tutte that every 4-connected planar graph is Hamiltonian and by a question on Hamiltonian decompositions. He also shows that finding this figure-eight subgraph is computationally equivalent to finding the Hamiltonian cycle given by Tutte's theorem. It follows that there is an \(O(n^ 3)\)-time algorithm for this problem.