Euler and Hamiltonian Paths and Circuits: Learn It 1

  • Determine whether a graph has an Euler path or circuit and use Fleury’s algorithm to find an Euler circuit
  • Recognize whether a graph contains a Hamiltonian circuit or path and determine the optimal Hamiltonian circuit using various algorithms
  • Identify a connected graph as a spanning tree and utilize Kruskal’s algorithm to create both a spanning tree and a minimum-cost spanning tree

In the first section, we created a graph of the Königsberg bridges and asked whether it was possible to walk across every bridge once. Because Euler first studied this question, these types of paths are named after him.

Euler Circuits

Euler path

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. One such path is [latex]CABDCB[/latex]. The path is shown in arrows to the right, with the order of edges numbered.

A graph with four vertices and five edges. Vertex A has edges connecting to Vertices B and C. Vertex B has edges connecting to Vertices A, C, and D. Vertex C has edges connecting to Vertices A, B, and D. Vertex D has edges connecting to Vertices B and C. An Euler path is shown. Path: CABDCB.

Euler circuit

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. Here’s a couple, starting and ending at vertex [latex]A[/latex]: [latex]ADEACEFCBA[/latex] and [latex]AECABCFEDA[/latex]. The second is shown in arrows.

 

A graph with six vertices and nine edges. Vertex A has edges connecting to Vertices B, C, and D. Vertex B has edges connecting to Vertices C and A. Vertex C has edges connecting to Vertices A, B, E, and F. Vertex D has edges connecting to Vertices A and E. Vertex E has edges connecting to Vertices A, C, D, and F. Vertex F has edges connecting to Vertices C and E. An Euler circuit is shown. Circuit: AECABCFEDA.

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. With Euler paths and circuits, we’re primarily interested in whether an Euler path or circuit exists.

Why do we care if an Euler circuit exists? We care if an Euler circuit exists because it can help us solve problems, such as determining the most efficient route for a traveling salesperson or the optimal path for a network of roads. By finding an Euler circuit, we can ensure that every edge in the graph is visited exactly once, which can help us to avoid redundancy or inefficiency in our solutions. Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.

Euler’s path and circuit theorems

A graph will contain an Euler path if it contains at most two vertices of odd degree.

A graph will contain an Euler circuit if all vertices have even degree

In the graph below, vertices [latex]A[/latex] and [latex]C[/latex] have degree [latex]4[/latex], since there are [latex]4[/latex] edges leading into each vertex. [latex]B[/latex] is degree [latex]2[/latex], [latex]D[/latex] is degree [latex]3[/latex], and [latex]E[/latex] is degree [latex]1[/latex]. This graph contains two vertices with odd degree ([latex]D[/latex] and [latex]E[/latex]) and three vertices with even degree ([latex]A[/latex], [latex]B[/latex], and [latex]C[/latex]), so Euler’s theorems tell us this graph has an Euler path, but not an Euler circuit.

A graph containing two vertices with odd degrees and three vertices with even degrees.