The first problem in graph theory dates to 1735, and is called the Seven Bridges of Königsberg. In Königsberg were two islands, connected to each other and the mainland by seven bridges, as shown in figure 5.2.1. The question, which made its way to Euler, was whether it was possible to take a walk and cross over each bridge exactly once; Euler showed that it is not possible.
We can represent this problem as a graph, as in figure 5.2.2.
The two sides of the river are represented by the top and bottom vertices, and the islands by the middle two vertices. There are two possible interpretations of the question, depending on whether the goal is to end the walk at its starting point. Perhaps inspired by this problem, a walk in a graph is defined as follows.
Definition 5.2.1 A walk in a graph is a sequence of vertices and edges, $$v_1,e_1,v_2,e_2,\ldots,v_k,e_k,v_{k+1}$$ such that the endpoints of edge $e_i$ are $v_i$ and $v_{i+1}$. In general, the edges and vertices may appear in the sequence more than once. If $v_1=v_{k+1}$, the walk is a closed walk or a circuit. $\square$
We will deal first with the case in which the walk is to start and end at the same place. A successful walk in Königsberg corresponds to a closed walk in the graph in which every edge is used exactly once.
What can we say about this walk in the graph, or indeed a closed walk in any graph that uses every edge exactly once? Such a walk is called an Euler circuit. If there are no vertices of degree 0, the graph must be connected, as this one is. Beyond that, imagine tracing out the vertices and edges of the walk on the graph. At every vertex other than the common starting and ending point, we come into the vertex along one edge and go out along another; this can happen more than once, but since we cannot use edges more than once, the number of edges incident at such a vertex must be even. Already we see that we're in trouble in this particular graph, but let's continue the analysis. The common starting and ending point may be visited more than once; except for the very first time we leave the starting vertex, and the last time we arrive at the vertex, each such visit uses exactly two edges. Together with the edges used first and last, this means that the starting vertex must also have even degree. Thus, since the Königsberg Bridges graph has odd degrees, the desired walk does not exist.
The question that should immediately spring to mind is this: if a graph is connected and the degree of every vertex is even, is there an Euler circuit? The answer is yes.
Theorem 5.2.2 If $G$ is a connected graph, then $G$ contains an Euler circuit if and only if every vertex has even degree.
Proof. We have already shown that if there is an Euler circuit, all degrees are even.
We prove the other direction by induction on the number of edges. If $G$ has no edges the problem is trivial, so we assume that $G$ has edges.
We start by finding some closed walk that does not use any edge more than once: Start at any vertex $v_0$; follow any edge from this vertex, and continue to do this at each new vertex, that is, upon reaching a vertex, choose some unused edge leading to another vertex. Since every vertex has even degree, it is always possible to leave a vertex at which we arrive, until we return to the starting vertex, and every edge incident with the starting vertex has been used. The sequence of vertices and edges formed in this way is a closed walk; if it uses every edge, we are done.
Otherwise, form graph $G'$ by removing all the edges of the walk. $G'$ is not connected, since vertex $v_0$ is not incident with any remaining edge. The rest of the graph, that is, $G'$ without $v_0$, may or may not be connected. It consists of one or more connected subgraphs, each with fewer edges than $G$; call these graphs $G_1$, $G_2$,…,$G_k$. Note that when we remove the edges of the initial walk, we reduce the degree of every vertex by an even number, so all the vertices of each graph $G_i$ have even degree. By the induction hypothesis, each $G_i$ has an Euler circuit. These closed walks together with the original closed walk use every edge of $G$ exactly once.
Suppose the original closed walk is $v_0,v_1,\ldots,v_m=v_0$, abbreviated to leave out the edges. Because $G$ is connected, at least one vertex in each $G_i$ appears in this sequence, say vertices $w_{1,1}\in G_1$, $w_{2,1}\in G_2$,…, $w_{k,1}\in G_k$, listed in the order they appear in $v_0,v_1,\ldots,v_m$. The Euler circuits of the graphs $G_i$ are $$\eqalign{ &w_{1,1},w_{1,2},\ldots,w_{1,m_1}=w_{1,1}\cr &w_{2,1},w_{2,2},\ldots,w_{2,m_2}=w_{2,1}\cr &\vdots\cr &w_{k,1},w_{k,2},\ldots,w_{k,m_k}=w_{k,1}.\cr }$$ By pasting together the original closed walk with these, we form a closed walk in $G$ that uses every edge exactly once: $$\eqalign{ v_0,v_1,&\ldots,v_{i_1}=w_{1,1},w_{1,2},\ldots,w_{1,m_1}=v_{i_1},v_{i_1+1},\cr &\ldots, v_{i_2}=w_{2,1},\ldots,w_{2,m_2}=v_{i_2},v_{i_2+1},\cr &\ldots,v_{i_k}=w_{k,1},\ldots,w_{k,m_k}=v_{i_k}, v_{i_k+1},\ldots,v_m=v_0.\cr }$$ $\qed$
Now let's turn to the second interpretation of the problem: is it possible to walk over all the bridges exactly once, if the starting and ending points need not be the same? In a graph $G$, a walk that uses all of the edges but is not an Euler circuit is called an Euler walk. It is not too difficult to do an analysis much like the one for Euler circuits, but it is even easier to use the Euler circuit result itself to characterize Euler walks.
Theorem 5.2.3 A connected graph $G$ has an Euler walk if and only if exactly two vertices have odd degree.
Proof. Suppose first that $G$ has an Euler walk starting at vertex $v$ and ending at vertex $w$. Add a new edge to the graph with endpoints $v$ and $w$, forming $G'$. $G'$ has an Euler circuit, and so by the previous theorem every vertex has even degree. The degrees of $v$ and $w$ in $G$ are therefore odd, while all others are even.
Now suppose that the degrees of $v$ and $w$ in $G$ are odd, while all other vertices have even degree. Add a new edge $e$ to the graph with endpoints $v$ and $w$, forming $G'$. Every vertex in $G'$ has even degree, so by the previous theorem there is an Euler circuit which we can write as $$v,e_1,v_2,e_2,\ldots,w,e,v$$ so that $$v,e_1,v_2,e_2,\ldots,w$$ is an Euler walk. $\qed$
Exercises 5.2
Ex 5.2.1 Suppose a connected graph $G$ has degree sequence $d_1,d_2,\ldots,d_n$. How many edges must be added to $G$ so that the resulting graph has an Euler circuit? Explain.
Ex 5.2.2 Which complete graphs $K_n$, $n\ge 2$, have Euler circuits? Which have Euler walks? Justify your answers.
Ex 5.2.3 Prove that if vertices $v$ and $w$ are joined by a walk they are joined by a path.
Ex 5.2.4 Show that if $G$ is connected and has exactly $2k$ vertices of odd degree, $k\ge1$, its edges can be partitioned into $k$ walks. Is this true for non-connected $G$?