7-2 Hamitonian Circuits and Cycles

True or false: With Hamilton circuits, every edge must be used. With Euler circuits, every vertex must be used.

• True
• False

Hamilton touches

• all edges
• all vertices

How do you determine if a graph has a Hamilton Circuit?

• There is a simple algorithm that can be applied directly.

• There is no way to guarantee the existence

• You can always find a Hamilton Circuit by trial and error.

• Graphs with an even number of vertices always have a Hamilton Circuit.

The graph shown contains NO cycles.

• True

• False

The graph shown contains NO cycles.

• True

• False

A cycle is...

• A path that starts and ends at different vertices.

• A path that starts and ends at the same vertex where backtracking is allowed.

• A path that starts and ends at the same vertex and uses every edge exactly once.

• A path that starts and ends at the same vertex and does not use any edge more than once.

Which of the following paths would create a cycle? There can be more than one answer.

• ABCA

• ACD

• ABCD

• ABCDA

Does the graph have a Hamiltonian Path?

• YES

• NO

Does the graph have a Hamiltonian Path?

• YES

• NO

Is there a cycle in this graph?

• No
• Yes