# Prove a graph Containing $2k$ odd vertices contains $k$ distinct trails

I'm reading the book Graphs and Their Uses which contains the following theorem and proof:

THEOREM 2.3. A connected graph with 2k odd vertices contains a family of k distinct trails which, together, traverse all edges of the graph exactly once.

PROOF. Let the odd vertices in the graph be denoted by in some order.

$a_1,a_2,\dots,a_k$ and $b_1,b_2,\dots,b_k$

When we add the $k$ edges $a_lb_l, a_2b_2 ,\dots, a_kb_k$ to the graph, all vertices become even and there is an Eulerian trail T. When these edges are dropped out again, T falls into k separate trails covering the edges in the original graph.

However this doesn't seem to make sense since in the graph whose vertices have degrees 3, 1, 1, 1 there is no way to add 2 edges in such a way that the degree of all odd vertices becomes even.

What am I missing here?

-
Do you allow multiple edges or not? – Srivatsan Jan 29 '12 at 9:28
Yes, I just figured out my problem - see below. – Robert S. Barnes Jan 29 '12 at 9:31

Exactly. (+1, but I don't have the votes at the moment.) It is most natural to allow multiple edges in this context. But if you feel uncomfortable about this, then you could add dummy vertices in the middle of edges: e.g., an edge $uv$ will become a pair of edges $ux$ and $xv$ where $x$ is a dummy vertex private to the edge. – Srivatsan Jan 29 '12 at 9:33
Here's an alternative proof. Take an odd vertex, and construct a trail from that to another odd vertex. Remove the edges of that trail; the resulting graph has $2k-2$ odd vertices. Repeat.