# Graphs and Eulerian tours

12.11.2020 (last taught)

In this lecture, we introduce the notion of a graph, which is of central importance for many branches of computer science as well as other scientific disciplines. Many questions benefit from being viewed through the lens of graphs. As a first example, we discuss a famous mathematical and algorithmic problem, which we call `Eulerian-Tour`

. We use this example to illustrate and motivate some basic concepts in the context of graphs.

## 1. Seven bridges of Königsberg

Leonhard Euler (mathematical giant, born 1707 in Basel) solved the following mathematical puzzle (fig. 1), called “Seven Bridges of Königsberg”:

Devise a walk through the city of Königsberg that crosses each of its seven bridges over the Pregel River exactly once.

Euler proved that such a walk does not exist. As part of his proof, he proposed the following abstract representation, which we call *graph* nowadays, for the city parts and the bridges. This representation captures all aspects of the city and bridges relevant for the puzzle.

Here, the four parts of the city separated by the river are represented by four *vertices* labeled A, B, C, and D. The seven bridges over the river are represented by *edges* that connect pairs of vertices.

The puzzle asks whether it is possible to walk along the edges of the above graph in such a way that each edge is traversed exactly once. We call such a walk *Eulerian*.

To answer the question whether a Eulerian walk exists, it turns out that vertex degrees play an important role, where the *degree* of a vertex is defined to be the number of edges that touch the vertex.

The following table contains the degrees of the vertices in the graph representing the bridges of Königsberg.

A | B | C | D |
---|---|---|---|

3 | 5 | 3 | 3 |

A vertex with degree *isolated*.

Based on these vertex degrees, the following claim demontrates that the above graph doesn’t have an Eulerian walk.

**Claim:** If there exists a Eulerian walk, then all but at most two vertex degrees must be even.

*Proof:* Suppose a Eulerian walk

## 2. House of Santa Claus

Eulerian walks are connected also to an old drawing and rhyming puzzle for children (which appears to be known mostly in German-speaking regions). The puzzle is to draw the following figure in eight strokes—one for each syllable of the rhyme “Das ist das Haus vom Ni-ko-laus”—without lifting the pen.

**Observation:** A sequence of strokes to draw this figure without lifting exactly corresponds to a Eulerian walk in the following graph (obtained by placing a vertex at each corner of the drawing).

This graph indeed has a Eulerian walk: C,A,E,B,D,A,B,C,D.

## 3. Hamiltonian path

A Hamiltoninan path in a graph is defined to be a walk that visits every vertex exactly once. This definition is syntactically similar to the definition of Eulerian walks. Only the role of edges and vertices is interchanged.

Despite the similar definition, it turns out that in general it is much more difficult to reason about Hamiltonian paths than about Eulerian walks.

The following graph is an example of a graph that has a Eulerian walk but not a Hamiltonian walk.

## 4. Algorithms for Hamiltonian paths and Eulerian walks

Suppose we are given a graph and the goal is to compute a Eulerian walk or a Hamiltonian path if it exists.

A naive algorithm is *brute-force search*: we consider all possible orderings of edges or vertices. However, the running time of this approach is at least exponential. Indeed, for a graph with

For Eulerian walks, as we will see in this lecture, it is possible to avoid brute-force search and compute a Eulerian walk in time

In contrast, for Hamiltonian paths, brute-force search appears to be unavoidable. The famous

## 5. Graphs

Before proceeding, we step back to discuss the broader significance of graphs. We also give a mathematical definition of graphs and introduce some terminology that is commonly used in the context of graphs.

Networks are ubiquitous in many different human endeavors:

*computer networks*(like the internet): computing devices are connected to each other by data links*social networks:*people are connected to each other by their social relationships*transportation networks:*cities are connected to each other by streets and train tracks*neural networks*(both artifical and natural ones): neurons are connected to each other at synapses

Graphs are mathematical models for networks that highlight some common structure shared by all networks.

**Definition:** A *graph*

It is often convenient to choose

In the above example, the vertex set is

**Definition:** If a graph *adjacent* in *incident* to

