SHORTEST CIRCUIT COVERS AND POSTMAN TOURS IN GRAPHS WITH A NOWHERE ZERO 4-FLOW

Let G be a graph with a nowhere zero 4-flow. It is shown that the length of a shortest circuit cover of E(G) is equal to the length of a shortest postman tour of E(G). Using this result an efficient algorithm for constructing shortest circuit covers for graphs that possess two disjoint spanning trees is obtained. It is also deduced that if H is a 2m-edge connected graph, m ≥ 2, then there exists a circuit cover of E(H) of length at most |E(H)|+min {|E(H)|/(2m+1), |V(H)|-1} and that if G has a nowhere zero 4-flow, then there exists a circuit cover of V(G) of length at most 2|V(G)|-2. Finally, it is shown that the equivalence between shortest circuit covers and postman tours may be extended to certain binary matroids.