Problem 7.2. On Teachers' Day, grateful students gave several railway tickets to Egor Sergeyevich so that he could travel across Russia.

The tickets were for travel between the following pairs of cities:

- Saint Petersburg and Tver,
- Yaroslavl and Nizhny Novgorod,
- Moscow and Kazan,
- Nizhny Novgorod and Kazan,
- Moscow and Tver,
- Moscow and Nizhny Novgorod.

The tickets were open-dated: with each ticket, one could travel once in any direction between the cities.

Egor Sergeyevich ultimately managed to visit each of the six cities once. In which city could the journey have started? List all possible options.
Answer: Saint Petersburg or Yaroslavl.

![](https://cdn.mathpix.com/cropped/2024_05_06_2fdcf97aa9799d0d4cd6g-19.jpg?height=248&width=1001&top_left_y=1045&top_left_x=226)

Fig. 1: to the solution of problem 7.2

Solution. All available routes are shown in Fig. 1. One road leads out of Saint Petersburg and Yaroslavl, so each of these cities must be the starting or ending point of the route.

Both options are possible. The route Saint Petersburg - Tver - Moscow - Kazan - Nizhny Novgorod - Yaroslavl starts in Saint Petersburg. If you travel this route in reverse, Yaroslavl will be the first city.