COVERING GRAPHS BY CYCLES

Let G be a bridgeless graph with m edges and n vertices. It is proved that the edges of G can be covered by circuits whose total length is at most m + (r/r - 1)(n - 1), where r is the minimum length of an even circuit (of G) of length at least 6 (r = infinity, if there is no such circuit). The proof suggests a polynomial-time algorithm for constructing such a cover.