4.05 Eulerian and Hamiltonian graphs

Consider the following graphs. Check that you can start at one vertex and travel along each edge exactly once without lifting your pen from the paper.

Each graph has a trail that uses every edge exactly once. The trail on the left is open and starts and finishes at different vertices. The graph on the right is closed and any vertex can be the start/end.

Traversable is the word to describe graphs where you can start at a vertex and draw in all the edges without taking your pen off the page or retracing any edge. The two types of traversable graphs are:

• If a graph has a closed trail (it starts and finishes at the same vertex) that uses every edge, it is called Eulerian (named after the same Euler who gave us the formula v+f-e=2). It can also be called an Eulerian trail or an Eulerian circuit.

• If a graph has an open trail (it starts and finishes at different vertices) that uses every edge, it is described as semi-Eulerian. It can also be called a semi-Eulerian trail.

It is possible to determine if an undirected graph is Eulerian or semi-Eulerian without having to actually find the trail:

• If a graph has exactly two vertices of odd degree, then the graph is semi-Eulerian. These two vertices will be the start and the end of the open semi-Eulerian trail.

• If a graph has all even vertices, then the graph is Eulerian. The closed Eulerian trail can start at any vertex.

Examples

Example 1

Suppose G is a very large network, with 300 vertices, each of even degree.

a

Does a semi-Eulerian trail exist for G?

A

Yes, as there are exactly two vertices of odd degree.

B

Yes, as there are no vertices with odd degree.

C

Yes, as there are an even number of even vertices and an even number of odd vertices.

D

No, as there are no vertices with odd degree.

Worked Solution

Create a strategy

A graph needs to have exactly two vertices of odd degree to to have a semi-Eulerian trail.

Apply the idea

All the vertices of network G are of even degree. So there cannot be a semi-Eulerian trail.

So the correct answer is option D.

b

Does an Eulerian circuit exist for G?

A

Yes, as there are no vertices with odd degree.

B

Yes, as there are an even number of even vertices and an even number of odd vertices.

C

Yes, as there are exactly two vertices of odd degree.

D

No, as there are no vertices with odd degree.

Worked Solution

Create a strategy

If a graph has all even degree vertices, the graph is Eulerian.

Apply the idea

Since all the vertices of network G are of even degree, an Eulerian circuit exists. So the correct answer is option A.

Example 2

Consider the following network:

a

Is it possible to draw an Eulerian circuit on the diagram?

Worked Solution

Create a strategy

Check if every vertex of the network has an even degree.

Apply the idea

Vertex	Degree
A	4
B	2
C	4
D	2
E	2
F	4
G	2

The table shows the degree of each vertex.

Since the degree of each vertex is even, yes, it is possible to draw an Eulerian circuit on the network.

Watch question walkthrough

b

Write an Eulerian circuit starting and ending with the vertex B.

Worked Solution

Create a strategy

Find a circuit that passes over all edges only once, starting and ending at vertex B.

Apply the idea

Starting at B, we can either go left or right. If we go to A, we can follow the following circut to cover every edge:\text{Eulerian circuit} = B,\,A,\,G,\,F,\,A,\,D,\,C,\,F,\,E,\,C,\,B

Reflect and check

You may need to use trial and error to find a circuit that does not pass over the same edge twice.

Another solution is: \text{Eulerian circuit} = B,\,A,\,G,\,F,\,E,\,C,\,D,\,A,\,F,\,C,\,B

Watch question walkthrough

Example 3

Consider the network below:

a

Is the network Eulerian or semi-Eulerian?

A

The graph is Eulerian (it can be traversed and starts and ends at the same vertex).

B

The graph is semi-Eulerian (it can be traversed but starts and ends at different vertices).

C

The graph is not Eulerian or semi-Eulerian

Worked Solution

Create a strategy

Find the degree of every vertex.

Apply the idea

Vertex	Degree
A	2
B	3
C	3
D	4
E	2
F	2

The table shows the degree of each vertex.

Since exactly two vertices have an odd degree, the network is semi-Eulerian. Which means it can be traversed but starts and ends at different vertices.

So the correct answer is option B.

b

Which vertex or vertices can the trail start at?

Worked Solution

Create a strategy

Choose one of the two vertices of odd degree.

Apply the idea

In part (a), the vertices of odd degree are B and C.

So the trail can start at either B or C.

c

Sarah has started to traverse through the graph, by moving along the vertices B,\,C,\,D. Which vertices are possible to travel to next along such a trail?

Worked Solution

Create a strategy

Draw the current trail on the graph.

Apply the idea

The diagram shows Sarah's current trail, with edges already traversed as dotted lines.

From D there are edges to B, C, E, and F.

Sarah cannot return to C as that edge has already been used.

If she travels to B then she will complete a circuit and not be able to reach edges DE or EF unless she repeats an edge.

So the vertices that are possible to travel to next are E and F.

d

Write a semi-Eulerian trail for the network that completes Sarah's journey.

Worked Solution

Create a strategy

Write a circuit that passes over all edges only once, starting and ending at different vertices.

Apply the idea

From part (c) we know that the trail starts with B,\,C,\,D, then can go to either E or F.

We can choose to go to E, as shown in the diagram.

Now we move to traverse the remaining solid edges to get the Semi-Eulerian trail: B,\,C,\,D,\,E,\,F,\,D,\,B,\,A,\,C

When we looked at Eulerian graphs, we were focused on using each of the edges just once.

