Question

Consider the graph below representing the map of a city. Create an efficient route through the city. Your path must travel every street. List the vertices in the order that you travel them.

Answer 1

ABCDEADBEC

Explanation:

A path that traverses all streets exactly once is called an Euler path. It is only possible for a graph that has an even number of streets coming together at each vertex, or one that has an odd number of streets at only two vertices.

This map has an odd number of streets at vertices A and C, so those are suitable starting and ending points for the path. I find it convenient to travel the outside ring first, then fill in the inner paths that weren't previously traveled. The list of vertices for one possible path is shown above.