Instead of writing

**Handshake lemma:** For every graph

*Proof:* Suppose every vertex distributes one coin to each of its incident edges. Then, every edge receives two coin in total, one coin from each of its endpoints. Thus, the sum of the vertex degrees has to equal twice the number of edges.

**Definition:** A *walk* of *length*

To this walk, we also associate the sequence of *Note:* The usual convention is that the length of a walk refers to its number of edges (as opposed to its number of vertices).

For a walk *Note:* If

A walk is *closed*, if starts and ends with the same vertex *path* is a walk without repeated vertices.

**Claim:** A walk

*Proof:* Each occurrence of

We say that vertex *reaches* vertex

The *connected component* of a vertex *connected* if every vertex

A *Eulerian tour* is a closed walk that visits every edge exactly once.

## 6. Characterization of Eulerian tours

The following theorem shows that the only possible obstruction for a Eulerian tour is a vertex of odd degree.

**Theorem:** A connected graph has a Eulerian tour if and only if all vertex degrees are even. A graph with a Eulerian tour is not necessarily connected. However, all edges need to be in the same connected component. In other words, the graph needs to be connected after removing isolated vertices.

One direction of the statement of the theorem is easy to prove. In a closed walk

To prove the other direction, we exhibit an algorithm that outputs a Eulerian tour in a connected graph whenever all vertex degrees are even.

*Note:* A similar theorem holds for Eulerian (non-closed) walks in connected graphs. We just need to account for up to two vertices with odd degrees. We can reduce questions about Eulerian walks to questions about Eulerian tours by adding a new vertex adjacent to the two odd-degree vertices if needed (see fig. 2).

## 7. Iterative approach

Instead of aiming at directly computing a Eulerian tour, we first consider simpler but related tasks.

