Euler Tours

The purpose of this chapter

This chapter concludes the part of this book devoted to vertex degrees. It is an application of the concept of vertex degrees, as well as some results from Chapter 4, to solve a problem that could be said to be the beginning of graph theory.

There is a striking contrast in graph theory between the theory of Euler tours and Eulerian graphs, discussed in this chapter, and the theorem of Hamilton cycles and Hamiltonian graphs, discussed in Chapter 17. Superficially, the two problems are very similar, yet we are able to pin down the exact circumstances in which an Euler tour exists; for Hamiltonian cycles, hard work is required in most cases.

Everything we say about the Euler tour problem for graphs remains true for multigraphs, with no substantial change. For directed graphs, the situation is a bit more complicated, and it is discussed at the end of the chapter. However, many of the important applications of Euler tours, such as the one in Chapter 20, are applications to directed graphs, so this is an important case of the problem to understand.

Don’t lift your pencil!

You might have seen a brainteaser like this before! Look at the diagram in Figure 8.1(a). Can you draw this shape on paper without lifting your pencil (or pen), and without going over the same line more than once?

You can: Figure 8.1(b) shows you one particularly symmetric way to do it. (To make it clear what the solution is, the lines are bent away from each other slightly to indicate where the path does or does not cross itself.) As a bonus, the path in Figure 8.1(b) returns to where it started.

This is a book on graph theory, though, not on pencil drawings. So what does this question have to do with graph theory? This is the same question that this book started with: how do we model this problem as a graph?

The places in the drawing that matter most are the places where several lines meet: when tracing the drawing with your pencil, those are the only places where we make a decision. So it makes sense to have a vertex for each of those points. The rest of the drawing consists of lines that go from one such point to another, and their shape does not matter for solving the puzzle: only the starting and ending point matters. So for every such line, we will add an edge between the two vertices it joins. If we apply idea to Figure 8.1(a), the result is shown in Figure 8.1(c).

The result is a multigraph; how did that happen?

We get parallel edges whenever there are two or more lines that start and end at the same pair of intersection points.

What sort of graph-theoretic object are we looking for when we solve the brainteaser?

We are looking for a walk in the graph which uses every edge exactly once.

There are two other well-known puzzles that are an instance of the same type of problem. One is the five rooms puzzle, shown in Figure 8.2(a). Here, five rooms are connected by a total of \(16\) doors, and the challenge is to plot a path through the rooms that passes exactly once through every door.

What should the vertices and edges be in the multigraph that makes the five rooms puzzle equivalent to the pencil-drawing puzzle?

There should be six vertices: one for each room, where we consider the outside region to be a room as well. Each door between two rooms should be an edge incident to both rooms.

Another such puzzle, the problem of the seven bridges of Königsberg, has historical significance. It was first studied by Leonhard Euler, in 1736 [6], and it may be one of the first mathematical problems to be abstracted into a graph-theoretic model before being solved. (It predates modern graph theory, so the terminology used by Euler was quite different from what you are reading here.) The problem itself is based on a map of the city of Königsberg, shown somewhat abstractly in Figure 8.2(b). In Euler’s time, there were seven bridges connecting the two sides of the river and the two large islands in the middle of the river. The challenge was to find a path through the city that crossed each bridge exactly once.

What should the vertices and edges be in the multigraph that models the bridges of Königsberg?

There should be a vertex for each of the four landmasses, with an edge for every bridge.

The problem we are solving in all three of these puzzles is named in Euler’s honor.

All three puzzles we have looked at are about finding an Euler walk. Even though the solution in Figure 8.1(b) happens to be an Euler tour, we have not had a reason to consider Euler tours for their own sake so far. However, you are about to see in this chapter that Euler tours are actually the more fundamental and more natural object. This is reflected in the following definition:

First steps

The key to determining whether an Euler walk or Euler tour exists turns out to depend on the degree of the vertices. To simplify terminology just for this chapter, we will call a vertex odd or even if it has odd degree or even degree, respectively.

The following result does not completely answer our question, but is easier to prove than the main theorem of this chapter, so it is where we will begin. I will give the proof in the language of multigraphs, so that we can be sure it works even then.

Why doesn’t Lemma 8.1 solve the problem completely?

If every vertex in a multigraph is even, the lemma doesn’t guarantee that the multigraph really does have an Euler tour.

In other words, we have shown that the condition “every vertex in \(G\) is even” is a necessary condition for \(G\) to be Eulerian: that is, \(G\) can’t be Eulerian without it. We have not determined whether it is a sufficient condition for \(G\) to be Eulerian: whether all graphs that satisfy the condition do in fact have Euler tours.

