Advanced Hamiltonian Path Theory Quiz

1) A graph is Hamiltonian if it contains:

A path using all edges

A cycle using all vertices once

A path using all vertices

A cycle using all edges

A Hamiltonian graph contains a Hamiltonian cycle.

Explanation

A Hamiltonian graph contains a Hamiltonian cycle.

2) Every Hamiltonian graph must also contain a Hamiltonian path.

True

False

A Hamiltonian cycle always includes a Hamiltonian path.

Explanation

A Hamiltonian cycle always includes a Hamiltonian path.

3) Which degree condition guarantees a Hamiltonian cycle (not just a path)?

Minimum degree ≥ 1

Minimum degree ≥ n/2

Maximum degree ≥ n−1

Average degree ≥ 1

This is Dirac’s theorem for Hamiltonicity.

Explanation

This is Dirac’s theorem for Hamiltonicity.

4) In a bipartite graph with parts of sizes m and n, a Hamiltonian cycle can exist only if:

M = n

M > n

M ≤ n

No such condition exists

Hamiltonian cycles alternate between partite sets, requiring equal sizes.

Explanation

Hamiltonian cycles alternate between partite sets, requiring equal sizes.

5) Which statements are true about Hamiltonian paths?

They visit each vertex once

They may repeat edges

They may repeat vertices

They can exist without forming a cycle

Hamiltonian paths visit all vertices but need not close into a cycle.

Explanation

Hamiltonian paths visit all vertices but need not close into a cycle.

Submit

6) If a graph contains an Eulerian path, it must also contain a Hamiltonian path.

True

False

Eulerian and Hamiltonian properties are unrelated.

Explanation

Eulerian and Hamiltonian properties are unrelated.

7) A complete bipartite graph (K_{m,n}) has a Hamiltonian path if and only if:

|m - n| ≤ 1

M = n

Both m and n are even

M + n is prime

Hamiltonian paths must alternate between partite sets.

Explanation

Hamiltonian paths must alternate between partite sets.

8) How many Hamiltonian cycles does (K_n) have?

N!

((n-1)!/2)

((n-2)!)

(2^{n-1})

Fix a start, arrange the others, divide by 2 for reverse direction.

Explanation

Fix a start, arrange the others, divide by 2 for reverse direction.

9) A Hamiltonian path in a tournament always exists.

True

False

Every tournament has a directed Hamiltonian path.

Explanation

Every tournament has a directed Hamiltonian path.

10) Ore’s theorem gives a sufficient condition for Hamiltonicity based on vertex degrees.

True

False

Ore’s theorem: deg(u)+deg(v) ≥ n for nonadjacent u,v.

Explanation

Ore’s theorem: deg(u)+deg(v) ≥ n for nonadjacent u,v.

11) Which graph property guarantees a Hamiltonian path but not a cycle?

Being a tree

Being a complete graph

Being regular of degree ≥ 2

Being Hamiltonian

Trees often have Hamiltonian paths but never cycles.

Explanation

Trees often have Hamiltonian paths but never cycles.

12) Which are sufficient Hamiltonicity conditions?

Dirac’s theorem

Ore’s theorem

Connected with at least 3 vertices

Maximum degree ≥ 1

Dirac and Ore give classical conditions; the others do not.

Explanation

Dirac and Ore give classical conditions; the others do not.

Submit

13) Which is true about Hamiltonian paths in planar graphs?

All planar graphs have them

They never have them

Some planar graphs do; some do not

Only bipartite planar graphs have them

Planarity doesn’t imply Hamiltonicity.

Explanation

Planarity doesn’t imply Hamiltonicity.

14) Every 2-connected graph contains a Hamiltonian path.

True

False

Without articulation points, a full-vertex path can be formed.

Explanation

Without articulation points, a full-vertex path can be formed.

15) A graph has 12 vertices, all with degree ≥ 6. Must it contain a Hamiltonian cycle?

Yes (Dirac’s theorem)

No

Minimum degree ≥ 6 = n/2 satisfies Dirac’s condition → Hamiltonian.

Explanation

Minimum degree ≥ 6 = n/2 satisfies Dirac’s condition → Hamiltonian.