For example, we could start by computing any closed walk (of length larger than

Indeed, if we can find such a list of closed walks for a connected graph, we can obtain a Eulerian tour by merging the closed walks as illustrated in the example fig. 3. We can always merge two closed walks that share a vertex to a single closed walk that uses the same edges. In a connected graph, we can keep merging in this way until only one closed walk remains that uses every edge exactly once.

To summarize, we consider the following approach for computing a Eulerian tour:

- iteratively compute closed walks
until every edge ised exactly once${Z}_{1},\dots ,{Z}_{k}$ - merge the closed walks to a Eulerian tour

In the following, we show how to carry out the first step for graphs without odd degree vertices.

## 8. Walking in graphs

We consider the following recursive procedure for finding a maximal walkHere, maximal means that the walk cannot be extended further. We don’t require the walk to have maximum length. starting in a vertex

`Walk`

(

- If there exists an unmarked edge
incident to$uv\in E$ :$u$ - Mark the edge
.$uv$ - Run
`Walk`

( ).$v$

- Mark the edge

We take note of a few properties of this procedure:

- The procedure
`Walk`

( ) marks a walk$u$ starting in$W$ .$u$ - Every edge gets marked at most once.
- The walk
ends in a vertex$W$ such that all edges incident to$v$ are marked.$v$

The second property holds because we never undo markings and we check that an edge is unmarked before marking it. The reason the third property holds is that in the last call of `Walk`

(

In the previous example (fig. 3), suppose we start with no edges marked and run the `Walk`

procedure first on B and then on E (without undoing the markings made by `Walk`

(B)). Then, we mark the following walks, assuming we process the edges in alphabetical order:

procedure call | marked walk |
---|---|

`Walk` (B): |
B A C B D E F B |

`Walk` (E): |
E G H E |

In order to analyze the `Walk`

procedure we propose the following property as an invariant:

`ALL-EVEN`

: every vertex is incident to an even number of unmarked edges

If all edges are unmarked and all vertex degrees are even, then `ALL-EVEN`

holds.

**Claim:** If `ALL-EVEN`

holds before running `Walk`

(`Walk`

(`Walk`

(

*Proof:* It is enough to prove that `ALL-EVEN`

also holds after `Walk`

(

Suppose

We know that before running `Walk`

(`ALL-EVEN`

held at that time). After running `Walk`

(`Walk`

procedure we noted). Hence, `Walk`

(

The claim implies that we can partition the edges of any graph without odd degree vertices into a collection of closed walks by repeatingly running the `Walk`

routing on vertices with unmarked edges until all edges are marked.

## 9. Fast algorithm

While the approach we have discussed so far allows us to compute a Eulerian tour in polynomialHere, we are not referring to any specific running times (like quadratic, cubic, and so on). As we will see later, the specific running times will depend on the kind of data structures we use to represent graphs. time, we need additional ideas in order to achieve linear running time.

As a starting point, we consider the following question: After one call of the `Walk`

routine has finished, which vertex should we choose as the start for the next call of the `Walk`

routine?

The idea is to backtrack in the walks we have computed so far. For example, suppose in fig. 3 we run `Walk`

(A) and mark the walk A B C A. Then, we backtrack in this walk two steps, A C B, and arrive at vertex B with unmarked edges incident to it. We run `Walk`

(B) and mark the walk B D E F B. We backtrack two steps, B F B, and arrive at vertex E. Finally, we run `Walk`

(E) and mark the walk E G H E. At this point all edges are marked.

To implement the idea of backtracking along the walks we have already found, we will use the following recursive procedure to build up a list

`Euler-Walk`

(

- For the edges
incident to$uv\in E$ :$u$ - If the edge
is not yet marked, mark the edge$uv$ and run$uv$ `Euler-Walk`

( ).$v$

- If the edge
- Append
to the end of the list$u$ .$Z$

Using `Euler-Walk`

as a subroutine, the following procedure find a Eulerian tour in a connected graph

`Euler`

(G):

- Initalize
as an empty list and all vertices to be unmarked.$Z$ - Run
`Euler-Walk`

( ) for an arbitraryFor a connected graph, we can choose the start vertex${u}_{0}$ to be arbitrary. If we allow the underlying graph to have isolated vertices, we should choose${u}_{0}$ to be a non-isolated vertex if one exists. vertex${u}_{0}$ .${u}_{0}\in V$ - Output the final content of the list
.$Z$

Recursion tree of the procedure `Euler-Walk`

applied to vertex A for the example graph in fig. 3. The red numbers indicate the order in which vertices are appended to the list

The content of the final list

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|

A | C | B | F | E | H | G | E | D | B | A |

## 10. Running time with adjacency matrix

In order to analyze the running time of `Euler`

(

Let

**Definition:** The *adjacency matrix*

For example, the graph in fig. 4 has the following adjacency matrix (with the red entries of the matrix corresponding to the red edge in the graph):

**Running times of basic operations on adjacency matrices:**

- Given two vertices
, we can test if$u,v\in V$ in time$uv\in E$ .$O(1)$ - Given a vertex
, we can enumerate the neighbors of$u\in V$ in time$u$ .$O(n)$

**Claim:** `Euler`

(

*Proof:* It suffices to bound the time for `Euler-Walk`

(`Euler-Walk`

is associated with with an edge in

Hence, the total number of calls of `Euler-Walk`

is at mostIndeed, if the graph is connected and has a Eulerian tour, then the number of calls of `Euler-Walk`

is equal to

For any individual call of `Euler-Walk`

, the number of elementary operations carried out while this call is active (i.e., not counting operations carried out inside nested recursive calls) is

Hence, the total running time is

## 11. Running time with adjacency lists

The main weakness of representing graphs by their adjacency matrix is that enumerating the neighbors of a vertex takes time

A better representation of a graph are its adjacency lists. For example, the graph in fig. 4 has the following adjacency list representation:

1 | 2 | 3 | 4 |
---|---|---|---|

(2,4) | (3,1,4) | (4,2) | (1,3,2) |

Let

**Definition:** The adjacency list representation of a graph

**Running times of basic operations on adjacency list representations:**

- Given two vertices
, we can test if$u,v\in V$ in time$uv\in E$ .$O(1+min\{\mathrm{d}\mathrm{e}\mathrm{g}(u),\mathrm{d}\mathrm{e}\mathrm{g}(v)\})$ - Given a vertex
, we can enumerate the neighbors of$u\in V$ in time$v$ .$O(1+\mathrm{d}\mathrm{e}\mathrm{g}(u))$

Per our convention,

**Claim:** The running time to enumerate all edges of

*Proof:* Using this fact that enumerating the neighbors of a single vertex

Note that without the additive 1 term, we might have been tempted to conclude a running time bound of

**Claim:** `Euler`

(

*Proof:* In order to implement `Euler-Walk`

(

To bound the running time of `Euler-Walk`

(`Euler-Walk`

calls that we make during `Euler`

(`Euler`

(`Euler-Walk`

. The number of operations for the `Euler-Walk`

is `Euler-Walk`

calls is at most `Euler-Walk`

calls is `Euler-Walk`

(

Hence, the total running time of `Euler-Walk`

(

The initialization phase of `Euler`

(

Thus, the total running itme of `Euler`

(

## 12. Correctness

In this section, we will prove the correctness of the algorithm developed in the previous section.

**Lemma:** For a connected graph

To prove this lemma, we imagine a tortoise and hareSee Aesop’s Fable “The Tortoise and the Hare”. For our proof, the two protagonists give us a non-recursive way to think about the behavior of the `Euler-Walk`

procedure. using the recursion tree `Euler-Walk`

(

First, we note that each edge of `Euler-Walk`

traverses an edge only if it hasen’t been traversed before, it follows that no edge of `Euler-Walk`

finishes only if all edges of a vertex have been traversed, it also follows that each edge of

Next, we describe how the hare and tortoise move in the recursion tree

The hare walks in `Euler-Walk`

that has finished. In general, we order the leafs of `Euler-Walk`

has finished. leaf, from the first leaf to the second leaf, and so on. Finally, it walks from the last leaf back to the root. In this way, the hare traverses every edge of `Euler-Walk`

procedure. Moving down the tree (away from the root) corresponds to starting a new recursive call. Moving up the tree (toward the root) corresponds to finishing a recursive call.

The tortoise is waiting at the first leaf of `Euler-Walk`

for the lower vertex, the sequence of vertices visited by the tortoise, ignoring the vertices it jumped from, equals the content of the final list `Euler`

.

Since each vertex and each edge of

**Claim:** The root and the first leaf of

This claim shows that the jumps of the tortoise in `Euler`

. As noted before, there is a one-to-one correspondence between the edges in

Hence, to establish the lemma, it remains to prove the claim.

*Proof:* In order to prove this claim, we use the fact that the `Euler-Walk`

procedure behaves the sameIn order to get a direct correspondence between `Euler-Walk`

and `Walk`

, we shall assume that both procedures process unmarked edges incident to a vertex in the same order (e.g., according to the alphabetical order of the labels of the neighbors). as the `Walk`

procedure from sec. 8 except for branching. We will show that the execution of `Euler-Walk`

(`Walk`

procedure.

As part of the proof of the above claim, we will show the following statement by induction on

: If we mark all edges in $P(i)$ visited by the hare until reaching leaf $G$ of $i$ , then $T$ `ALL-EVEN`

is satisfied (see sec. 8).

Consider the path in `Euler-Walk`

and `Walk`

, we shall assume that both procedures process unmarked edges incident to a vertex in the same order (e.g., according to the alphabetical order of the labels of the neighbors). to the (non-branching) recursion tree of `Walk`

(`Walk`

(`ALL-EVEN`

is satisfied in

It also follows that `Walk`

procedure maintains the `ALL-EVEN`

invariant.

We are to show that `ALL-EVEN`

is satisfied. Consider the lower lowest common ancestor `Walk`

(`Euler-Walk`

represented by `Euler-Walk`

. Alternatively, we can simulate this branching by calling the `Walk`

procedure several times from this vertex. as the path from `Walk`

in sec. 8, this path corresponds to a closed walk in `Walk`

procedure maintains the `ALL-EVEN`

invariant.