An Eulerian path in a bipartite graph
Given a trail in an undirected graph we can form a subgraph by taking the same set of vertices in the original graph but keeping only those edges which appear in the trail. In the case of an Eulerian path we will then be keeping one edge from each pair. The diagram of this new, directed, graph will be the same as the diagram of the original graph, except each edge will have an arrow indicating its direction. We found an Eulerian path in our bipartite graph earlier. The corresponding directed graph is given in the accompanying figure.
You may we recall that we’ve already seen a directed graph which selected one edge from each pair, as a way of showing that the graph is bipartite. That graph had the property that at each vertex the edges were either all outgoing or all incoming. In terms of degrees, for each vertex either the in-degree or out-degree is zero. This new directed graph is different. Here the in-degree and out-degree are always equal.
More generally, suppose we start from an Eulerian trail in an undirected graph and create a directed graph by keeping all the vertices and those edges belonging to the path, as above. Whenever a vertex appears in the interior of the trail, i.e. not as the initial or final vertex, it is the final endpoint of one edge and the initial endpoint of the following edge so the first of those edges contributes one to the in-degree and the latter contributes one to the out-degree. The initial edge contributes one to the out-degree of its initial endpoint and the final edge contributes one to the in-degree of its final endpoint. All of the contributions of any edge to the degrees of any vertex arise in one of the ways just described. So for all but the initial and final vertices of the trail the in-degree and out-degree must be the same. For the initial vertex the in-degree is one less than the out-degree and for the final vertex it is one more, unless the initial and final vertex are the same, i.e. unless the trail is a circuit, in which case the in and out degrees at that vertex are again the same. Each edge in the directed graph corresponds to a pair of edges in the original undirected graph and each such edge contributes one to the degree of its endpoints so the degree of a vertex in the undirected graph is the sum of the in-degree and out-degree of that vertex in the directed graph. This degree is therefore even, except in the case of a trail which is not a circuit, in which case the degrees of the initial and final vertices are odd. There are therefore either zero or two vertices of odd degree in an undirected graph with an Eulerian trail. If there are zero then that trail, and all other Eulerian trails, are circuits. If there are two then that trail, and all other Eulerian trails, are not circuits. If the number of vertices of odd degree in an undirected graph is not equal to zero or two then there is no Eulerian trail.
In particular the regular graph we considered earlier with twelve vertices of degree five has no Eulerian trail since it has twelve odd vertices. We can also see that any Eulerian path on the graph we just considered is a circuit, since the number of odd vertices is zero.
Suppose we have an undirected graph all of whose vertices have even degree and at least one has positive degree. Then there is a trail of positive length through that vertex. The number of edges in trail is at most the number of total edges, which is finite, so there is a longest trail through that vertex. What can we say about this trail?
First of all, such a longest trail must in fact be a circuit. To see this we construct two subgraphs. Both have the same vertex set as the origin graph. The first has those edges which belong to the trail, along with the edges in the reverse direction. The second has all the other edges. These are both undirected graphs. The first graph was constructed to have an Eulerian trail. If the initial or final vertex of this trail had odd degree in the first subgraph then it would also have odd degree in the second subgraph, since the two degrees add up to the degree in the original graph. Zero is not an odd number so the degree in the second subgraph is positive, which means there is a pair of edges in the original graph with that vertex as their initial or final endpoint, neither of which belong to the trail. We could therefore extend the trail by appending one or the other of these edges, either at the beginning, if the vertex is the initial vertex or the trail, or at the end, if it’s the final vertex, to obtain a longer trail. Since our trail was chosen to be as long as possible this is impossible, so the degree of the initial and final vertices in the first subgraph is even and therefore those vertices are the same and the trail is a circuit.
Next, a longest trail contains one edge from each pair attached to any of its vertices. We use the same subgraphs as before. We’ve now established that the first subgraph has an Eulerian circuit and that the degrees of the vertices in an undirected graph with an Eulerian circuit are all even so the degrees of all vertices in the first subgraph are all even. We know that the degree of each vertex in the original graph is even and is the sum of its degrees in the two subgraphs so the degree in the second subgraph is also even. Suppose there were a vertex on the circuit which did not contain an edge from each pair connected to it. Then those edges would be in the second subgraph. The second subgraph thus has vertices of even order and this vertex has positive degree so by what we proved in the preceding paragraph, applied now to this subgraph, there is a circuit of positive length through this vertex. We could then splice this circuit in to the original trail to obtain a longer trail, but this is impossible, so the assumption that there is such a vertex is untenable.
So now we know that a longest trail through a vertex is necessarily a circuit and that it contains all edges connected to any of its vertices. Consider now a walk starting at the same vertex. The final vertex of this walk must be traversed by the circuit. This is proved by induction on the length of the walk. If the walk is of length 0 then the final vertex is the initial one and so is certainly traversed by the circuit. If the length is positive then we can assume, by induction, that circuit traverses the final vertex of the walk obtained by deleting the final edge of the original walk. But every edge through that vertex is then traversed by the circuit, including the edge we just deleted, so the final edge of the original path, and hence the final vertex, is traversed by the circuit.
Every vertex in the same component of the graph as the original vertex is connected to that vertex by a walk, and so is traversed by the circuit, as are all the edges connected to it. So a longest path through a vertex traverses every vertex and edge of that component. In particular, if the graph is connected then the longest trail traverses every vertex and edge of the graph. It is therefore an Eulerian trail and, since we’ve already seen that it’s a circuit, is an Eulerian circuit.
What we have just shown is that a connected undirected graph has an Eulerian circuit if and only if all of its vertices have even degree. There is a similar theorem for non-closed Eulerian trails. A connected undirected graph has such a trail if and only if exactly two of its vertices have odd degree. Those two vertices are the initial and final points of the trail. The trick to proving this is to consider the original graph as a subgraph of a larger graph, obtained by adding an extra vertex and pairs of edges from that vertex to the two odd vertices. The larger graph has vertices of even degree and so has an Eulerian circuit. This circuit goes through the added vertex. If we remove the edges in and out of this vertex then we obtain an Eulerian trail in the original graph.
Previously we saw that if there is an Eulerian circuit then the graph is connected and all vertices have even degree. We now have the converse, that if the graph is connected and all vertices have even degree then there is an Eulerian circuit. A similar statement applies to graphs with exactly two vertices of odd degree and Eulerian trails.
It’s often said that proofs by contradiction are non-constructive but the one above does actually give an algorithm for finding Eulerian circuits:
Choose a vertex.
Starting at that vertex continue to an adjacent vertex, a vertex adjacent to that, etc., always avoiding edges which have already been used in either direction. Do this until there are no available edges left wherever you stopped.
The vertex where you stopped must be the one where you started, so you have a circuit, but not necessarily an Eulerian one. If it’s not Eulerian then there’s a vertex somewhere along the path with edges you haven’t used. Starting from that vertex continue to an adjacent vertex, a vertex adjacent to that, etc. When you can’t continue any further you must have ended up at the vertex where you left the original circuit. Splice the new circuit into the old one at the point where it was first visited.
Keep doing the preceding operation until there are no vertices on the circuit with available edges. At this point you have an Eulerian circuit.