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 De lta(G) circuits of the cover, where Delta(G) is the maximum degree of G. This paper affirms Pyber's conjecture by establishing an intermedia te result, namely that every bridgeless graph G has a circuit cover su ch that each vertex v of G is contained in at most d(v) circuits of th e cover if d(v) greater than or equal to 3 and in at most three circui ts of the cover if d(v) = 2. Our proofs rely on results on integer flo ws. (C) 1995 Academic Press, Inc.