Show that a graph can be separated in k disjoint trails but with at most one trail of length odd.

211 Views Asked by At

Let $G$ be a connected graph containing $2k$ odd vertices, where $k\ge 1$. Prove that $E(G)$ can be partitioned into subsets $E_i$, $1 \le i \le k$, where each subgraph $G[E_i]$ induced by $E_i$ is an open trail, at most one of which has odd length.

(Source: Problem 3 in Chapter 3 of Chromatic Graph Theory, p. 87)

Finding the $trails$ is not difficult if you add $k$ new vertex and add edges between this new vertex and the vertex whose have an odd degree, so we can find an eulerian cycle. Something looking like this:

$C = {v_1,w_1,v_2,T_1,v_3, w_2, v_4,T_2, ... , v_{2k-1}, w_k, v_{2k}, T_k, v_1}$ so the trails we need are $T_i$ but how can I show that there is only one at most of odd degree. I mean in the new graph we can add a vertex in a cycle since every eulerian graph can be decompose in cycles and we are having th same trajectories but we alter the length of one trajectory.