Graph Theory Show that if u and v are the only odd verticies

Graph Theory

Show that if u and v are the only odd verticies in the connected simple graph G, then G has a Euler Trail from u to v.

Hint: If you use the result from class if all vertices of G have an even degree then there is a closed Euler Trail, then the result becomes very easy.

Solution

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.