Let G=(V,E) be a connex graph. Color it's edges randomly with red/blue.

-prove that there exists an Eulerian circuit, without any two adjacent edges of the same color.. only if for any v vertex of G the number of incident blue edges is equal to the number of red ones.

-if G is complete and x,y,z are three distinct vertices prove that, if there is a path without consecutive edges of the same color from x to y passing through z, then there is a path with the same property that has xz as the first edge or zy as the last edge.

Please help me by at least providing some suitable references that may help me solve this problem.

Thank you in advance.


1 Answer 1


These probably should be comments but I don't have sufficient reputation.

Hint for problem 1: If there are an equal number of red and blue edges at each vertex, what does that tell you about the parity of the degree of each vertex?

Hint for problem 2: If you have a path from x to y passing through z, can you use the fact that the graph is complete to find another path that fits the alternating condition?

  • $\begingroup$ hint2 is ok. Not sure about hint 1.. I think I'll still have to prove that my path has no consecutive edges of the same color. $\endgroup$
    – sdadffdfd
    Oct 31, 2010 at 6:41
  • $\begingroup$ my mistake, I misread the question. Try inducting on the number of red/blue edges at a vertex. $\endgroup$ Oct 31, 2010 at 7:54

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.