7.4 Hamiltonian Paths and Circuits

A Hamiltonian cycle is

• A cycle that includes every vertex

• A cycle that includes every vertex more than once

• A cycle that includes every edge

• A cycle that includes every edge more than once

A graph in which every vertex is directly connected by a single edge to each of the other vertices

• Tree

• Hamiltonian cycle

• Isomorphic graph

• Complete graph

A Euler's or Hamiltonian Circuit end and start in the same place. 

• True
• False

In a Hamiltonian Path or Circuit, you must use each edge. 

• True 
• False

In a Hamiltonian Circuit or Path, you can only use each vertex once. 

• True
• False

Does this graph have a Hamiltonian Circuit?

• True
• False

In a Hamiltonian Path, you must

• Travel every edge once and only once, returning to where you started

• Travel to every vertex once and only once, returning to where you started

• Travel every edge once and only once, not returning to where you started

• Travel to every vertex once and only once, not returning to where you started

A Hamiltonian Path Exists on this graph

• Yes

• No

Select a Hamiltonian path:

• acfgebad

• dacfgeb

• acfdeb

• abegfc

In the following graph, decide which of the following is true: (could be more than one)

• You can find a Hamiltonian Circuit if you travel 6, 4, 5, 1, 2, 3, 4, 6

• You can find a Euler Path if you travel 1, 5, 2, 3, 4, 6

• You cannot find a Hamiltonian Path

• You cannot find a Euler Path