Prove edges of G can be colored by red and blue so that every vertex has the same number of red and blue edges adjacent to it. The problem is given as follow:

Let G be a connected graph having an even number of edges such that all the degrees are even. Prove that the edges of G can be colored by red and blue in such a way that every vertex has the same number of red and blue edges adjacent to it.

My approach is:

Since all degrees are even, then G is not a tree and contains only cycles. This also implies two cycles cannot share a common edge, otherwise one vertex has odd degree. G has even number edges indicates it has even number of cycles which share common vertices. Therefore, G can be colored by red and blue in such a way that every vertex has the same number of red and blue edges adjacent to it.

I don't know if I miss something needs to be clarify in this proof...

My new approach:

G contains a Eulerian circuit because all the degrees are even. Traversing the circuit from a vertex u and coloring the edges blue, red, blue, red....as a sequence. Because G has even number of edges, it has even number of blue and red edges; hence, the color of first edge starting from vertex u is different from the last edge goes back to starting point. Therefore, QED 

 A: Since it was quite some time ago that I gave a hint in the comments above and the OP has not returned to say that he has figured it out and no other answer has been posted, I will give an extended hint (practically a full solution):


 Depending on strictness and definitions, one might also want to concern yourself with the case that $G$ has exactly one vertex (or even exactly zero vertices).  There is exactly one graph with exactly one vertex, and it has zero edges and can trivially be seen to satisfy all of the conditions.  It is common to see graph theory problems specify that we are interested only in proving results for graphs with at least $n\geq 2$ vertices since the one-vertex graph is so dull and uninteresting.

As $G$ is connected and has every vertex with even degree, there exists an Eulerian circuit (a walk which possibly reuses vertices that starts and ends in the same place which uses every edge exactly once).
Take any such Eulerian circuit with starting and ending point $x$ (where $x$ is a vertex of $G$) and alternately color the edges along the circuit red and blue.
It remains to show the following two things:


*

*Why does every vertex other than $x$ have as many red edges as blue edges?

*Why does $x$ have as many red edges as blue edges?

 Why is the last edge in the circuit a different color than the first edge in the circuit?  (Have we used all of the hypotheses yet in our proof?)

$~$

 Would $x$ have had as many red edges as blue edges if the number of edges in the graph total was in fact odd?  What are the colors of the first and last edge in the circuit in that case?

