2. Between Moscow and Saint Petersburg, there are seven settlements: Yaroslavl, Tver, Klin, Vyshny Volochek, Shestihino, Zavidovo, and Bologoye. It is known that Moscow is connected by direct railway communication with seven points, Saint Petersburg with five, Tver with four, Yaroslavl with two, Bologoye with two, Shestihino with two, and Zavidovo with one. How many settlements is Vyshny Volochek connected to by direct communication? How many ways are there to travel from Moscow to Saint Petersburg?
Solution: Let's build a graphical interpretation of the problem. The sum of the degrees of the vertices of the graph must be even. Let the degree of the vertex BB be x, and Klin be y. Then the degrees of the vertices of the railway graph are $7,5,4,2,2,2,1, x, y$. The sum of all vertices $7+5+4+2+2+2+1+x+y=23+x+y$. Since this sum must be even, therefore $\mathrm{x}+\mathrm{y}=$ odd. Note that Klin and Vyshny Volochek are generally equally significant by the condition, which means that any pair of numbers that can be for Klin $=\mathrm{a}, \mathrm{BB}=\mathrm{b}$, can also be replaced by Klin $=\mathrm{b}, \mathrm{BB}=\mathrm{a}(*) . \quad$ Let's build some road scheme and consider what options can be derived from it: since Moscow is connected to 7 points, it means that it has direct railway communication with all cities except St. Petersburg (since by condition the cities are located between Moscow and St. Petersburg, therefore, on the way we will definitely encounter one of the settlements). Then Zavidovo is no longer connected by road to any. Remove Moscow and Zavidovo from consideration, then the degrees of all vertices will decrease by one. The new sequence of vertices: 5,3,1,1,1, x-1, y-1. Consider St. Petersburg (which has 5 roads), that is, it is connected to all cities except Moscow, Zavidovo, and one more city.

Case 1. Let this city $\mathrm{X}$ have a vertex degree of 1 (that is, it is either Yaroslavl, or Shestihino, or Bologoye), then St. Petersburg is connected to the other five cities, and at least two cities have degrees of 1. Remove St. Petersburg. Then the new degrees of the vertices are: Tver (2), Klin (y-1), Vyshny Volochek (x-1), and $\mathrm{X}(1)$. Then Tver is connected to some pair of cities: X-Vyshny Volochek, Klin-Vyshny Volochek, X-Klin. (see Fig.1)

![](https://cdn.mathpix.com/cropped/2024_05_06_10143262d92027b500e2g-04.jpg?height=214&width=460&top_left_y=767&top_left_x=455)

Vyshny Volochek ( $(x-2)$

![](https://cdn.mathpix.com/cropped/2024_05_06_10143262d92027b500e2g-04.jpg?height=225&width=446&top_left_y=1138&top_left_x=471)

![](https://cdn.mathpix.com/cropped/2024_05_06_10143262d92027b500e2g-04.jpg?height=228&width=445&top_left_y=771&top_left_x=994)

![](https://cdn.mathpix.com/cropped/2024_05_06_10143262d92027b500e2g-04.jpg?height=223&width=442&top_left_y=1139&top_left_x=1001)

Then the degree of Vyshny Volochek is either 2, or 3, or 4. Considering that there may be a connection Klin-Vyshny Volochek, the degree of one of the cities may increase by 1, that is, the final degree of Vyshny Volochek = $2,3,4$ or 5

Case 2. Let St. Petersburg not be connected to Tver. Then, removing St. Petersburg, we get that Tver's degree remains 4, but there is nothing to connect it to, as only two cities remain (Klin and Vyshny Volochek), so the situation is impossible.

Case 3. Let St. Petersburg not be connected to either Klin or Vyshny Volochek (according to (*)). Then Tver is connected to Klin and Vyshny Volochek. Therefore, the degree of Vyshny Volochek is either 4, or 3, or 2. (example in Fig.2)

![](https://cdn.mathpix.com/cropped/2024_05_06_10143262d92027b500e2g-04.jpg?height=280&width=562&top_left_y=2099&top_left_x=450)

## Calculate the number of travel options from Moscow to St. Petersburg

Case 1. If $\mathrm{X}$ is either Yaroslavl, or Shestihino, or Bologoye, then in each case there are 9 options. Considering the possibility of connecting Klin-Vyshny Volochek, there are 15 options.

Case 2. If $\mathrm{X}$ is either Klin or Vyshny Volochek, then there are 9 or 10 options (depending on whether Klin-Vyshny Volochek is connected or not).

Fig.3 illustrates all roads if $\mathrm{X}$ is Yaroslavl

![](https://cdn.mathpix.com/cropped/2024_05_06_10143262d92027b500e2g-05.jpg?height=440&width=580&top_left_y=408&top_left_x=544)

Fig.3.

Answer: Vyshny Volochek can be connected to 2, 3, 4, or 5 points. The number of ways to travel is 9 or 10 or 15.

| Criteria for evaluating the task | Points |
| :--- | :---: |
| The correct answer is obtained and justified | 10 |
| The correct answer is obtained, but the case where Klin and Vyshny Volochek are connected by a separate road is not considered | 9 |
| The answer is not entirely correct, and the set of solutions separately includes the case of a direct connection between Moscow and St. Petersburg | 8 |
| The correct answer is obtained, but the solution is either not fully justified or contains an arithmetic error that does not affect the result | 5 |
| Partial cases of the road scheme are obtained, but not all | 2 |
| The answer is either incorrect or guessed, with no justification | 0 |