Cycle cover property and \(\text{CPP}=\text{SCC}\) property are not equivalent (Q1861230)

The Chinese postman problem (CPP) asks for a shortest postman tour in a graph. The shortest cycle cover problem (SCC) asks for a family \(\mathcal C\) of circuits in a graph \(G\) such that each edge of \(G\) belongs to a circuit of \(\mathcal C\) and the total length of all circuits in \(\mathcal C\) is as small as possible. A graph has the CPP = SCC property if the solutions of the two problems have the same value. A graph \(G\) has the cycle cover property if for every Eulerian \((1,2)\)-weighting \(w:E(G)\rightarrow\{1,2\}\), there exists a family \(\mathcal C\) of circuits in \(G\) such that every edge \(e\) is in precisely \(w_e\) circuits of \(\mathcal C\). The cycle cover property implies the CPP = SCC property. The author presents counterexamples to a conjecture of \textit{C.-Q. Zhang} [J. Graph Theory 14, 537-546 (1990; Zbl 0729.05041)] stating the equivalence of the cycle cover property and the CPP = SCC property for 3-connected graphs.