Mathematics — Graph Theory · paths-even-degree-parity
Problem
Let G be a multigraph such that every vertex of G has even degree. Let u and v be two distinct vertices of G. Prove that the number of paths from u to v is even.
[Hint: When you add an edge joining u to v, the graph G becomes a graph with exactly two odd-degree vertices u and v, and the claim becomes ``the number of paths from u to v is odd'' (why?). In this form, the claim turns out to be easier to prove. Indeed, any path must start with some edge\ldots Keep in mind that paths can be replaced by trails, by Exercise 3.10.]