Let G be a tree with 2k vertices of odd degree Prove that G

Let G be a tree with 2k vertices of odd degree. Prove that G decomposes into k paths.

Solution

Method 1 - According to Eulerian trails, a graph decomposes into k Eulerian trails if and only if every vertex of G has even degree. Since in a tree, we have no cycles, so a path should be a path. Therefore, it decomposes into k 1 paths, P1, P2, . . . , Pk1. So G decomposes into k paths, namely P, P1, P2, . . . , Pk1.

Method 2 -

When k = 1, then G has two odd vertices and since it should have a minimum of 2 leaves, these are the only two odd vertices. This means, that G must be a path.

Let\'s assume G is a forest with 2k odd vertices. Since G₀ is a tree we know that there is a unique path P. So G E(P) is a forest with 2k 2 odd vertices. By the induction hypothesis it decomposes into k 1 paths, P1, P2, . . . , Pk1. So G decomposes into k paths, namely P, P1, P2, . . . , Pk1.