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?

  • 1
    $\begingroup$ Do you allow multiple edges or not? $\endgroup$ – Srivatsan Jan 29 '12 at 9:28
  • $\begingroup$ Yes, I just figured out my problem - see below. $\endgroup$ – Robert S. Barnes Jan 29 '12 at 9:31
  • $\begingroup$ @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. $\endgroup$ – user120386 Jul 25 '17 at 11:47

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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Srivatsan Jan 29 '12 at 9:33
  • $\begingroup$ @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. $\endgroup$ – Robert S. Barnes Jan 29 '12 at 9:38
  • $\begingroup$ What do you mean by "a minimum of k distinct trails"? (And is your example a star with 3 leaves?) $\endgroup$ – Srivatsan Jan 29 '12 at 9:39
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Tomer Amir Mar 14 '14 at 0:23
  • $\begingroup$ Your inductive step may also disconnect the graph: consider removing only the middle edge of an H-shaped tree on six vertices. $\endgroup$ – Ravi Fernando Jul 8 '18 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.