In the country of Bulmenia there are 40 big cities. Each of them is connected with 4 other big cities via paths, and you can get from any city to any other via these paths.
- Show that you can create a trip passing through every path exactly once that ends in the city it starts from.
- Show that you can create one or multiple trips, such that every trip passes through different cities, ends in the city it starts from, and also every city is part of exactly one trip.
Remark: The paths can intersect each other, but you cannot switch from one path to another midway.
Source: IMO 2020
- Let us call a trip that ends in the city it starts from a “loop”. Start from any city and keep traveling without using any path twice. If at some point you can’t continue, stop, creating a loop, and modify your trip as follows. Pick any city you have visited from which there are unused paths going out, and once again start traveling along the unused paths until you can’t continue further. Add the newly formed loop to the original trip and continue this procedure until there are no unused paths left, thus completing a loop passing through every path exactly once. This method works because there is an even number of paths going out from every city and you can get from any city to any other.
- Use the loop from 1. and color every second path on it in black. Then, notice that there are 2 black paths going out from evey city. Therefore, these black paths create one or multiple disjoint loops passing through every city in Bulmenia exactly once.