Eulerian and Hamiltonian Walks Revision Notes for HSC SSCE Mathematics Standard

Eulerian and Hamiltonian Walks

Introduction to graph walks

When working with network graphs, we often need to find paths that follow specific rules. Two important types of walks are Eulerian walks (which focus on edges) and Hamiltonian walks (which focus on vertices). Understanding these concepts helps solve practical problems like planning delivery routes or designing communication networks.

infoNote

The distinction between these two types of walks is fundamental: Eulerian walks are all about traversing edges, while Hamiltonian walks are about visiting vertices. This difference affects everything from how we identify them to their real-world applications.

Eulerian trails and circuits

What are Eulerian walks?

Eulerian walks are special paths through a graph that travel along every edge exactly once. They're named after the Swiss mathematician Leonhard Euler, who first studied these patterns.

There are two types of Eulerian walks:

Eulerian trail: A path that travels along every edge of a graph exactly once, starting at one vertex and finishing at a different vertex.

Eulerian circuit: A path that travels along every edge of a graph exactly once, starting and finishing at the same vertex.

Real-world applications

Eulerian walks have many practical uses. For instance, consider a graph where vertices represent towns and edges represent roads. Finding an Eulerian trail or circuit means discovering a route that travels down every road exactly once - perfect for mail delivery services, rubbish collection, or street cleaning.

A graph that contains an Eulerian trail is called a traversable graph.

How to identify Eulerian walks

The beauty of Eulerian walks is that we can determine whether they exist by checking the degrees of vertices (remember: the degree of a vertex is the number of edges connected to it).

chatImportant

Rules for Identifying Eulerian Walks:

For an Eulerian trail to exist:

The graph must be connected
Exactly two vertices must have an odd degree
These two odd-degree vertices become the start and end points of the trail

For an Eulerian circuit to exist:

The graph must be connected
Every vertex must have an even degree

Worked example: Identifying Eulerian walks

Let's examine three different graphs to determine whether they contain Eulerian trails, Eulerian circuits, or neither.

lightbulbExample

Worked Example: Identifying Eulerian Walks in Three Graphs

Graph (a) - Eulerian circuit:

Looking at this graph, we notice that all vertices have an even degree (specifically, degree $2$ ).

Since every vertex has an even degree, this graph contains an Eulerian circuit. We can start at any vertex, travel through every edge once, and return to our starting point.

Graph (b) - Eulerian trail:

In this graph, exactly two vertices have an odd degree (degree $3$ ), while the remaining vertices have an even degree (degree $2$ ).

Because there are exactly two odd-degree vertices, this graph contains an Eulerian trail. The trail must start at one of the odd-degree vertices and finish at the other.

Graph (c) - Neither:

This graph has four vertices with odd degree and one vertex with even degree.

Since there are more than two odd-degree vertices, this graph contains neither an Eulerian trail nor an Eulerian circuit.

infoNote

Exam Tip:

When determining if a graph has an Eulerian walk, always:

Count the degree of each vertex
Identify how many vertices have odd degrees
Apply the rules: zero odd vertices = circuit; exactly two odd vertices = trail; any other number = neither

Hamiltonian paths and cycles

What are Hamiltonian walks?

While Eulerian walks focus on edges, Hamiltonian walks focus on vertices. These walks are named after Irish mathematician Sir William Hamilton.

Hamiltonian path	Hamiltonian cycle
A path that passes through every vertex of a graph once and only once	A Hamiltonian path that starts and finishes at the same vertex

An important difference: a Hamiltonian path may or may not use all the edges of the graph - it only needs to visit all the vertices.

Real-world applications

Hamiltonian walks are useful when we need to visit every location exactly once, but the route taken between locations doesn't matter.

infoNote

For example, imagine vertices represent people in a network and edges represent email connections. A Hamiltonian path ensures every person receives a message exactly once, regardless of which specific connection path the message follows.

How to identify Hamiltonian walks

Unlike Eulerian walks, Hamiltonian paths and cycles don't have a simple rule based on vertex degrees. The only way to identify them is through careful inspection of the graph. This makes finding Hamiltonian walks more challenging!

chatImportant

Critical Difference from Eulerian Walks:

There is no simple formula or rule to determine if a Hamiltonian path or cycle exists in a graph. You must examine the graph carefully and try different routes. This is a fundamental difference from Eulerian walks, which can be identified quickly using vertex degree rules.

Worked example: Finding Hamiltonian walks

Consider the following network graphs:

lightbulbExample

Worked Example: Finding Hamiltonian Walks in a Network Graph

Part (a): Finding a Hamiltonian path from A to D

A Hamiltonian path must visit every vertex exactly once, but doesn't need to use every edge.

One solution: $A - F - G - B - C - H - E - D$

This path visits all eight vertices ( $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , $G$ , $H$ ) exactly once, starting at $A$ and finishing at $D$ .

Note: This solution isn't unique! Another valid path would be $A - F - E - H - G - B - C - D$ .

Part (b): Finding a Hamiltonian cycle starting at A

A Hamiltonian cycle must visit every vertex exactly once and return to the starting vertex.

One solution: $A - B - C - D - E - F - A$

This cycle visits all vertices once and returns to vertex $A$ .

Again, multiple solutions exist. For instance, $A - F - E - D - C - B - A$ is also valid.

infoNote

Exam Tip:

For Hamiltonian paths and cycles:

There's no shortcut rule - you must inspect the graph carefully
Multiple correct answers often exist
Check your answer by counting vertices: you should visit each vertex exactly once
For cycles, make sure you return to the starting vertex

Key differences between Eulerian and Hamiltonian walks

Understanding the fundamental differences helps avoid confusion:

chatImportant

Key Differences Between Eulerian and Hamiltonian Walks:

Eulerian walks:

Focus on edges - every edge must be used exactly once
Vertices may be visited more than once
Can be identified using vertex degree rules
Existence can be determined quickly

Hamiltonian walks:

Focus on vertices - every vertex must be visited exactly once
Edges may or may not all be used
No simple rule for identification
Must be found through inspection

bookmarkSummary

Key Points to Remember:

Eulerian trails use every edge once, starting and ending at different vertices. They exist when a connected graph has exactly two odd-degree vertices.
Eulerian circuits use every edge once, starting and ending at the same vertex. They exist when all vertices have even degree.
Hamiltonian paths visit every vertex once. They don't have a simple existence rule and must be found by inspection.
Hamiltonian cycles visit every vertex once and return to the start vertex. Like paths, they must be found by inspection.
Think "E for Edge" (Eulerian) and "H for Hit every vertex" (Hamiltonian) to remember the key difference between these two types of walks.

Eulerian and Hamiltonian Walks (HSC SSCE Mathematics Standard): Revision Notes