If \((x_0, e_1, x_1, e_2, x_2, \dots, e_m, x_m)\) were an Euler walk, but not an Euler tour, what would change in the proof of Lemma 8.1?

When \(x=x_m\), it would no longer be true that \(x=x_0\) as well, so the degree of \(x\) would be \(2k-1\) rather than \(2k\): \(x\) would be odd. Also, when \(x=x_0\), the argument wouldn’t “notice” the contribution of edge \(e_1\) to \(x\)’s degree, because \(I\) only contains positive integers, so \(x\) would be odd in this cases as well.

Following this reasoning carefully gives us the following claim:

Which of the puzzles in Figure 8.2 have solutions?

Neither puzzle has a solution. If we convert them to multigraphs, then in both cases there will be four odd vertices. However, Lemma 8.2 implies that a graph with an Euler walk can have at most two odd vertices.

The condition “at most two odd vertices” is a bit more complicated than the condition “no odd vertices”, but that’s not the real reason that Euler tours are taken to be more fundamental than Euler walks.

Imagine for a moment that we had a method for finding Euler tours, but not Euler walks, and suppose that we were faced with a graph \(G\) where only two vertices, \(x\) and \(y\), were odd. Well, we could fix this quite easily: we could simply add an edge \(e\) with endpoints \(x\) and \(y\). In the new graph¹ \(H\), all vertices would be even, so \(H\) would have an Euler tour.

In our imagination, we already have a method for finding Euler tours, so we could easily find an Euler tour in \(H\). That Euler tour would have to use the new edge \(e\) at some point. Well, if we simply delete edge \(e\) from the tour, we could follow the tour starting from \(x\) and visit all the other edges, ending at \(y\). This is an Euler walk in \(G\).

Outside our imagination, we don’t have any systematic method of finding Euler walks or Euler tours, yet. However, this argument lets us reduce the Euler walk problem to the Euler tour problem. It tells us that all we need to focus on is finding Euler tours in graphs where all vertices are even. As soon as we find an algorithm to do this, we will immediately have an algorithm for Euler walks as well!

Cycle decompositions

Let’s take a detour² and consider cycle decompositions.

In general, a decomposition of \(G\) is a set of subgraphs \(\{G_1, G_2, \dots, G_k\}\) such that every edge of \(G\) is an edge of exactly one subgraph \(G_i\). We have already seen one kind of decomposition: the decomposition of a graph into its connected components. We will encounter two other examples of decompositions later: \(1\)-factorizations in Chapter 16 and ear decompositions in Chapter 25.

In particular, a cycle decomposition of \(G\) is a set of cycles in \(G\) such that every edge of \(G\) is an edge of exactly one of the cycles. This uses the terminology in a straightforward way, but one thing is awkward: the notation. We cannot write a cycle decomposition \(\{C_1, C_2, \dots, C_k\}\), because the notation \(C_n\) already refers to the \(n\)-vertex cycle graph. When we must, we resort to a standard option all mathematicians take when not allowed to use subscripts: use superscripts instead, writing the cycle decomposition as \(\{C^{(1)}, C^{(2)}, \dots, C^{(k)}\}\).

When studying the Euler tour problem in 1912, Oswald Veblen realized that a single closed walk and a collection of many cycles share a common feature: in both cases, if they visit a vertex \(k\) times, they use \(2k\) edges incident to that vertex. Therefore the necessary condition for Eulerian graphs is also necessary for having a cycle decomposition. However, Veblen was able to prove [101] that for cycle decompositions, this condition is both necessary and sufficient!

A key step of this proof uses Theorem 4.4: if a graph has minimum degree at least \(2\), then it contains a cycle. We proved this theorem for simple graphs, but if you go back and examine our argument, you should be able to convince yourself that it can be carried out in multigraphs as well.

Alternatively, there is a way to generalize the theorem to multigraphs without looking at the proof of Theorem 4.4 at all. How?

If a multigraph has a loop, it has a cycle of length \(1\), and if it has two parallel edges, it has a cycle of length \(2\). In both cases, we already get the conclusion we want. If the multigraph has neither of these, then we can think of it as a simple graph.

This proof also gives us an algorithm for finding a cycle decomposition. Simply find any cycle, set it aside, and repeat with the remainder of the graph until we are out of edges. How do we find a cycle? Well, the proof of Theorem 4.4 begins by taking a longest path, but this is done only to simplify the proof. Really, we can build up a path by aimless wandering through the graph, taking care only not to leave a vertex by the same edge we used to enter it. As soon as we revisit the vertex, we obtain a cycle in the same way that we obtained it from the longest path.

