An old exercise from my graph theory notes has the following exercise:
Let $G$ be a connected graph with an even number of edges and with a non-zero even number $2n$ of vertices of odd degree. Then $G$ is an edge-disjoint union of $n$ trails of even length.
I'm having problems with the even-length part of the conclusion. I can show that we have a disjoint trails corresponding to pairs of odd vertices:
Let $x_1,x_2,\dots,x_n$ and $y_1,y_2,\dots,y_n$ be the odd vertices of the graph. By adding the edges $x_l y_l, x_2 y_2 ,\dots, x_n y_n$ to the graph, we have a new graph where all vertices have even degree. This implies the new graph can be expressed as the edge-disjoint union of circuits. When the added edges are removed from the new graph, we have disjoint trails in the original graph.
Are these trails, that I got, those that are of even length? How do I show the even length part?