# 6. Variant 1

Given the road map of the kingdom. The cities are marked with numbers, and the segments represent roads. One day, a traveling knight started his journey from one of the cities in the kingdom and managed to construct his route in such a way that he traveled each road exactly once. In which city, marked with a number, could he have started his journey? List all possible options.

![](https://cdn.mathpix.com/cropped/2024_05_06_1bd5a25c646ad8e2b536g-07.jpg?height=274&width=358&top_left_y=1256&top_left_x=862)
Answer: 2, 5.

Solution: If a city is not the beginning or the end of the knight's journey, then every time he enters through one road, he must exit through another road. This means that the roads from such a city come in "pairs," and there is an even number of them in total. Therefore, cities 2 and 5, from which an odd number of roads lead out, will be the start and end of the journey (in some order), while the other cities cannot be the start or end of the journey. The required paths exist. For example, for 5, the path $5-6-1-2-3-4-5-7-1-8-3-7-8-2$ works, and for 2, the reverse path works.

## Variant 2

Given a map of the kingdom's roads. The cities are marked with numbers, and the segments represent roads. One day, a traveling knight started his journey in one of the cities of the kingdom and managed to construct his route so that he traveled each road exactly once. In which city, marked with which number, could he have started his journey? List all possible options.

![](https://cdn.mathpix.com/cropped/2024_05_06_1bd5a25c646ad8e2b536g-07.jpg?height=314&width=355&top_left_y=2274&top_left_x=885)

Answer: $1,6$.

## Variant 3

Given a map of the kingdom's roads. The cities are marked with numbers, and the segments represent roads. One day, a traveling knight started his journey in one of the cities of the kingdom and managed to construct his route so that he traveled each road exactly once. In which city, marked with which number, could he have started his journey? List all possible options.

![](https://cdn.mathpix.com/cropped/2024_05_06_1bd5a25c646ad8e2b536g-08.jpg?height=353&width=412&top_left_y=512&top_left_x=846)

Answer: $7,8$.

## Variant 4

Given a map of the kingdom's roads. The cities are marked with numbers, and the segments represent roads. One day, a traveling knight started his journey in one of the cities of the kingdom and managed to construct his route so that he traveled each road exactly once. In which city, marked with which number, could he have started his journey? List all possible options.

![](https://cdn.mathpix.com/cropped/2024_05_06_1bd5a25c646ad8e2b536g-08.jpg?height=547&width=379&top_left_y=1247&top_left_x=862)

Answer: 2, 4.

## Variant 5

Given a map of the kingdom's roads. The cities are marked with numbers, and the segments represent roads. One day, a traveling knight started his journey in one of the cities of the kingdom and managed to construct his route so that he traveled each road exactly once. In which city, marked with which number, could he have started his journey? List all possible options.

![](https://cdn.mathpix.com/cropped/2024_05_06_1bd5a25c646ad8e2b536g-08.jpg?height=334&width=545&top_left_y=2175&top_left_x=774)

Answer: $2,6$.