Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Problem: Assume G = (V,E) is a connected graph with 4 vertices of odd degree. Show G can be decomposed into 2 edge-disjoint simple (no edge is repeated) walks.

Attempt at a Solution: Suppose the four vertices of odd degree are A, B, C, and D.

  • Find a path from A to B. Since no vertices are repeated, no edges are repeated.
  • Delete the edges from that path. Now A and B have even degree.
  • Now C and D are the only edges with odd degree; find a Euler walk from C to D. This uses up all the remaining edges, none of which are repeated.

I'm a little confused as to whether or not this is valid. Thanks for any comments/suggestions!

share|cite|improve this question
It seems like a natural enough approach, but you should perhaps be a bit more careful in places. E.g. What if G is disconnected after the removal of the path from A to B? – Douglas S. Stones Apr 3 '13 at 23:58
Thanks for everyone's advice and hints! I understand now. – Luke8ball Apr 4 '13 at 0:46
up vote 3 down vote accepted

This proof is very close, but it is not valid yet. As mentioned by Douglas Stones, you must find a way to make sure that your path does not disconnect the graph.

Hint: Make the $A,B$-trail maximal. Why would this not disconnect the graph?

Suppose maximal trail $P$ disconnects the graph. Then, $C$ and $D$ must be in the same component by the handshake lemma. Since the other component has all vertices with even degree, it must contain an Eulerian circuit $E$. Moreover, it must contain at least one vertex $v$ in the trail $P$. Then $A P v E v P B$ is a longer trail, which is a contradiction.

share|cite|improve this answer
Did you intend your $C$ to be the Eulerian circuit in $APvCvPB$? A bit confusing since $C$ is already a vertex name. – EuYu Apr 4 '13 at 0:27
Fixed. Thanks for pointing this out. – Andrew Salmon Apr 4 '13 at 0:37

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.