Question

The figure below is a map showing $12$ cities and $17$ roads connecting certain pairs of cities. Paula wishes to travel along exactly $13$ of those roads, starting at city $A$ and ending at city $L,$ without traveling along any portion of a road more than once. (Paula is allowed to visit a city more than once.) How many different routes can Paula take?

$0$

$1$

$2$

$3$

$4$

Solution:

A route uses $13$ roads as an open trail from $A$ to $L,$ so on the used roads exactly $A$ and $L$ have odd degree and every other city has even degree.

In the full map the corner cities $A$ and $L$ already have even degree $2,$ and six edge-cities have odd degree $3.$ Removing $4$ roads must flip the parity of $A,$ $L,$ and those six cities, and of no others. This forces the four removed roads to pair up those eight cities in the only possible way, so the set of $13$ used roads is uniquely determined.

Counting the Eulerian trails from $A$ to $L$ on that graph gives exactly $4$ routes.

Thus, E is the correct answer.

2019 AMC 12B Problem 10

Solution:

Problem 10 in Other Years