Q14 Matemática  (IMO Shortlist 2016)

Existem $n\ge 3$ ilhas em uma cidade. Inicialmente, a empresa de ferry oferece algumas rotas entre alguns pares de ilhas, de modo que é impossível dividir as ilhas em dois grupos, de modo que não haja duas ilhas em grupos diferentes conectadas por uma rota de ferry. Após cada ano, a companhia de ferry fechará uma rota de ferry entre duas ilhas $X$ e $Y$. Ao mesmo tempo, para manter o serviço, a empresa abrirá novas rotas de acordo com a seguinte regra: para qualquer ilha que esteja conectada a uma rota de balsa para exatamente uma de $X$ e $Y$, uma nova rota entre esta ilha e a outra de $X$ e $Y$ é adicionada. Suponha que, a qualquer momento, se partimos todas as ilhas em dois grupos não vazios de alguma forma, sabe-se que a companhia de balsas fechará uma determinada rota conectando duas ilhas dos dois grupos após alguns anos. Prove que depois de alguns anos haverá uma ilha que está conectada a todas as outras ilhas por rotas de balsa.