Cycle cover property and <f>CPP=SCC</f> property are not equivalent

Let <f>G</f> be an undirected graph. The Chinese postman problem (CPP) asks for a shortest postman tour in <f>G</f>, i.e., a closed walk using each edge at least once. The shortest cycle cover problem (SCC) asks for a family <f>C</f> of circuits of <f>G</f> such that each edge is in some circuit of <f>C</f> and the total length of all circuits in <f>C</f> is as small as possible. Clearly, an optimal solution of CPP cannot be greater than a solution of SCC. A graph <f>G</f> has the <f>CPP = SCC</f> property when the solutions to the two problems have the same value. Graph <f>G</f> is said to have the cycle cover property if for every Eulerian <f>1,2</f>-weighting <f>w : E(G) ↦ {1,2}</f> there exists a family <f>C</f> of circuits of <f>G</f> such that every edge <f>e</f> is in precisely <f>we</f> circuits of <f>C</f>. The cycle cover property implies the <f>CPP = SCC</f> property. We give a counterexample to a conjecture of Zhang (J. Graph Theory 14(5) (1990) 537; Ann. Discrete Math. 55 (1993) 183; Integer Flows and Cycle Covers of Graphs, Marcel Dekker, New York, 1997; Deans, Graph Structure Theory, AMS, Providence, RI, 1993, pp. 677–688) stating the equivalence of the cycle cover property and the <f>CPP = SCC</f> property for 3-connected graphs. This is also a counterexample to the stronger conjecture of Lai and Zhang, stating that every 3-connected graph with the <f>CPP = SCC</f> property has a nowhere-zero 4-flow. We actually obtain infinitely many cyclically 4-connected counterexamples to both conjectures. [Copyright &y& Elsevier]