6
$\begingroup$

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?

  • 0
    @Robert : I am not getting your statement that ** when these edges are droped out again, $T$ falls into $k$ seprate trails covering the edges in the orignal graph.2017-07-25

2 Answers 2

5

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.

  • 0
    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.2012-01-29
1

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.

  • 0
    Your inductive step may also disconnect the graph: consider removing only the middle edge of an H-shaped tree on six vertices.2018-07-08