Hamiltonian Graphs

Question 1

When is a path in a graph Hamiltonian?

Answer 1

When it passes through each vertex exactly once.

Question 2

When is a cycle in a graph Hamiltonian?

Answer 2

When it passes though every vertex exactly once.

Question 3

When is a graph Hamiltonian?

Answer 3

If it contains a Hamiltonian cycle

Question 4

If u and w are non-adjacent vertices in an n-vertex graph G and deg(u) + deg(w) \geq n, and G+uw is Hamiltonian then ___ ___ ___

Answer 4

G is Hamiltonian

Question 5

Every graph with n \geq 3 vertices and minimum degree at least ___ is Hamiltonian

Answer 5

n/2