- #1

- 123

- 0

## Homework Statement

Use ordinary induction on k or on the number of edges (one by one) to prove that a connected graph with 2k odd vertices composes into k trails if k > 0. Does this remain true without the connectedness hypothesis?

## Homework Equations

## The Attempt at a Solution

If k = 1, the resulting graph is [tex]K_2[/tex], the complete graph on two vertices, both of which have odd degree. If we add an edge connecting these 2 vertices, we obtain an Eulerian circuit. Removing one edge reduces the graph to exactly 1 trail. Assume this proposition holds for k >= 1. I need to show that it holds for [tex]k + 1[/tex], i.e., [tex]2(k + 1)[/tex] odd vertices. Let G be a graph with [tex]2(k+1)[/tex] odd vertices. Label these vertices as [tex]u_1, u_2, ..., u_2k+2[/tex].

And that's where I get stuck... I know that since G is connected, it contains trails, but I am not sure how to work this back to k trails...

(Sorry about the latex; I can't remember how to make it not break to a new line).