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 ?


marked as duplicate by Misha Lavrov, Rolf Hoyer, Leucippus, Parcly Taxel, Rohan Dec 9 '17 at 5:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Have you tried to connect this issue with a bipartited graph ? $\endgroup$ – Jean Marie Dec 8 '17 at 18:12
  • 1
    $\begingroup$ @JeanMarie, I tried, but there is no evident proof its bipartite, and furthermore its not bipartite in sense that one color leads to one component and the other one to the left one $\endgroup$ – Dmitriy Baranov Dec 8 '17 at 21:26