# Decomposing a Connected Graph into Walks

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!

-
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

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.
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