On cuts and cycles in planar graphs

A partition is said to be balanced if the sizes of the sets in the partition differ by at most one. The size of a graph partition is the number of edges that have their end-vertices in different parts of the partition. A folklore conjecture claims that, for any planar graph G on n vertices, a minimum balanced bipartition of G has size at most n. We confirm this conjecture. A Hamiltonian graph is one that contains a cycle passing through all its vertices. A pancyclic graph is one that contains cycles of all possible lengths. In 1971-72, Bondy made the metaconjecture that, barring a simple family of exceptions, any nontrivial condition on a graph that implies that the graph is Hamiltonian also implies that the graph is pancyclic. This meta-conjecture implies, as a special case, that every 4-connected planar graph is pancyclic. Identifying 4-connected planar graphs that do not contain a 4-cycle as a family of exceptions, Malkevitch conjectured that a 4-connected planar graph is pancyclic if it contains a 4-cycle. We show that every 4-connected planar graph contains at least ⌈n/2⌉ + 1 cycles of pairwise distinct lengths. We also show that every 4-connected planar graph not containing a 4-cycle contains at least ⌈5n/6 ⌉ + 2 cycles of pairwise distinct lengths.