Discrete UE Hamiltonian Paths & Circuits Review

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

State whether you can find a Hamiltonian path, circuit or neither.

• Path

• Circuit

• Neither

Find the Hamiltonian Path (ignore direction of arrows)

• 1, 3, 4, 3, 2

• 1, 2, 3, 4

• 2, 3, 4, 3, 1

• There is none