Unique messenger route (graphs)

Visual trapsLevel 3 · Intermediate · ●●●○○

A courier must travel each street exactly once on the following map:
```text
A---B
|\ |

| \ |
C---D---F
\ | /
\ | /
E
```
To avoid ambiguity, the streets (edges) are exactly these 9:

A-B, A-C, B-C, B-D, C-D, C-E, D-E, D-F, E-F.

Is there a route that uses all streets exactly once?
If it exists, it indicates which neighborhood it should start from, which one to end in, and gives a valid route.

Solve this riddle

Hints

Show hints

Bto Ato Cto Bto Discount Cto Eto Discount Fto E.
Reusable idea: in a connected graph, there is an Eulerian path if and only if there are exactly 0 or 2 odd vertices.
Yes, there is an Eulerian route. It must start at B and end at E (or vice versa).

Solution

Show full solution

Back to problem
Answer: Yes, there is an Eulerian route. It must start with B and end with E (or vice versa).
Vertex degrees:

$\deg(A)=2$
$\deg(B)=3$
$\deg(C)=4$
$\deg(D)=4$
$\deg(E)=3$
$\deg(F)=2$

There are only two odd vertices (B and E), so there is an Eulerian path that starts at one and ends at the other.
Valid route:

$$ B\to A\to C\to B\to D\to C\to E\to D\to F\to E. $$

Reusable idea: in a connected graph, there is an Eulerian path if and only if there are exactly 0 or 2 odd vertices.

Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The code with checksum and reverse · Next: The scale and the different ball →