Small Circuit Double Covers of Cubic Multigraphs

Let G be a two-connected graph. A family F of circuits of G is called a circuit double cover (CDC) if each edge of G is contained in exactly two circuits of F. In this paper, we show that if a simple cubic graph G (G ≠ K4) of order n has a CDC, then G has a CDC containing at most n/2 circuits. This result establishes the equivalence of the circuit double cover conjecture (due to Szekeres, Seymour) and the small circuit double cover conjecture (due to Bondy) for any cubic graph. Actually, a stronger result is obtained in this paper for all loopless cubic graphs. Another result in this paper establishes an upper bound on the size of any CDC of a cubic graph.