AMC12 2019 B

Answer (E): Label the remaining cities as shown below. Because 3 roads reach cities $B$, $C$, $E$, $H$, $J$, and $K$, at least one of these roads must be excluded from Paula’s route at each of these 6 cities. Furthermore, because the route must begin at $A$ and conclude at $L$, one of the two roads reaching $A$ and one reaching $L$ must be excluded. There are 17 roads and only 4 can be excluded from a 13-road route. Because 8 cities must involve excluded roads and no road can reach more than 2 cities, the 4 excluded roads must each involve 2 of these 8 cities. Because $C$ can be paired only with $B$, and $J$ can be paired only with $K$, $\overline{BC}$ and $\overline{JK}$ must be excluded. For similar reasons, $\overline{AE}$ and $\overline{HL}$ must be the other two excluded roads and Paula’s route must be as shown below. There are exactly 4 routes, depending on the choice of path (clockwise or counterclockwise) around the loops at $F$ and $G$, namely $ABFJIEFGCDHGKL$, $ABFEIJFGHDCGKL$, $ABFJIEFGCDHGKL$, and $ABFEIJFGHDCGKL$.