Cycle Covers of Planar \(3\)-Connected Graphs

D.W. Barnette1
1 Department of Mathematics Univeristy of California Davis, CA 95616

Abstract

We show that the edges of a planar 3-connected graph with \(n\) vertices can be covered by at most \([(n + 1)/{2}]\) cycles. This proves a special case of a conjecture of Bondy that the edges of a 2-connected graph can be covered by at most \((2n – 1)/{3}\) cycles.