What makes a euler circuit

The degree of each vertex is labeled in red. The ordering of the edges of the circuit is labeled in blue and the direction of the circuit is shown with the blue arrows. Definition: Euler Path A path that travels through every edge of a connected graph once and only once and starts and ends at different vertices.

Definition: Euler Circuit An Euler path that starts and ends at the same vertex. Therefore, the number of vertices of odd degree must be even. Finding Euler Circuits Be sure that every vertex in the network has even degree. Begin the Euler circuit at any vertex in the network. As you choose edges, never use an edge that is the only connection to a part of the network that you have not already visited. An Euler path is a path that uses every edge in a graph with no repeats.

Being a path, it does not have to return to the starting vertex. In the graph shown below, there are several Euler paths. The path is shown in arrows to the right, with the order of edges numbered. An Euler circuit is a circuit that uses every edge in a graph with no repeats. Being a circuit, it must start and end at the same vertex. The graph below has several possible Euler circuits. The second is shown in arrows.

Look back at the example used for Euler paths—does that graph have an Euler circuit? A few tries will tell you no; that graph does not have an Euler circuit. When we were working with shortest paths, we were interested in the optimal path. Why do we care if an Euler circuit exists? Think back to our housing development lawn inspector from the beginning of the chapter. The lawn inspector is interested in walking as little as possible.

The ideal situation would be a circuit that covers every street with no repeats. Luckily, Euler solved the question of whether or not an Euler path or circuit will exist. In the graph below, vertices A and C have degree 4, since there are 4 edges leading into each vertex.

B is degree 2, D is degree 3, and E is degree 1. Is there an Euler circuit on the housing development lawn inspector graph we created earlier in the chapter?

All the highlighted vertices have odd degree. Since there are more than two vertices with odd degree, there are no Euler paths or Euler circuits on this graph. Unfortunately our lawn inspector will need to do some backtracking. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler path. You will end at the vertex of degree 3.

You run into a similar problem whenever you have a vertex of any odd degree. If you start at such a vertex, you will not be able to end there after traversing every edge exactly once. After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave.

The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree that you do not start a path at, then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to arrive and leave again.

Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again. What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at one of the odd degree vertices and end at the other.

In such a situation, every other vertex must have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree. The converse is also true: if all the vertices of a graph have even degree, then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler path.

A graph has an Euler path if and only if there are at most two vertices with odd degree. Thus there is no way for the townspeople to cross every bridge exactly once. This can be done. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path or Hamiltonian path. We could also consider Hamilton cycles , which are Hamliton paths which start and stop at the same vertex. The graph on the left has a Hamilton path many different ones, actually , as shown here:.

The graph on the right does not have a Hamilton path. Note that this graph does not have an Euler path, although there are graphs with Euler paths but no Hamilton paths.

It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. However, nobody knows whether this is true. There is no known simple test for whether a graph has a Hamilton path.

For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check wither there is a Hamilton path. In fact, this is an example of a question which as far as we know is too difficult for computers to solve; it is an example of a problem which is NP-complete.