5
$\begingroup$

An old exercise from my graph theory notes has the following exercise:

Let $G$ be a connected graph with an even number of edges and with a non-zero even number $2n$ of vertices of odd degree. Then $G$ is an edge-disjoint union of $n$ trails of even length.

I'm having problems with the even-length part of the conclusion. I can show that we have a disjoint trails corresponding to pairs of odd vertices:

Let $x_1,x_2,\dots,x_n$ and $y_1,y_2,\dots,y_n$ be the odd vertices of the graph. By adding the edges $x_l y_l, x_2 y_2 ,\dots, x_n y_n$ to the graph, we have a new graph where all vertices have even degree. This implies the new graph can be expressed as the edge-disjoint union of circuits. When the added edges are removed from the new graph, we have disjoint trails in the original graph.

Are these trails, that I got, those that are of even length? How do I show the even length part?

  • 0
    Just edited the question. $G$ has $2n$ odd vertices.2012-08-17
  • 0
    reading from my notes: $G$ is connected with $2n$ odd vertices ($n>1$) and of even size.2012-08-17
  • 1
    How do you know the edges $x_{i}y_{i}$ don't already exist?2013-09-25

1 Answers 1