# 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?

#### Solutions Collecting From Web of "Prove a graph Containing $2k$ odd vertices contains $k$ distinct trails"

I see my problem, I’m thinking in terms of simple graphs, but this theorem is thinking in terms of multigraphs. If you add an edge between 3 and 1 and then between 1 and 1 then all vertices become even and there is an Eulerian cycle in the graph. Take away the new edges and you get back a graph in which each edge between odd degree vertices becomes it own trail.

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.