Hamiltonian Paths Basics Quiz

1) A Hamiltonian path in a graph is a path that:

Uses every edge exactly once

Visits every vertex exactly once

Returns to the starting vertex

Has no repeated edges

It must visit each vertex exactly once.

Explanation

It must visit each vertex exactly once.

2) A Hamiltonian cycle is a Hamiltonian path that additionally:

Is the shortest path

Is the longest path

Ends where it started

Has no edges

A Hamiltonian cycle starts and ends at the same vertex.

Explanation

A Hamiltonian cycle starts and ends at the same vertex.

3) Which of the following graphs always has a Hamiltonian path?

A tree with 4 leaves

A path graph

A complete graph

A star graph

Complete graphs contain Hamiltonian paths and cycles.

Explanation

Complete graphs contain Hamiltonian paths and cycles.

4) A graph with a Hamiltonian cycle must be connected.

True

False

A cycle cannot occur in a disconnected graph.

Explanation

A cycle cannot occur in a disconnected graph.

5) Dirac’s theorem gives a sufficient condition for a Hamiltonian cycle.

True

False

Dirac’s theorem ensures Hamiltonicity under degree ≥ n/2.

Explanation

Dirac’s theorem ensures Hamiltonicity under degree ≥ n/2.

6) According to Dirac’s theorem, a graph on n vertices is Hamiltonian if:

Every vertex has degree ≥ n/2

The graph is bipartite

The graph is a tree

The graph is planar

This is Dirac’s condition for Hamiltonian cycles.

Explanation

This is Dirac’s condition for Hamiltonian cycles.

7) Which of the following is true about all Hamiltonian paths?

They must include a cycle

They are longest paths

They include all vertices

They require an Eulerian cycle

Hamiltonian paths visit all vertices.

Explanation

Hamiltonian paths visit all vertices.

8) A graph has 10 vertices, all of degree 1 except one vertex of degree 9. Does it contain a Hamiltonian path?

Yes

No

The high-degree vertex can connect all leaf vertices in sequence.

Explanation

The high-degree vertex can connect all leaf vertices in sequence.

9) Every Hamiltonian cycle is also a Hamiltonian path.

True

False

A Hamiltonian cycle contains a Hamiltonian path within it.

Explanation

A Hamiltonian cycle contains a Hamiltonian path within it.

10) Which graph definitely does not have a Hamiltonian cycle?

C₅

K₄

P₄

K₃,₃

A path graph (P₄) contains no cycles at all.

Explanation

A path graph (P₄) contains no cycles at all.

11) Which graphs contain a Hamiltonian path?

P₅

A tree of 7 vertices

A disconnected graph

K₆

Disconnected graphs cannot have Hamiltonian paths.

Explanation

Disconnected graphs cannot have Hamiltonian paths.

Submit

12) In a Hamiltonian path, vertices:

May repeat

Must not repeat

Must have the same degree

Must form a cycle

Vertices must be visited exactly once.

Explanation

Vertices must be visited exactly once.

13) Which statements are true?

A Hamiltonian cycle implies a Hamiltonian path

A Hamiltonian path implies a Hamiltonian cycle

Some bipartite graphs have Hamiltonian cycles

Trees may have Hamiltonian paths

Paths are more general; cycles require extra conditions.

Explanation

Paths are more general; cycles require extra conditions.

Submit

14) How many Hamiltonian paths does the complete graph Kₙ contain?

N!

(n−1)!

N!/2

N−2

Any permutation of vertices defines a Hamiltonian path.

Explanation

Any permutation of vertices defines a Hamiltonian path.

15) A Hamiltonian path exists in every connected graph.

True

False

Many connected graphs fail to be Hamiltonian.

Explanation

Many connected graphs fail to be Hamiltonian.