22-3 Euler tour

An Euler tour of a strongly connected, directed graph G=(V,E)G = (V, E) is a cycle that traverses each edge of GG exactly once, although it may visit a vertex more than once.

a. Show that GG has an Euler tour if and only if in-degree(v)=out-degree(v)\text{in-degree}(v) = \text{out-degree}(v) for each vertex vVv \in V.

b. Describe an O(E)O(E)-time algorithm to find an Euler tour of GG if one exists. (Hint:\textit{Hint:} Merge edge-disjoint cycles.)

a. First, we'll show that it is necessary to have in degree equal out degree for each vertex. Suppose that there was some vertex v for which the two were not equal, suppose that in-degree(v)out-degree(v)\text{in-degree}(v) - \text{out-degree}(v). Note that we may assume that in degree is greater because otherwise we would just look at the transpose graph in which we traverse the cycle backwards. If vv is the start of the cycle as it is listed, just shift the starting and ending vertex to any other one on the cycle. Then, in whatever cycle we take going though vv, we must pass through vv some number of times, in particular, after we pass through it a times, the number of unused edges coming out of vv is zero, however, there are still unused edges goin in that we need to use. This means that there is no hope of using those while still being a tour, becase we would never be able to escape vv and get back to the vertex where the tour started. Now, we show that it is sufficient to have the in degree and out degree equal for every vertex. To do this, we will generalize the problem slightly so that it is more amenable to an inductive approach. That is, we will show that for every graph GG that has two vertices vv and uu so that all the vertices have the same in and out degree except that the indegree is one greater for uu and the out degree is one greater for vv, then there is an Euler path from vv to uu. This clearly lines up with the original statement if we pick u=vu = v to be any vertex in the graph. We now perform induction on the number of edges. If there is only a single edge, then taking just that edge is an Euler tour. Then, suppose that we start at vv and take any edge coming out of it. Consider the graph that is obtained from removing that edge, it inductively contains an Euler tour that we can just post-pend to the edge that we took to get out of vv.

b. To actually get the Euler circuit, we can just arbitrarily walk any way that we want so long as we don't repeat an edge, we will necessarily end up with a valid Euler tour. This is implemented in the following algorithm, EULER-TOUR(G)\text{EULER-TOUR}(G) which takes time O(E)O(|E|). It has this runtime because the for loop will get run for every edge, and takes a constant amount of time. Also, the process of initializing each edge's color will take time proportional to the number of edges.

EULER-TOUR(G)
    color all edges WHITE
    let (v, u) be any edge
    let L be a list containing v
    while there is some WHITE edge (v, w) coming out of v
        color (v, w) BLACK
        v = w
        append v to L