Question 94
There are 1000 cities in the country of Euleria, and some pairs of cities are linked by dirt roads. It is possible to get from any city to any other city by traveling along these roads. Prove that the government of Euleria may pave some of the roads so that every city will have an odd number of paved roads leading out of it.