Covering Graphs by Cycles
Genghua Fan · SIAM Journal on Discrete Mathematics · 1992
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 = \infty $, if there is no such circuit). The proof suggests a polynomial-time algorithm for constructing such a cover.