# Euler and Hamiltonian Paths and Circuits

In the next lesson, we will investigate specific kinds of paths through a graph called Euler paths and circuits. Euler paths are an optimal path through a graph. They are named after him because it was Euler who first defined them. By counting the number of vertices of a graph, and their degree we can determine whether a graph has an Euler path or circuit. We will also learn another algorithm that will allow us to find an Euler circuit once we determine that a graph has one.### Learning Objectives

- Determine whether a graph has an Euler path and/ or circuit
- Use Fleury's algorithm to find an Euler circuit
- Add edges to a graph to create an Euler circuit if one doesn't exist
- Identify whether a graph has a Hamiltonian circuit or path
- Find the optimal Hamiltonian circuit for a graph using the brute force algorithm, the nearest neighbor algorithm, and the sorted edges algorithm
- Identify a connected graph that is a spanning tree
- Use Kruskal's algorithm to form a spanning tree, and a minimum cost spanning tree

## Euler Circuits

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 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.

### Example

In the graph shown below, there are several Euler paths. One such path is CABDCB. The path is shown in arrows to the right, with the order of edges numbered.### 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.

### Example

The graph below has several possible Euler circuits. Here’s a couple, starting and ending at vertex A: ADEACEFCBA and AECABCFEDA. The second is shown in arrows.*exists*. 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. That’s an Euler circuit! 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### Example

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. This graph contains two vertices with odd degree (D and E) and three vertices with even degree (A, B, and C), so Euler’s theorems tell us this graph has an Euler path, but not an Euler circuit.### Example

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.### Example

When it snows in the same housing development, the snowplow has to plow both sides of every street. For simplicity, we’ll assume the plow is out early enough that it can ignore traffic laws and drive down either side of the street in either direction. This can be visualized in the graph by drawing two edges for each street, representing the two sides of the street.### Fleury's Algorithm

### Fleury’s Algorithm

### Eulerization and the Chinese Postman Problem

Not every graph has an Euler path or circuit, yet our lawn inspector still needs to do her inspections. Her goal is to minimize the amount of walking she has to do. In order to do that, she will have to duplicate some edges in the graph until an Euler circuit exists.### Eulerization

**Eulerization**is the process of adding edges to a graph to create an Euler circuit on a graph. To eulerize a graph, edges are duplicated to connect pairs of vertices with odd degree. Connecting two odd degree vertices increases the degree of each, giving them both even degree. When two odd degree vertices are not directly connected, we can duplicate all edges in a path connecting the two.

### Example

### Example

## Hamiltonian Circuits

### The Traveling Salesman Problem

In the last section, we considered optimizing a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.### Hamiltonian Circuits and Paths

**Hamiltonian circuit**is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A

**Hamiltonian path**also visits every vertex once with no repeats, but does not have to start and end at the same vertex.

### Example

### Example

Does a Hamiltonian path or circuit exist on the graph below? We can see that once we travel to vertex E there is no way to leave without returning to C, so there is no possibility of a Hamiltonian circuit. If we start at vertex E we can find several Hamiltonian paths, such as ECDAB and ECABD### try it now

**complete graph.**Suppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next. There is then only one choice for the last city before returning home. This can be shown visually:

### Number of Possible Circuits

*N*vertices in a complete graph, there will be [latex](n-1)!=(n-1)(n-2)(n-3)\dots{3}\cdot{2}\cdot{1}[/latex] routes. Half of these are duplicates in reverse order, so there are [latex]\frac{(n-1)!}{2}[/latex] unique circuits. The exclamation symbol, !, is read “factorial” and is shorthand for the product shown.

### Example

Cities |
Unique Hamiltonian Circuits |

9 | 8!/2 = 20,160 |

10 | 9!/2 = 181,440 |

11 | 10!/2 = 1,814,400 |

15 | 14!/2 = 43,589,145,600 |

20 | 19!/2 = 60,822,550,204,416,000 |

**not**an efficient algorithm.

### Nearest Neighbor Algorithm (NNA)

*and*optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to

**heuristic algorithms**; efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit.

### Example

**greedy**algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge AD forced us to use the very expensive edge BC later.

### Example

