We have connected undirected graph with colored edges in two way (green or blue). And also each vertex have the same number of green and blue edges. How to prove that there are alternate colored (green-blue) path between any two nodes?

  • $\begingroup$ Not an expert in this topic but maybe this could be a start. For every blue vertex into a node there is a green one leaving. $\endgroup$ – avz2611 Nov 29 '17 at 13:10

Find an Eulerian path through alternating green/blue edges, and we'll be done.

Why is that possible? Well, start from any edge at any direction; at every vertex, choose an unused edge of opposite color (there must be one, for initially there were as much green as blue edges at any vertex, and this condition remains true even after we pass through it). So our procedure will never "paint itself into a corner"; nor will it be infinite, since there are only so many edges. How will it end, then?

The only remaining option is: it will run into its beginning via an edge of opposite color. (If it will run into the beginning via an edge of the same color, that's not a problem; we now have two unused edges of opposite color at that vertex, so we'll just use any of them to leave and continue.) So we'll end up with an alternating cycle.

Sure, our cycle is not necessarily Eulerian: it could have skipped some edges. But then the remaining graph (the one consisting of unused edges) has the same property of green=blue at each vertex, so let's just repeat the procedure over and over again, until all edges are included in cycles. Then join the cycles.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.