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!