Q4 Matemática  (Tournament Of Towns 1982)

Em um determinado país existem mais de $101$ cidades. A capital deste país está conectada por rotas aéreas diretas com cidades de $100$, e cada cidade, exceto a capital, está conectada por rotas aéreas diretas com cidades de $10$ (se $A$ está conectada com $B,B$ está conectada com $A$). Sabe-se que de qualquer cidade é possível viajar de avião para qualquer outra cidade (possivelmente por outras cidades). Provar que é possível fechar metade das rotas aéreas ligadas à capital e preservar a capacidade de viajar de qualquer cidade para qualquer outra cidade do país. (IS Rubanov)