Take the 2-minute tour ×
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.

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|improve this question
2  
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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.