Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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?

share|cite|improve this answer
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. – sdadffdfd Oct 31 '10 at 6:41
my mistake, I misread the question. Try inducting on the number of red/blue edges at a vertex. – Harry Stern Oct 31 '10 at 7:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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