We will now look at Hamiltonian graphs, which are named after Sir William Hamilton - an Irish mathematician, physicist and astronomer.

A Hamiltonian graph is a graph which has a closed path (cycle) that visits each vertex exactly once, ending on the same vertex as it began. This closed path is also called a Hamiltonian cycle.

In the graph, the Hamiltonian cycle is marked in red. As it is a cycle, we cannot have repeated edges or repeated vertices. Note that we do not need to use all the edges in order to visit each vertex once.

Other Hamiltonian cycles here include ABDCA,\, DBACD, and many others.

A semi-Hamiltonian path is a path that visits every vertex once and starts and ends at different vertices. Semi-Hamiltonian graphs are sometimes called traceable.

If a graph has a Hamiltonian cycle then it automatically has a semi-Hamiltonian path (by just dropping off the last vertex in the cycle we create a path - for example, ABDC and DBAC in the graph above).

Unlike Eulerian and semi-Eulerian paths, there is no systematic procedure to help us identify if a semi-Hamiltonian path or Hamiltonian cycle exists. The only thing we can do is look for them.

Here are three networks:

• the first is semi-Hamiltonian and has a semi-Hamiltonian path highlighted;

• the second is Hamiltonian and has a Hamiltonian cycle highlighted;

• the third does not have a Hamiltonian or semi-Hamiltonian path.

The following graph is a complete graph. Recall that means each vertex is connected to every other vertex. It has many semi-Hamiltonian paths and Hamiltonian cycles. Remember, a semi-Hamiltonian path is a path where we visit each of the vertices only once.

Here is the full list of semi-Hamiltonian paths for this graph:

ABCD,\,ABDC,\,ADCB,\,ADBC,\,ACBD,\,ACDB,\,BACD,\,BADC,\,BCDA,\,BCAD,\,BDAC, \\ BDCA,\,CABD,\,CADB,\,CBDA,\,CBAD,\,CDBA,\,CDAB,\,DABC,\,DACB,\,DBAC,\,DBCA, \\ DCAB and DCBA.

So the list of semi-Hamiltonian paths is actually just all combinations of the four vertices A,\,B,\,C and D.

Also, because it is a complete graph all of the paths listed above can be turned into Hamiltonian cycles by returning to the original node.

In a complete graph with n vertices, each vertex is connected to every other vertex by an edge. Starting at any vertex there are n-1 possible choices of vertices to visit next. After that, there are \\ n-2 vertices left to visit, and so on. Since every vertex is connected to every other vertex, this means there are n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1 possible Hamiltonian cycles.

For example, if a complete graph has 4 vertices the number of Hamiltonian cycles is given by:4! = 4 \times 3 \times 2 \times 1 = 24

A graph can be a traversable Eulerian/semi-Eulerian, a Hamiltonian/semi-Hamiltonian network, both, or neither, as these examples demonstrate:

The first is Eulerian and Hamiltonian, the second is only Hamiltonian, the third is only Eulerian, and the fourth is neither.

Examples

Example 4

Which of the following graphs are semi-Hamiltonian?

A

B

C

D

Worked Solution

Create a strategy

Check each graph to see if a semi-Hamiltonian path is possible.

Apply the idea

For option A, we can start with A, \, E, \,D. But to get to B we need to come back through D. So we cannot create a semi-Hamiltonian path.

For option B, a semi-Hamiltonian path is C, \,A, \,D, \,B , \,E. We cannot create a Hamiltonian circuit without repeating some vertices. So the graph is semi-Hamiltonian but not Hamiltonian.

For option C, a Hamiltonian circuit is B, \,A, \,C, \,D, \,E, \,B. So it is a Hamiltonian network.

For option D, a semi-Hamiltonian path is A, \,B, \,C, \,D , \,E. We cannot create a Hamiltonian circuit without repeating some vertices. So the graph is semi-Hamiltonian but not Hamiltonian.

So the correct answers are option B and D.

Watch question walkthrough

Example 5

A rock band is planning a tour across several cities. The following table represents the routes and distance between the cities at which they will be performing.

Starting City	Ending City	Distance
A	C	9
A	F	6
B	E	11
B	F	5
C	D	3
C	F	7
E	D	5
E	F	8

a

Which of the following graphs does the table represent?

A

B

C

D

Worked Solution

Create a strategy

Compare the routes and distances in the table with each of the graphs.

Apply the idea

Looking at the table, starting at A and ending at C, there is a distance of 9. So the edge AC must have a weight of 9. That means that option A cannot be the answer.

In the last row of the table, starting at E and ending at F, there is a distance of 8. The only remaining graph that has the edge EF with weight 8, is option C.

So the correct answer is option C.

Watch question walkthrough

b

Using either the correct graph or table given, find the shortest route for the rock band to cross starting at city A and passing by each city only once.

Worked Solution

Create a strategy

At each vertex, choose the edge that has the lowest weight until all vertices have been visited.

Apply the idea

From A we move to F since 6 \lt 9.

From F we move to B since 5\lt 7 \lt 8.

From B we move to E since it is the only remaining option.

From E we move to D since it is the only remaining option.

From D we move to C since it is the only remaining option.

So the shortest route for the rock band to cross starting at city A and passing by each city only once is: \text{Shortest route} = A,\,F,\,B,\,E,\,D,\,C

Reflect and check

There are other routes with the same total weight. The weight of the above route is 6+5+11+5+3=30.

Another route that has the same total weight, and so would also be the shortest route is: A,\,C,\,D,\,E,\,F,\,B

Watch question walkthrough