Constructing Paths in a Connected Graph with Odd-Degree Vertices

Question

I am working on a problem and would appreciate some insights or suggestions on how to approach it.

Problem: Let G = (V, E) be a connected graph where n is the number of vertices in V that are of odd degree. How can one construct n/2 trails in G such that each edge in E is contained in exactly one of these trails? (edit: replaced path with trail)

My solution: By the Handshaking Lemma, the number of vertices of odd degree is even; thus, n/2 will always be a positive integer. Construct pairs of vertices of odd degree such that no vertex of odd degree is left unpaired. Construct a path between each pair such that the path contains only vertices of even degree between the start and end vertices. According to the theorem discussed in the lecture, it follows that this path is Eulerian. Now, remove the edges of the Eulerian path from the graph and repeat the process with all remaining pairs of vertices.

Answer 1

Firstly, the statement is not true with standard terminology. You cannot necessarily do this with paths, but you can do it with trails. We'll see later why we need this.

For the corrected version, you have a good idea, but the proof currently has some issues.

The first problem is that you pick an arbitrary pair of odd-degree vertices $u$ and $v$, and try to construct a path between them only using even-degree vertices. There is no reason why such a path should exist. However, you don't need it to. Just take any path between $u$ and $v$. When you remove that path, the degrees of $u$ and $v$ change by $1$ (so become even), and the degree of every other vertex on the path decreases by $2$, so doesn't change parity.

(The business about the path being Eulerian doesn't make sense, but is also unnecessary.)

The second problem is that the original statement only works for connected graphs, but you reduce to a graph that may not be connected. Actually, it is also true for any graphs where every component (with at least one edge) has an odd degree vertex, as an easy corollary. So there is a potential problem if removing the path leaves you with a disconnected graph where some component (with at least one edge) has all degrees even. In order to deal with this, note that this component is Eulerian, and must meet the path. So when you meet the component as you go along the path, you can add in a detour using all the edges of the component. Since this forces us to reuse a vertex, what we have is no longer a path, but is a trail.