2019 AMC 12B Problem 10

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

Answer: E

Concepts:graph theory parity casework

Difficulty rating: 1640

Small hint:

Using

13

of the

17

roads leaves exactly

4

roads unused

Big hint:

A trail exists only if just

A

and

L

have odd degree; this forces which

4

roads to drop

Solution:

Name the four cities in the top row

A,B,C,D,

those in the middle row

E,F,G,H,

and those in the bottom row

I,J,K,L.

A route using

13

roads is an open Euler trail, so in the used graph exactly

A

and

L

have odd degree.

In the full map, the vertices whose degree parity must change are

A,B,C,E,H,J,K,L.

Because only

4

roads are removed, those roads must pair these

8

vertices. Among them,

E

is adjacent only to

A,

forcing

AE

to be removed; then

BC

is forced. Similarly

H

is adjacent only to

L,

forcing

HL,

and then

JK.

The remaining graph is a chain

\begin{gathered} A-B-F,\\ F-E-I-J-F,\\ F-G,\\ G-C-D-H-G,\\ G-K-L. \end{gathered}

Each of the two

4

-cycles can be traversed in either direction, and everything else is forced. Hence there are

2\cdot2=4

routes.

Thus, E is the correct answer.