n national roads in Republic of Unistan
Source: 2013 Portugal MO p3
October 9, 2020
combinatorics
Problem Statement
In the Republic of Unistan there are national roads, each of them links two cities exactly. You can travel from one city to another of your choice using a sequence of roads. The President of Unistan ordered to label the national roads with the integers from to by an old law: if a city is adjacent to more than one road, the greatest common divisor of the numbers of that roads must be one. Show that you can label the national roads without breaking the law.