### Example

### try it now

The table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP. The computers are labeled A-F for convenience.A | B | C | D | E | F | |

A | -- | 44 | 34 | 12 | 40 | 41 |

B | 44 | -- | 31 | 43 | 24 | 50 |

C | 34 | 31 | -- | 20 | 39 | 27 |

D | 12 | 43 | 20 | -- | 11 | 17 |

E | 40 | 24 | 39 | 11 | -- | 42 |

F | 41 | 50 | 27 | 17 | 42 | -- |

### Example

### Example

*Derivative Work*, is doing a bar tour in Oregon. The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Use NNA starting at Portland, and then use Sorted Edges.

Ashland | Astoria | Bend | Corvallis | Crater Lake | Eugene | Newport | Portland | Salem | Seaside | |

Ashland | - | 374 | 200 | 223 | 108 | 178 | 252 | 285 | 240 | 356 |

Astoria | 374 | - | 255 | 166 | 433 | 199 | 135 | 95 | 136 | 17 |

Bend | 200 | 255 | - | 128 | 277 | 128 | 180 | 160 | 131 | 247 |

Corvallis | 223 | 166 | 128 | - | 430 | 47 | 52 | 84 | 40 | 155 |

Crater Lake | 108 | 433 | 277 | 430 | - | 453 | 478 | 344 | 389 | 423 |

Eugene | 178 | 199 | 128 | 47 | 453 | - | 91 | 110 | 64 | 181 |

Newport | 252 | 135 | 180 | 52 | 478 | 91 | - | 114 | 83 | 117 |

Portland | 285 | 95 | 160 | 84 | 344 | 110 | 114 | - | 47 | 78 |

Salem | 240 | 136 | 131 | 40 | 389 | 64 | 83 | 47 | - | 118 |

Seaside | 356 | 17 | 247 | 155 | 423 | 181 | 117 | 78 | 118 | - |

*To see the entire table, scroll to the right*

Using NNA with a large number of cities, you might find it helpful to mark off the cities as they’re visited to keep from accidently visiting them again. Looking in the row for Portland, the smallest distance is 47, to Salem. Following that idea, our circuit will be:

Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree 3.

We start adding the shortest edges:

Seaside to Astoria 17 miles

Corvallis to Salem 40 miles

Portland to Salem 47 miles

Corvallis to Eugene 47 miles

Newport to Astoria (reject – closes circuit)

Newport to Bend 180 miles

Bend to Ashland 200 miles

At this point the only way to complete the circuit is to add:

Crater Lk to Astoria 433 miles. The final circuit, written to start at Portland, is:

Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Crater Lake, Astoria, Seaside, Portland. Total trip length: 1241 miles.

While better than the NNA route, neither algorithm produced the optimal route. The following route can make the tour in 1069 miles:

Portland, Astoria, Seaside, Newport, Corvallis, Eugene, Ashland, Crater Lake, Bend, Salem, Portland

### try it now

[1] There are some theorems that can be used in specific circumstances, such as Dirac’s theorem, which says that a Hamiltonian circuit must exist on a graph with*n*vertices if each vertex has degree

*n*/2 or greater.

## Licenses & Attributions

### CC licensed content, Original

- Revision and Adaptaion.
**Provided by:**Lumen Learning**License:**CC BY: Attribution. - Learning Outcomes and Introduction.
**Provided by:**Lumen Learning**License:**CC BY: Attribution.

### CC licensed content, Shared previously

- Graph Theory: Euler Paths and Euler Circuits .
**Authored by:**James Sousa (Mathispower4u.com).**License:**CC BY: Attribution. - Math in Society.
**Authored by:**Lippman, David.**License:**CC BY: Attribution. - Graph Theory: Fleury's Algorthim .
**Authored by:**James Sousa (Mathispower4u.com).**License:**CC BY: Attribution. - Hamiltonian circuits.
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Hamiltonian circuits .
**Authored by:**David Lippman.**License:**CC BY: Attribution. - TSP by brute force .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Number of circuits in a complete graph .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Nearest Neighbor ex2 .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Sorted Edges ex 2 .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Kruskal's ex 1 .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Kruskal's from a table .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution.