The entire field of graph theory began when Euler asked whether the seven bridges of Konigsberg could all be crossed exactly once. Abstractly, we can represent the parts of the city separated by rivers as vertices and the bridges as edges between the vertices. Then Euler's question asks whether there is a closed walk through the graph that includes every edge in a graph exactly once. In his honor, such a walk is called an Euler tour. So how do you tell in general whether a graph has an Euler tour? At first glance this may seem like a daunting problem. The similar sounding problem of finding a cycle that touches every vertex exactly once is one of those Millenium Prize NP-complete problems known as the Traveling Salesman Problem). But it turns out to be easy to characterize which graphs have Euler tours. Theorem. A connected graph has an Euler tour and only if every vertex has even degree. (a) Show that if a graph has an Euler tour, then the degree of each of its vertices is even. In the remaining parts, we'll work out the converse: if the degree of every vertex of a connected finite graph is even, then it has an Euler tour. To do this, let's define an Euler walk to be a walk that includes each edge at most once. (b) Suppose that an Euler walk in a connected graph does not include every edge. Explain why there must be an unincluded edge that is incident to a vertex on the walk. In the remaining parts, let w be the longest Euler walk in some finite, connected graph. (c) Show that if w is a closed walk, then it must be an Euler tour. (d) Explain why all the edges incident to the end of w must already be in w. (e) Show that if the end of w was not equal to the start of w, then the degree of the end would be odd. (f) Conclude that if every vertex of a finite, connected graph has even degree, then it has an Euler tour