I'm trying to understand the solution to exercise 6.4 in Robin J. Wilson's 'Introduction to Graph Theory':
Let $G$ be a connected graph with $k$ $(>0)$ vertices of odd degree. Show that the minimum number of trails, that together include every edge of $G$ and that have no edges in common, is $k/2$.
I am well aware that there are many posts concerning this exact result (e.g. $k$-edge disjoint walks or number of trails in an odd graph is $n/2$ or a graph containing $2k$ odd vertices contains $k$ disctinct trails or even $k/2$ non-closed trails). Wilson's book also includes a solution, which essentially duplicates the reasoning in these posts. I've reproduced Wislon's proof at the end for completeness. Unfortunately, none of these answers have helped my understanding.
Here is my summary of all the proofs of this result I have seen to date (and the part I got stuck in):
Firstly, the number of vertices of odd degree is even by the Handshaking Lemma, so $k=2n$ for some $n\in \mathbb{N}$. Label the odd vertices as $u_1, …, u_{2n}$. There are two ways of proceeding:
- Add the edges $u_1u_2, u_3u_4, …, u_{2n-1}u_{2n}$ (total of $n$) to the graph
- Add vertices $w_1, …, w_{n}$ and the edges $u_1w_1$, $w_1u_2$, $u_3w_2$, $w_2u_4$, …, $u_{2n-1}w_n$, $w_nu_{2n}$ (so that for each $i = 1, …, n$, there is an edge connecting $w_i$ and $u_{2i-1}$ and $w_i$ and $u_{2i}$.)
As a result of either of these procedures the degrees of all the graph's vertices become even, so the updated graph is Eulerian (this follows by Theorem 6.2 of the book, which states: A connected graph G is Eulerian if and only if the degree of each vertex of $G$ is even).
Then all the proofs proceed by removing the added edges (in case 1) or the vertices (in case 2) one by one.
In case 2:
When we remove $w_1$ and the edges adjacent to it, the graph contains exactly two edges of odd degree, so it is now semi-Eulerian (i.e. it contains an Eulerian trail). This follows by Corollary 6.4 of the book, which states: A connected graph is semi-Eulerian if and only if it has exactly
two vertices of odd degree.
Removing another vertex and the edges adjacent to it apparently splits the graph into two trails, removing yet another one splits it into three, and so on, until the $k$th vertex has been removed and the walk has been split into $k$ trails. This is the part of every proof I fail to grasp. How does the trail split? In what location of the graph does it split? I'd greatly appreciate a detailed explanation of what happens when additional vertices are removed.
Case 1 is essentially identical:
When we remove 1 of the added edges, say $u_1u_2$, there are precisely two vertices of odd degree: $u_1$ and $u_2$. So the graph is semi-Eulerian. […]
EDIT: Corollary 6.3 of the book states:
A connected graph is Eulerian if and only if its set of edges can be split up into disjoint cycles.
Perhaps this can be used here? However, the corollary says nothing about the number of these disjoint cycles, and neither does its proof (at least the one that I've seen).
The solution in Wilson's book itself reads:
At least $k/2$ trails are needed, so as to 'use up' all $k$ vertices of odd degree. If we now add $k/2$ edges to $G$ and join these vertices in pairs, then we obtain an Eulerian graph $G'$. We obtain the required $k/2$ trails by writing down an Eulerian trail for $G'$ and then omitting the added edges.
Best Answer
Your idea of adding the edges is the key to the solution. Observe that once you add those edges(the ones you mentioned) in the graph, every vertex attains even degree (since the ones with even degree already aren't disturbed, and the each of the ones with odd degree got one edge, making it's degree even). Since this new graph now has even degree at each vertex, it has an Eulerian tour. Now, this tour contains all the edges of the original graph along with the new edges you added, so we remove them.
The thing that you probably missed here is what happens when we remove those extra edges, which are $n$ many in number.
Observe that removing $k$ many edges from a tour which are not adjacent in the tour (i.e. while following the tour, they don't occur consecutively) gives us $k$ many disjoint trails. You can observe this fact by explicitly writing down a tour (i.e. the vertices and edges in order) and then omitting $k$ many of them which don't occur consecutively. In our case, the extra edges you added aren't even adjacent, i.e., they don't occur consecutively in the tour. So removing $n$ many of them leaves us with $n$ many edge disjoint trails.
Hope that helps you.
Keep mathing !!