Gluing cycles together

Before we go on, let me clear the air about one thing: the condition that all vertices are even is not sufficient to guarantee that a graph is Eulerian. However, the exception is rather silly.

How can you find a graph where all vertices are even, but which does not have an Euler tour? (Small examples include a multigraph with \(2\) edges and a simple graph with \(6\) edges.)

Just make sure that your graph has multiple connected components with edges in them! A walk can never jump from one component to another, so you can never include all edges of the graph in a single walk.

This is a minor quibble; we will be fine if we restrict our attention to connected graphs. We can even allow graphs with multiple components, as long as all components except for one are merely isolated vertices. The cycle decomposition we get from Theorem 8.3 is the key ingredient in putting together an Euler tour.

To truly understand the proof and the algorithm, let’s go through an example, finding an Euler tour of the graph in Figure 8.4(a). We will begin with a cycle decomposition. The one shown in Figure 8.4(b) is actually not the best one to use—life would be easier for us if we had fewer longer cycles. The decomposition with many short cycles will let us see more steps of the algorithm in action.

1. Initially, our partial tour \(PT\) is a walk \((1,5,7,1)\) representing \(C^{(1)}\).

2. Next, we want to add a cycle that shares a vertex with \(PT\): that is, we can’t use \(C^{(2)}\). Let’s take \(C^{(4)}\) instead; \(C^{(3)}\) would also work.

   The only vertex of \(C^{(4)}\) appearing on \(PT\) is vertex \(5\). So we choose to represent \(C^{(4)}\) by the closed walk \((5, 3, 4, 6, 5)\), and replace the \(5\) in \(PT\) by this closed walk: now, \[PT = (1, \underbrace{5, 3, 4, 6, 5}, 7, 1).\]

3. At this point, \(PT\) has lots of vertices, so we can add either remaining cycle. Let’s add \(C^{(2)}\). It shares vertex \(4\) with \(PT\), so we represent \(C^{(2)}\) by \((4, 2, 8, 4)\) and splice it into \(PT\): now, \[PT = (1, 5, 3, \underbrace{4, 2, 8, 4}, 6, 5, 7, 1).\]

4. Finally, only \(C^{(3)}\) is left to add; it shares many vertices with \(PT\), but in particular, it shares vertex \(1\), so we choose to represent it by \((1, 2, 6, 8, 7, 3, 1)\). We replace the first occurrence of \(1\) in \(PT\) by this closed walk, getting the final result: \[PT = (\underbrace{1, 2, 6, 8, 7, 3, 1}, 5, 3, 4, 2, 8, 4, 6, 5, 7, 1).\]

To check that \(PT\) is an Euler tour for yourself, draw all the vertices of the graph in Figure 8.4(a), with no edges between them. Then, follow \(PT\), drawing each edge as you use it. As you go, check that you never draw an edge more than once; at the end, check that you have drawn all of Figure 8.4(a).

Variations on Euler tours

Of course, now that we have an algorithm for Euler tours, we immediately have an algorithm for Euler walks, as well as a test for their existence. The only thing that changes is that a graph with two odd vertices can still have an Euler walk.

In a graph with exactly two odd vertices, is it possible for them to be in different connected components?

It is not: if this happened, then looking at one of those components by itself, we’d see a subgraph with only one odd vertex. However, by Corollary 4.2 to the handshake lemma, the number of odd vertices in any graph is even.

Can you think of a way to modify the algorithm for Euler tours so that it finds an \(x-y\) Euler walk instead?

Instead of a partial tour \(PT\), begin with a partial walk \(PW\) representing an \(x-y\) path \(P\), and let \(H = G - E(P)\). In \(H\), all vertices are even, so we can take \(\mathcal U\) to be a cycle decomposition of \(H\). From here, the algorithm can be continued as before.

Another interesting problem is the problem of finding Euler tours in a directed graph. The first novelty in the directed setting is that we no longer check for whether a vertex is even: entering and leaving a vertex has a different effect on its indegree and outdegree.

If a directed graph \(D\) has an Euler tour, what can you say about the degree of a vertex that appears on the tour \(k\) times?

Each arc into the vertex adds \(1\) to its indegree, and each arc out of the vertex adds \(1\) to its outdegree. Thus, the vertex will have indegree \(k\) and outdegree \(k\).

What, then, is the corresponding necessary condition for a digraph to be Eulerian?

