Hamilton Paths and Hamilton Circuits: Videos & Practice Problems
Hamilton Paths and Hamilton circuits are routes through a graph that focus on visiting vertices. A Hamilton path visits each vertex exactly once. A Hamilton circuit also visits each vertex exactly once, but it returns to the starting vertex, so the only repeated vertex is the first and last one. If a sequence repeats a vertex anywhere else, it is neither a Hamilton path nor a Hamilton circuit.
In complete graphs, every pair of vertices is connected by an edge, so Hamilton circuits must exist. The number of unique Hamilton circuits is given by \(\frac{(n-1)!}{2}\). Some settings instead use \((n-1)!\) if opposite directions are counted as different circuits. For weighted graphs, the total weight of a path or circuit is found by adding the weights of its edges.
Hamilton Paths and Hamilton Circuits
Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.
H.P.
H.C.
NEITHER
Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.
H.P.
H.C.
NEITHER
Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.
H.P.
H.C.
NEITHER
Hamilton Paths and Hamilton Circuits Example 1
Hamilton Paths and Hamilton Circuits Example 2
Number of Hamilton Circuits in a Complete Graph
Determine if the graph must have Hamilton circuits. If so, how many?
Note: We will be using the formula below.
Complete? ☐
# of vertices: ___
# of Hamilton circuits: ___
Complete? Yes; # of vertices: 60; # of Hamilton circuits: 6
Complete? No; # of vertices: 60; # of Hamilton circuits: 6
Complete? Yes; # of vertices: 6; # of Hamilton circuits: 120
Complete? Yes; # of vertices: 6; # of Hamilton circuits: 60
How many Hamilton circuits exist in a complete graph with the given number of vertices, ?
Note: We will be using the formula below.
1
3
2
6
How many Hamilton circuits exist in a complete graph with the given number of vertices, ?
Note: We will be using the formula below.
Number of Hamilton Circuits in a Complete Graph Example 3
Weighted Graphs
The weights on the graph below represent distances (in miles). Find the total distance (weight) of each path or circuit.
Home, Grocery Store, Post Office, Bank
17 mi
20 mi
18 mi
13 mi
The weights on the graph below represent distances (in miles). Find the total distance (weight) of each path or circuit.
Home, Grocery Store, Post Office, Bank, Home
22 mi
23 mi
25 mi
27 mi
Weighted Graphs Example 4
Weighted Graphs Example 5
Brute Force Method
Brute Force Method Example 6
Brute Force Method Example 7
Here's what students ask on this topic:
A Hamilton path in a graph is a route that visits each vertex exactly once without repeating any vertex. In contrast, a Hamilton circuit (or Hamiltonian cycle) also visits each vertex exactly once but returns to the starting vertex, making the first and last vertex the same. This means a Hamilton circuit is a closed loop, while a Hamilton path is not necessarily closed. If any vertex is repeated other than the first and last in a circuit, the sequence is neither a Hamilton path nor a Hamilton circuit. Understanding these concepts is fundamental in graph theory and has applications in optimization problems like the traveling salesman problem.
In a complete graph where every pair of vertices is connected by an edge, Hamilton circuits always exist. The number of unique Hamilton circuits is given by the formula . This formula accounts for the fact that circuits that are the same but traveled in opposite directions are considered identical. However, in some contexts, opposite directions are counted as different circuits, and the number of Hamilton circuits is then . This distinction is important when analyzing the symmetry of routes in problems like routing and scheduling.
In a weighted graph, each edge has an associated weight, often representing cost, distance, or time. To calculate the total weight of a Hamilton path or circuit, you sum the weights of all edges included in the path or circuit. Mathematically, if the path includes edges with weights , then the total weight is . This total weight is crucial in optimization problems where the goal is to find the Hamilton circuit or path with the minimum total weight, such as in the traveling salesman problem.
In a complete graph, every pair of distinct vertices is connected by an edge. This high level of connectivity guarantees that it is always possible to find a route that visits each vertex exactly once and returns to the starting vertex, forming a Hamilton circuit. The completeness ensures no vertex is isolated or unreachable, which is a necessary condition for the existence of Hamilton circuits. This property makes complete graphs a fundamental example in studying Hamiltonian cycles and related combinatorial problems.
A sequence of vertices is disqualified from being a Hamilton path or circuit if it repeats any vertex more than allowed. For a Hamilton path, each vertex must be visited exactly once with no repetitions. For a Hamilton circuit, each vertex must be visited exactly once except the starting vertex, which is repeated at the end to complete the circuit. If any vertex appears more than once in the middle of the sequence, the sequence is neither a Hamilton path nor a Hamilton circuit. This strict condition ensures the uniqueness of vertex visits, which is essential for many graph traversal and optimization problems.
