Q2 Matemática  (Romanian Masters of Mathematics Collection 2017)

Um país planar tem um número ímpar de cidades separadas por distâncias distintas aos pares. Algumas dessas cidades estão conectadas por voos diretos de ida e volta. Cada cidade está diretamente conectada a exatamente duas outras cidades, e as últimas estão localizadas mais distantes dela. Prove que, usando esses voos, pode-se ir de qualquer cidade para qualquer outra cidade