Can a Connected Graph with 2k Odd Vertices be Composed into k Trails?

[tarheelborn]

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 K_2, 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 k + 1, i.e., 2(k + 1) odd vertices. Let G be a graph with 2(k+1) odd vertices. Label these vertices as u_1, u_2, ..., u_2k+2.

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).

 

[haruspex]

Is it possible for a connected component to have an odd number of odd-valent vertices?

 

[tarheelborn]

No, a connected component cannot have an odd number of odd-valent vertices. Then could we say that since G cannot have an odd number of odd-valent vertices, there must be some (at least one) even-valent vertices which would indicate some (at least one) trails?

 

[haruspex]

No, a connected component cannot have an odd number of odd-valent vertices.

Right, so how does the 2k total decompose across the components? What can you say about decomposition into trails in each component?

 

[tarheelborn]

A trail contributes even degree to every vertex, except that non-closed trails contribute odd degree to their endpoints. Thus a single trail can have, at most, two vertices of odd degree, so the composition of G contains 2k odd vertices, divided by 2 vertices per trail = k trails. That should do it, right? Thank you very much.

 

[haruspex]

A trail contributes even degree to every vertex, except that non-closed trails contribute odd degree to their endpoints. Thus a single trail can have, at most, two vertices of odd degree, so the composition of G contains 2k odd vertices, divided by 2 vertices per trail = k trails. That should do it, right? Thank you very much.

That's not what I had in mind. You know that each component of G must have an even number of odd-valent vertices. Where that number > 0, the component decomposes into half that many trails. In that way, you decompose a disconnected graph with 2k odd-valent vertices into k trails provided... what?

 

[tarheelborn]

You are losing me here somewhat... I see that each trail has odd-valent vertices at its endpoints, so there would be two odd-valent vertices per trail. Then a graph with 2k odd-valent vertices would decompose into k trails provided the graph was Eulerian?

 

[haruspex]

In the OP, you say you know that if a graph is connected and has 2k > 0 odd-valent vertices then it decomposes into k trails. Suppose more generally that a graph has n connected components. We've established that each must have an even number 2k_i of odd-valent vertices, Ʃk_i = k. If the i^th component decomposes into k_i trails then we're home, right? How might that not be so? What condition are we missing on k_i?

 

[tarheelborn]

I think the ith component must have odd vertices; otherwise we have a circuit, not a trail.

 

[haruspex]

I think the ith component must have odd vertices; otherwise we have a circuit, not a trail.

I'm not sure whether a trail is defined to have distinct endpoints. Maybe a circuit is just a special case of a trail? But even if a circuit is counted as a trail, you will still not be able to decompose the entire graph into k trails. Do you see why?

 

[tarheelborn]

The ith component would need odd vertices. Without that condition the graph could not be composed into k trails. Is that what you mean?

 

[haruspex]

The ith component would need odd vertices. Without that condition the graph could not be composed into k trails. Is that what you mean?

Yes. E.g. Consider a graph consisting of two connected components, K₂ and K₃. It satisfies the criteria in the OP (k=1), but does not consist of a single trail.