Every vertex must have an indegree equal to its outdegree. (We can call such vertices balanced.)

To prove a necessary and sufficient condition for directed graphs, we must retrace the steps we took in the undirected setting. The only new ingredient is the result we use to find a single cycle; we proved it in Chapter 7. Can you anticipate it before it is used?

Starting from a cycle decomposition, the algorithm for finding an Euler tour is the same as it was for undirected graphs. However, there is a further difficulty with stating the final result. We do not know exactly which graphs it applies to, because do not yet know what it means for a directed graph to be connected.

I will give you the statement first, and then we will determine what it means. This is the proper way to go about it: we figure out what we should prove by figuring out the assumptions we need to use.

The proof is the same as the proof of Theorem 8.4: we start with a cycle decomposition, and splice the cycles into a partial Euler tour, one by one.

Looking at the proof of Theorem 8.4, where did we need the graph to be connected?

We needed it to be impossible for the partial tour \(PT\) and the unused cycles \(\mathcal U\) to have no vertices in common.

So the notion of connectedness we need is simply that it should be impossible to split the vertices of our digraph \(D\) into two sets, with no arcs between them in either direction: that’s what we’d get if \(PT\) and the cycles of \(\mathcal U\) shared no vertices. This is a notion of connectedness that ignores the orientations of the arcs.

Formally, we call a digraph \(D\) weakly connected if the underlying graph is connected. Now we know what Corollary 8.6 means!

Practice problems

1. The classic brainteaser in the “draw without lifting your pencil” genre is the picture of a stylized house shown below:

   

   In order to draw this picture without lifting your pencil or retracing any line, where must you start and end? (Of course, you can always swap the start and end.)

2. Find a cycle decomposition of the circulant graph \(\operatorname{Ci}_{10}(1,2)\), and use it to find an Euler tour of \(\operatorname{Ci}_{10}(1,2)\).

3. Find an Euler tour of the \(4\)-dimensional hypercube graph, \(Q_4\).

4. Let \(G\) be the graph below. Find a vertex \(x\) such that \(G-x\) is Eulerian.

   

5. The graph below is not Eulerian, because some of its vertices are odd. What is the maximum length of a closed walk in this graph that does not use any edge more than once? Prove your answer.

   

6. In the complete graph \(K_7\), every vertex has degree \(6\), so by Theorem 8.3, \(K_7\) has a cycle decomposition.

   1. Suppose we wanted to decompose \(K_7\) into as few cycles as possible. How many cycles would we want to use, and of what lengths? Give an example of such a decomposition.

   2. Suppose we wanted to decompose \(K_7\) into as many cycles as possible. How many cycles would we want to use, and of what lengths? Give an example of such a decomposition.

7. Suppose that the complete graph \(K_n\), where \(95 < n < 105\), has a cycle decomposition in which every cycle has length \(5\). What must the value of \(n\) be?

8. Prove that every graph has a “double tour”: a closed walk which uses every edge exactly two times, once in each direction. (That is, for every edge \(xy\), the walk contains one segment \(\dots, x, y, \dots\) and one segment \(\dots, y, x, \dots\).)

9. This exercise presents part of a method due to Noga Alon [2] for finding perfect matchings (which we will cover in detail starting in Chapter 13) using Euler tours.

   1. Let \(G\) be a bipartite graph: that is, \(V(G)\) is the union of two sets \(A\) and \(B\), with \(A \cap B = \varnothing\), such that all edges of \(G\) have one endpoint in \(A\) and one endpoint in \(B\).

      Prove that if every vertex of \(G\) is even, then \(G\) has an even number of edges.

   2. Let \(G\) be a graph in which every vertex is even and (as in part (a)) the number of edges is even. Prove that \(G\) has a spanning subgraph \(H\) such that for every vertex \(x\), \(\deg_H(x) = \frac12 \deg_G(x)\).

   3. Prove by induction on \(k\) that for all \(k \ge 0\), every \(2^k\)-regular bipartite graph has a \(1\)-regular spanning subgraph.

10. (BMO 1977) Prove that for each integer \(n>1\) it is possible to construct a necklace having \(2n^2\) beads in all, these being of \(2n\) different colors, in such a way that for each pair of different colors there is at least one pair of adjacent beads of these two colors. Is it possible to do the same using \(2n^2-1\) beads in all? Give a reason for your answer.

Footnotes

1. Or multigraph: even if \(G\) is a simple graph, it might already have an edge \(xy\), so we need to switch to a multigraph model to add edge \(e\).↩︎

2. Heh-heh.↩︎