Statement: Given a connected graph with all edges coloured in one of two colours (red and black), so that for each vertex the number of incident red edges is equal to the number of black edges.
Proof: there is a color-alternating path between any pair of vertexes.
I had some thoughts on this problem in context of Euler cycle (I can even prove it in the other direction), also have found such theorem:
Theorem (2 colors): A 2-edge colored graph has an alternating Euler cycle if and only if the red degree=blue degree for every vertex
May be someone knows how to prove it ?