## Graph theory proof

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?

So far, I have:

Let k = 1. The resulting graph is K_2, the complete graph on 2 vertices. Note that both vertices have odd degree. Adding an edge, e, to K2 connecting the two vertices creates an Eulerian circuit, say C, with two edges. Each of these edges is a trail. Now delete e to return to K2 and we are left with exactly k = 1 trails. Now assume a connected graph with 2n odd vertices, n ∈ Z, composes into n trails. We need to show that a connected graph with n+1 edges, with 2(n+1) odd vertices composes into n trails. Let G be a graph with 2(n+1) odd vertices. We can label these vertices u_1, u_2, · · · , u_(2n+2). Let G' = G - 2 of the odd vertices. Then G' has 2x odd vertices and, by the Induction Hypothesis, composes into x trails.

I know that each component has an even number, n, of vertices with odd degree, so G composes into n trails provided each component has odd vertices. But I think I am missing part of the induction.