Hamiltonian Paths and Circuits

Definition

A Hamiltonian path in a graph is a path that passes through every vertex of the graph exactly once.

A Hamiltonian circuit or Hamiltonian cycle is a cycle that passes through every vertex of the graph exactly once and ends at the starting vertex.

If a graph contains a Hamiltonian circuit, it is called a Hamiltonian graph.

Example of a Hamiltonian circuit in a simple graph with vertices $A, B, C, D$ :

A → B → C → D → A

This sequence visits each vertex once and returns to the start, so it is a Hamiltonian circuit.

Main Content

1. First Concept: Hamiltonian Path

A Hamiltonian path is a route through a graph that includes every vertex exactly one time, with no repeats of vertices.
The path does not need to return to the starting vertex, so its endpoints may be different.

A simple example is a graph with vertices arranged in a line:

A — B — C — D

Here, the path A → B → C → D is a Hamiltonian path because all vertices are visited once.

More examples can be seen in graphs where vertices are connected in a chain-like or suitably linked structure. A graph may have many Hamiltonian paths, one Hamiltonian path, or none at all. The existence of such a path depends on the graph’s connectivity and structure.

Important observations:

A Hamiltonian path uses all vertices, not all edges.
A graph may have a Hamiltonian path even if it does not have a Hamiltonian circuit.
The path must be simple, meaning no vertex repetition is allowed.

2. Second Concept: Hamiltonian Circuit

A Hamiltonian circuit is a closed loop that visits every vertex exactly once and returns to the starting point.
It is stronger than a Hamiltonian path because it requires both complete vertex coverage and a return edge to form a cycle.

Example:

A → B → C → D → A

This is a Hamiltonian circuit if each of the vertices $A, B, C, D$ appears exactly once before returning to $A$ .

A graph with a Hamiltonian circuit is called Hamiltonian. Such graphs are often studied in problems where a round trip is required, such as traveling through cities and coming back to the origin.

Important observations:

Every Hamiltonian circuit contains a Hamiltonian path, but not every Hamiltonian path can be extended into a circuit.
A Hamiltonian circuit always has at least as many edges as vertices.
The cycle must include all vertices exactly once, so any repeated vertex breaks the condition.

A visual example for a 4-vertex cycle:

A — B | | D — C

Possible Hamiltonian circuit: A → B → C → D → A

3. Third Concept: Conditions, Properties, and Differences from Eulerian Concepts

Hamiltonian problems are about visiting every vertex exactly once, whereas Eulerian problems are about traversing every edge exactly once.
This distinction is crucial because a graph can be Eulerian without being Hamiltonian, and vice versa.

Comparison:

Hamiltonian path

uses all vertices exactly once.

Hamiltonian circuit

uses all vertices exactly once and returns to start.

Eulerian path

uses all edges exactly once.

Eulerian circuit

uses all edges exactly once and returns to start.

Useful properties and sufficient conditions:

A complete graph $K_n$ with $n \ge 3$ is Hamiltonian because every vertex is connected to every other vertex.
A cycle graph $C_n$ is Hamiltonian, since the whole graph itself is a Hamiltonian circuit.
Certain degree conditions can help determine Hamiltonicity. For example, if every vertex in a simple graph with $n \ge 3$ has degree at least $n/2$ , then the graph is Hamiltonian (Dirac’s theorem).
Another result, Ore’s theorem, gives a useful sufficient condition based on the sum of degrees of non-adjacent vertices.

These conditions are sufficient, not necessary. That means a graph may still be Hamiltonian even if it does not satisfy them.

Working / Process

1. Identify the vertices and edges of the graph

List all vertices clearly.
Understand which vertices are connected by edges.
Check whether the graph is connected, because a disconnected graph cannot have a Hamiltonian path or circuit.

2. Try to construct a path or cycle that visits each vertex once

Start from a vertex and attempt to move through unvisited adjacent vertices.
Avoid revisiting any vertex.
For a Hamiltonian circuit, make sure the final vertex connects back to the starting vertex.

3. Verify the result

Confirm that every vertex appears exactly once.
For a path, ensure there is no repeated vertex and no need to return to the start.
For a circuit, ensure the path is closed and includes all vertices exactly once.

Example workflow on a graph with vertices $A, B, C, D$ forming a square:

Try A → B → C → D
Check if all vertices are included once: yes
If there is an edge D → A, then A → B → C → D → A is a Hamiltonian circuit

For larger graphs, systematic methods such as backtracking, search algorithms, or applying sufficient conditions are often used because manual checking becomes difficult.

Advantages / Applications

Route planning and transportation

Hamiltonian circuits model problems where each location must be visited once, such as delivery routes and the Traveling Salesman Problem.

Computer science and algorithms

They are important in complexity theory and help illustrate NP-complete problems.

Network design and scheduling

Hamiltonian paths can represent efficient sequences for tasks, machine operations, or communication links.

Additional applications include:

Robotics path planning
Genetic sequencing and bioinformatics
Puzzle solving and recreational mathematics
Designing circuits and control systems where sequential visitation matters

Summary

Hamiltonian paths visit every vertex exactly once.
Hamiltonian circuits visit every vertex exactly once and return to the start.
These concepts focus on vertices, not edges.

Important terms to remember

Hamiltonian path
Hamiltonian circuit
Hamiltonian graph
Vertex
Cycle
Simple graph
Dirac’s theorem
Ore’s theorem