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?

  • $\begingroup$ Just edited the question. $G$ has $2n$ odd vertices. $\endgroup$ Aug 17 '12 at 9:40
  • $\begingroup$ reading from my notes: $G$ is connected with $2n$ odd vertices ($n>1$) and of even size. $\endgroup$ Aug 17 '12 at 9:53
  • 1
    $\begingroup$ How do you know the edges $x_{i}y_{i}$ don't already exist? $\endgroup$ Sep 25 '13 at 0:41

I'll solve the problem in three steps:

(1) First I'll show that any connected graph $G$ with an even number, $2m$, of edges is the edge-disjoint union of $m$ trails of length 2.

(2) If $G$ is a graph with even number of edges and $2n$ vertices of odd degree, and the edges is an edge-disjoint union of trails, it is possible to successively concatenate trails until we are left with $n$ trails all starting and ending in odd degree vertices plus any number of circular trails.

(3) We can merge the circular trails with the $n$ linear trails so as to end up with only $n$ trails.

The reason $n\ge1$ is required is that for $n=0$, i.e. all vertices have even degree, step (3) will end with a single circular trail (an Euler path) with no linear trail to merge it to.

1: Splitting $G$ into 2-trails

Proof goes by induction (or descent): i.e. I reduce the graph to one or more graphs with a smaller number of edges.

Pick a vertex, $x$ of degree 2 or higher: one must exist, or $G$ would have two vertices and one edge only. Decompose $G$ into components $G_1,\ldots,G_k$ which correspond to the connected components after removing $x$ from $G$, but with the vertec $x$ and edges between $x$ and vertices of each $G_i$ included in $G_i$: i.e. two vertices are in the same component if the can be connected by a path not passing through $x$. Each edge of $G$ is then in exactly one of the $G_i$.

If there is only one component, we can pick any two edges at $x$, say $xy$ and $xz$ for vertices $y$ and $z$, form the 2-trail $yxz$ and subsequently remove these two from the graph. If this leaves $x$ with degree zero, we also remove $x$. The remaining graph is still connected and with even number of edges.

If all components have even number of edges, each of these have a smaller number of edges and so follow from the induction hypothesis.

If there are components with an odd number of edges, there must be an even number of these. Take any two of these, pick one edge $xy$ to one of them and one edge $xz$ to the other, form the 2-trail $yxz$ as before, then remove these two edges (and $x$ if left with degree 0). The two selected components may (or may not) get disconnected from the rest of the graph after removing these edges, but each connected component of $G$ after removing $yxz$ will have even number of edges and so be handled by the induction hypothesis.

This procedure (by induction or used iteratively) will reduce $G$ to a disjoint union of trails of length 2.

2: Join 2-paths into maximal paths

If at a vertex $x$ there are two trails that start/end there, join these two trails together. Do this iteratively until no more such cases exist. The only place trails can start/end will be at vertices of odd degree; conversely, at each vertex of odd degree, there must be exactly one trail starting/ending. Hence, we are left with $n$ trails starting/ending in the $2n$ vertices of odd degree, plus any number of circular trails.

Since we start with 2-trails, and the joining of two even length trails remain even, all trails (linear and circular) are of even length.

3: Merge circular trails with linear trails

Take any circular trail, $\omega$, from the set. There must be a vertex $x$ in $\omega$ through which another trail from the set passes which we denote $\gamma$: if not, $\omega$ must contain an entire connected component of $G$. Merge $\gamma$ and $\omega$ together at $x$ into a new trail, also of even length since both $\omega$ and $\gamma$ were. If $\gamma$ is linear, the merged trail is linear; if $\gamma$ is circular, the merged trail is circular. But in either case, the number of circular trails in the set is reduced by 1.

We repeate this step until there are no circular trails left. This requires $n>0$, otherwise we will be left with a single circular Euler path spanning the entire graph which we cannot get rid of.



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.