I’m reading the book Graphs and Their Uses which contains the following theorem and proof:
THEOREM 2.3. A connected graph with 2k odd vertices contains a family
of k distinct trails which, together, traverse all edges of the graph
PROOF. Let the odd vertices in the graph be denoted by
in some order.
- Prove $P_m X P_n$ is Hamiltonian if and only if at least one of $m,n$ is even
- Families of sets, determination of SDR (system of distinct representatives)
- How many weakly-connected digraphs of n vertices are there without loops and whose vertices all have indegree 1?
- Connectedness of a regular graph and the multiplicity of its eigenvalue
- Rank of an interesting matrix
- How adjacency matrix shows that the graph have no cycles?
$a_1,a_2,\dots,a_k$ and $b_1,b_2,\dots,b_k$
When we add the $k$ edges $a_lb_l, a_2b_2 ,\dots, a_kb_k$ to the graph, all
vertices become even and there is an Eulerian trail T. When these
edges are dropped out again, T falls into k separate trails covering
the edges in the original graph.
However this doesn’t seem to make sense since in the graph whose vertices have degrees 3, 1, 1, 1 there is no way to add 2 edges in such a way that the degree of all odd vertices becomes even.
What am I missing here?
I see my problem, I’m thinking in terms of simple graphs, but this theorem is thinking in terms of multigraphs. If you add an edge between 3 and 1 and then between 1 and 1 then all vertices become even and there is an Eulerian cycle in the graph. Take away the new edges and you get back a graph in which each edge between odd degree vertices becomes it own trail.
Here’s an alternative proof. Take an odd vertex, and construct a trail from that to another odd vertex. Remove the edges of that trail; the resulting graph has $2k-2$ odd vertices. Repeat.