The edges in a certain graph represent roads, and the vertices represent intersections. We want to time the traffic signals at each intersection and not visit any intersection twice. Should we look for an Euler circuit or a Hamilton circuit?
A)Euler
B)Hamilton
C)either
D)neither

Question

Quizplus · Accepted Answer

A Hamilton circuit visits every vertex exactly once, which is what we want to do when timing the traffic signals at each intersection without revisiting any intersection. On the other hand, an Euler circuit visits every edge exactly once which does not necessarily guarantee that we can visit every intersection exactly once without backtracking. Therefore, we should look for a Hamilton circuit.

The Edges in a Certain Graph Represent Roads, and the Vertices