How does a Hamiltonian path differ from a Hamiltonian cycle?

Both require visiting every vertex exactly once. A Hamiltonian cycle has one additional requirement: the final vertex must connect back to the start. That closure condition is what upgrades an open traversal to a cycle.

What is the key difference between Hamiltonian and Eulerian graph questions?

Hamiltonian questions constrain vertex usage, while Eulerian questions constrain edge usage. This means Hamiltonian solutions track whether each vertex appears once, not whether each edge is used once. Choosing the wrong framework leads to invalid reasoning even if the route looks plausible.

Why can a graph be semi-Hamiltonian but not Hamiltonian?

A graph is semi-Hamiltonian when a full vertex-coverage path exists but no route closes into a cycle. The missing ingredient is start-end adjacency after covering all vertices. So coverage alone is not enough for Hamiltonian status.

What error occurs if a vertex is repeated in a claimed Hamiltonian path?

Repeating a vertex breaks the exact-once condition immediately. Even if all other vertices are visited, the route is not Hamiltonian because uniqueness is part of the definition. The fix is to rebuild the sequence with strict vertex tracking.

Why is 'I found a long cycle' not enough to prove a graph is Hamiltonian?

A cycle can still omit one or more vertices. Hamiltonian proof requires that every vertex in the graph appears exactly once in that cycle. Without checking against the full vertex set, the claim is incomplete.

What common mistake happens when classifying semi-Hamiltonian graphs?

Students often stop after finding a path and call the graph Hamiltonian. They must still check whether the path can be closed into a cycle by an edge from last to first vertex. If closure fails, the correct label is semi-Hamiltonian.

What is a Hamiltonian graph?

A Hamiltonian graph is one that contains at least one Hamiltonian cycle. The cycle must pass through every vertex exactly once and return to its start. This definition is existence-based, so only one valid cycle is needed.

What does the notation $|V|$ mean in Hamiltonian reasoning?

$|V|$ is the number of vertices in the graph. In a valid Hamiltonian path or cycle, the route must include exactly $|V|$ distinct vertices. This count check is a fast way to detect omissions or repeats.

How is a semi-Hamiltonian graph defined?

A semi-Hamiltonian graph contains a Hamiltonian path but no Hamiltonian cycle. So full vertex coverage is possible, but closure to the starting vertex is not. This distinction helps classify open-route feasibility separately from closed tours.

Why is constructing an explicit vertex order an effective proof method?

Hamiltonian properties are existential, so one valid construction is enough to establish the claim. A vertex order makes each condition auditable: adjacency, no repeats, and full coverage. This is why explicit routes are preferred in exam proofs.

Hamiltonian Graphs | Pearson Edexcel International A-Level Maths

1. Definition & Core Concepts

Core Terms

Hamiltonian path is a path that visits every vertex exactly once, so the emphasis is complete vertex coverage without repetition. It is stricter than a general path because missing even one vertex fails the condition. Use this concept when the task is to pass through all locations exactly once without necessarily returning.
Hamiltonian cycle is a Hamiltonian path that returns to its starting vertex, creating a closed loop through all vertices exactly once. The return edge is essential, so a graph can have a Hamiltonian path but still fail to be Hamiltonian. This is the defining feature of a Hamiltonian graph.
A graph is semi-Hamiltonian if it has at least one Hamiltonian path but no Hamiltonian cycle. This classification helps distinguish open-route feasibility from closed-tour feasibility. In practice, it captures cases where full coverage is possible but closure is structurally blocked.

A graph with one highlighted Hamiltonian cycle that passes through each vertex exactly once and returns to the start.

2. Underlying Principles

Why the Condition Is Vertex-Based

Hamiltonian reasoning is about vertices, not edges, so the key invariant is whether each vertex appears exactly once in the sequence. This is why dense graphs often help, but density alone does not guarantee a cycle. The closure requirement adds one extra adjacency constraint between the last and first vertices.
A Hamiltonian cycle on $n$ vertices has exactly $n$ edges in the cycle order, even if the graph itself has many more edges. Those extra edges are optional alternatives, not mandatory parts of the Hamiltonian structure. This principle explains why multiple different Hamiltonian cycles can exist in the same graph.

