Problem
COM-B2-M05-P013 A Criterion for Signs on a Connected Graph
Signs \(+\) and \(-\) are written at the vertices of a connected graph. In one move, choose an edge and change the signs at both endpoints. Prove that all signs can be made positive if and only if the initial number of negative signs is even.
Necessity comes from the product of signs. For sufficiency, use a spanning tree and remove negative signs from leaves.
Necessity: one move changes two signs, so the parity of the number of negative signs is preserved. If in the end there are \(0\) negative signs, then initially their number must be even.
For sufficiency, take a spanning tree and choose a root. Process leaves other than the root. If a leaf has a minus sign, apply the move to the edge joining the leaf to its parent; the leaf becomes positive, while the parent changes sign. If the leaf is positive, do nothing. After that, the leaf need not be touched again.
This makes all vertices except possibly the root positive. The parity of the number of negative signs has been preserved, and at the final stage there are no negative signs outside the root. Therefore the root is also positive. Hence all signs can be made positive.
A strong problem: besides the invariant, a constructive sufficiency proof is required.