Instead of a configuration of islands and bridges, let us discuss the graph corresponding to it. We’ll say the graph is traversable if we can find a walk that goes over every edge precisely once, and refer to such a walk as an Euler walk in the graph. We also say a graph is Eulerian if it has such a walk. A closed Euler walk is also called an Euler circuit.

In our discussion of the Königsberg bridges, we observed that an odd vertex could be at the start of the walk or at the finish. So, if a graph is traversable, it can have at most two odd vertices. You can’t have an odd number of odd vertices, so there can be either two odd vertices (one will be the start, the other the finish), or none (the walk begins and ends at the same vertex). We’ll refer to the walk as closed if the start equals the finish, and open otherwise.

So, if a graph has an Euler walk, all the degrees of its vertices or all but two of them must be even. Another obvious condition is that the graph must be connected,  or else no single walk could cover all the edges. In fact, Euler showed that these necessary conditions are also sufficient. Formally, his result can be stated as:

 If a connected graph has no odd vertices, then it has an Euler walk starting from any given point and finishing at that point. If there are two odd vertices, then there is an Euler walk whose ends are the odd vertices.

To see how his reasoning works, we consider any simple walk in a graph that starts and finishes at the same vertex. If one erases every edge in that walk, one deletes two edges touching any vertex that was crossed once in the walk, four edges touching any vertex that was crossed twice, and so on. (For this purpose, count  “start” and “finish” combined as one crossing.) In every case an even number of edges is deleted.

First, consider a graph with no odd vertex. Select any vertex x, and select any edge incident with x. Go along this edge to its other endpoint, say y. Then choose any other edge incident with y. In general, on arriving at a vertex, select any edge incident with it that has not yet been used, and go along the edge to its other endpoint. At the moment when this walk has led into the vertex z, where z is not x,  an odd number of edges touching z has been used up (the last edge to be followed,  and an even number previously). Since z is even, there is at least one edge incident with z that is still available. Therefore, if the walk is continued until a further edge is impossible, the last vertex must be x—that is, the walk is closed. It will necessarily be a simple walk and it must contain every edge incident with vertex x.

Now assume that a connected graph with every vertex even is given, and a simple closed walk has been found in it by the method just described. Delete all the edges in the walk, forming a new graph. From the preceding paragraph it follows that every vertex of the new graph is even. It may be that we have erased every edge in the original graph; in that case we have already found an Euler walk. If there are edges still left, there must be at least one vertex, say c, that was in the original walk and that is still on an edge in the new graph—if there were no such vertex, then there could be no connection between the edges of the walk and the edges left in the new graph, and the original graph must have been disconnected. Select such a vertex c,  and find a closed simple walk starting from c. Then unite the two walks as follows:

at one place where the original walk contained c, insert the new walk. For example,

if the two walks are

                                                          x,y,...,z,c,u,...,x

and

                                                                      c,s,...,t,c,

then the resulting walk will be

                                                     x,y,...,z,c,s,...,t,c,u,...,x.

(There may be more than one possible answer if c occurred more than once in the first walk. Any of the possibilities may be chosen.) The new walk is a closed simple walk in the original graph. Repeat the process of deletion, this time deleting the newly formed walk. Continue in this way. Each walk contains more edges than the preceding one, so the process cannot go on indefinitely. It must stop: this will only happen when one of the walks contains all edges of the original graph, and that walk is an Euler walk.

Finally, consider the case where there are two odd vertices p and q and every other vertex is even. Form a new graph by adding an edge pq to the original (it might duplicate an existing edge, or it might not). This new graph has every vertex even.

Find a closed Euler walk in it, choosing p as the first vertex and the new edge pq as the first edge. Then delete this first edge; the result is an Euler walk from q to p.

                      Fig. 1.1 Find Euler walk

              Fig. 1.2Constructing an Euler wa