Question

Show that a graph without isolated vertices has an Eulerian walk if and only if it is connected and all vertices except at most two have even degree.

Answer 1

Prove: If an undirected graph G has an Eulerian walk W, the graph can have at most two odd degree vertices. For a vertex v, let d(v) be the degree of v and let n_W(v) be the number of edges on W incident to v. Since W is Eulerian, n_W(v) = d(v). Also observe that n_W(v) must be even for all vertices other than the start and end vertices of the W. This is because each time W enters an intermediate vertex, it must exit it so W uses up two edges incident to it. Therefore, there can be at most two odd degree vertices (the start and end vertex).

Prove: If a connected graph has at most two odd degree vertices, it has an Eulerian walk. We learned in lecture that there must be an even number of odd degree vertices, since the sum of the degrees of all vertices must be even. Therefore, there are either 0 odd degree vertices or 2 odd degree vertices. If there are 0, we have an Eulerian tour by Euler’s theorem. If there are 2 odd degree vertices, u and v, we can construct an Eulerian walk. We will start our walk T from vertex u, never repeating edges. Let’s say we get stuck at vertex w. If w = u, then n_T(w) is even, since we started at u. But since d(u) is odd, there must exist at least one unused edge incident to u which we can use to continue. If w ≠ u, then n_T(w) is odd; we have entered w but not exited. If w is even degree, there must exist at least one unused edge incident to w which we can use to exit. Therefore, w must be odd degree, so w must be v. We’ve created a walk T, but it is not necessarily Eulerian. If we remove T from the graph, the remaining graph has even degree. This is because we are subtracting n_T(w) from the degree of each vertex w. For the even degree vertices (vertices other than u and v), we are modifying the degree by subtracting an even number, resulting in an even degree. For u and v we are subtracting odd numbers from their degrees, resulting in even degrees. Now we can construct Eulerian tours in the remaining graph. These tours might be disconnected, but they can all be connected to T. Finally, we splice together T with all the Eulerian tours to create the final Eulerian trail.