Question

If any of the graphs below have a Hamiltonian circuit, list the vertices of the complete circuit. There may be many possibilities. For full credit, just list one for each graph, if the circuit exists

Answer 1

9514 1404 393

Answer:

1. ABHGEFDCA
2. does not exist
3. ECBADFE

Step-by-step explanation:

A Hamiltonian circuit visits each node once and returns to its start. There is no simple way to determine if such a circuit exists.

__

For graph 2, if there were a circuit, paths ACB, ADB, and AEB would all have to be on it. Inclusion of all of those requires visiting nodes A and B more than once, so the circuit cannot exist.

__

For graph 3, the circuit must include paths BAD and DFE. That only leaves node C, which can be reached from both nodes B and E, so path ECB completes the circuit.