Classification rule: If you can explicitly list a cycle that uses every vertex exactly once and returns to start, the graph is Hamiltonian; if only a full-coverage open path exists, it is semi-Hamiltonian. Constructive evidence is the standard proof approach in elementary graph settings.

3. Methods & Techniques

Construction Workflow

Start by listing all vertices and tracking a candidate order so no vertex repeats, because repetition immediately breaks Hamiltonian validity. Then grow the path by choosing adjacent unused vertices, prioritizing forced moves at low-degree vertices. This reduces branching and avoids dead-end exploration late in the search.
After building a full vertex sequence, test the final condition: for a cycle, verify the last vertex is adjacent to the first; for a path, this closure is not required. This single adjacency check often decides Hamiltonian versus semi-Hamiltonian status. Always separate these two checks to avoid classification errors.
For adjacency-matrix inputs, convert to a quick sketch or adjacency list before searching because visual structure reveals feasible ordering constraints faster. A matrix gives connectivity data, but a sketch exposes bottlenecks and near-complete subgraphs that guide trial construction. Use the matrix afterward to verify each step formally.

4. Key Distinctions

High-Value Comparisons

Feature	Hamiltonian Path	Hamiltonian Cycle
Vertex visit condition	Each vertex exactly once	Each vertex exactly once
Start and end	Different allowed	Must be same vertex
Graph classification impact	Semi-Hamiltonian possible	Hamiltonian graph confirmed

Feature	Hamiltonian Idea	Eulerian Idea
What must be used exactly once	Vertices	Edges
Typical check style	Construct full vertex order	Degree parity conditions often help
Main failure mode	Repeated or missing vertex	Repeated or omitted edge

Decision criterion: use Hamiltonian methods when the task says "visit every vertex/location once," and use Eulerian methods when it says "traverse every edge/road once." The wording points directly to the governing constraint. Misreading this language is a major source of incorrect method choice.

5. Exam Strategy & Tips

Scoring-Oriented Technique

Write the candidate route as an ordered vertex string and tick vertices as they are used, because this creates visible proof of exact-once coverage. Examiners usually award method marks for a logically checkable construction process. A clean sequence is stronger than an unlabeled drawing.
If asked to "show" Hamiltonian status, provide one valid Hamiltonian cycle and state why it satisfies both conditions: complete coverage and return to start. If cycle construction fails but a full path works, explicitly classify as semi-Hamiltonian and justify the missing closure edge. This direct wording protects conclusion marks.
Perform a final audit: count vertices in the graph and compare with vertices listed in your route. In a valid Hamiltonian path/cycle, the route should include each vertex exactly once, so the number of distinct listed vertices must match $|V|$ . This quick check catches omissions before submission.

6. Common Pitfalls & Misconceptions

Frequent Errors

A common mistake is treating any long cycle as Hamiltonian even when one vertex is skipped. Hamiltonian status is all-or-nothing on vertex coverage, so missing one vertex invalidates the claim completely. Always verify against the full vertex set, not just the visible shape.
Students often confuse "no repeated edges" with "no repeated vertices," but Hamiltonian paths restrict repeated vertices specifically. You may avoid repeating edges and still fail Hamiltonian conditions if a vertex appears twice or is omitted. Keep the constraint language precise during checking.
Another error is assuming high vertex degree guarantees Hamiltonian cycles in every case. High connectivity helps search, but structural bottlenecks can still prevent a valid closed tour. Treat degree as a heuristic, not a proof by itself.

Hamiltonian Graphs

Summary

1. Definition & Core Concepts

Core Terms

2. Underlying Principles

Why the Condition Is Vertex-Based

3. Methods & Techniques

4. Key Distinctions

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions

Hamiltonian Graphs

Summary

1. Definition & Core Concepts

Core Terms

2. Underlying Principles

Why the Condition Is Vertex-Based

3. Methods & Techniques

Construction Workflow

4. Key Distinctions

High-Value Comparisons

5. Exam Strategy & Tips

Scoring-Oriented Technique

6. Common Pitfalls & Misconceptions

Frequent Errors

Construction Workflow

High-Value Comparisons

Scoring-Oriented Technique

Frequent Errors