# 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

## 2 Answers

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.

-
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
@Srivatsan There is something I'm still not getting. Why k distinct trails and not a minimum of k distinct trails. For instance in my 3,1,1,1 example there are actually 3 possible distinct trails not 2. It would seem that the number of distinct trails is equal to the number of edges between vertices. They must have intended in the Theorem the minimal number of trails to cover the graph. –  Robert S. Barnes Jan 29 '12 at 9:38
What do you mean by "a minimum of k distinct trails"? (And is your example a star with 3 leaves?) –  Srivatsan Jan 29 '12 at 9:39
I think the intention in the proof must have been to show the minimum number of distinct trails needed to cover all edges in the graph without using any edge twice. –  Robert S. Barnes Jan 29 '12 at 9:44

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.

-
this doesn't promise that you will travel on all the edges in the graph by itself... it is not mentioned directly in the question, but you might have some vertices with an even degree. –  Tomer Mar 14 at 0:23