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!

  • 2
    $\begingroup$ 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? $\endgroup$ – Douglas S. Stones Apr 3 '13 at 23:58
  • $\begingroup$ Thanks for everyone's advice and hints! I understand now. $\endgroup$ – Luke8ball Apr 4 '13 at 0:46

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.

  • $\begingroup$ Did you intend your $C$ to be the Eulerian circuit in $APvCvPB$? A bit confusing since $C$ is already a vertex name. $\endgroup$ – EuYu Apr 4 '13 at 0:27
  • $\begingroup$ Fixed. Thanks for pointing this out. $\endgroup$ – A.S Apr 4 '13 at 0:37

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.