Note that if a signed Eulerian graph contains an odd number of negative edges, it must contain an unbalanced cycle.

- [x.sub.n-1] - [x.sub.0] denote a signed Eulerian graph formed by the union of ([x.sub.i], [x.sub.i+1])-paths where i [member of] [Z.sub.n].

(i) [v.sub.a] - [v.sub.b] - w - [v.sub.a], which is the symmetric difference of [C.sub.b] and C', is an unbalanced Eulerian graph, so it contains an unbalanced cycle.

(ii) [v.sub.c] - [v.sub.d] - w - [v.sub.c], which is the symmetric difference of [C.sub.l] and C', is an unbalanced Eulerian graph, so it contains an unbalanced cycle.

(ii) [v.sub.a] - [v.sub.b] - [v.sub.c] - [v.sub.d] - w - [v.sub.a], which is the symmetric difference of Cl and the symmetric difference of C' and Cb, is an unbalanced Eulerian graph, so it contains an unbalanced cycle.

Then the symmetric difference of [C.sub.l] and C is an unbalanced Eulerian graph that contains an unbalanced cycle of length shorter than the length of the critical cycle [C.sub.l], a contradiction.

Polynomial-time algorithms are known for switching to a triangle-free graph [Hay96, HHW02], to a claw-free graph [JK08], to an

eulerian graph [HHW02], to a bipartite graph [HHW02], and to a planar graph [EHHR00a, Kra03].