Q16 Matemática  (Tournament Of Towns 2011)

Em um país, existem cidades de $100$. Alguns pares de cidades são unidos por estradas. As estradas não se cruzam, exceto nas cidades. É possível ir de qualquer cidade a qualquer outra cidade por estrada. Prove que é possível pavimentar algumas das estradas de modo que o número de estradas pavimentadas em cada cidade seja ímpar.