Circuit Coverings of Graphs and a Conjecture of Pyber

An equivalent statement of the circuit double cover conjecture is that every bridgeless graph G has a circuit cover such that each vertex v of G is contained in at most d(v) circuits of the cover, where d(v) is the degree of v. Pyber conjectured that every bridgeless graph G has a circuit cover such that every vertex of G is contained in at most Δ(G) circuits of the cover, where Δ(G) is the maximum degree of G. This paper affirms Pyber′s conjecture by establishing an intermediate result, namely that every bridgeless graph G has a circuit cover such that each vertex v of G is contained in at most d(v) circuits of the cover if d(v) ≥ 3 and in at most three circuits of the cover if d(v) = 2. Our proofs rely on results on integer flows.