In a country, there are 100 towns. Some pairs of towns are joined by roads. The roads do not intersect one another except meeting at towns. It is possible to go from any town to any other town by road. Prove that it is possible to pave some of the roads so that the number of paved roads at each town is odd.
Clearly we have here a connected simple graph with no loops and with $100$ nodes. Say we have $2n$ nodes instead of $100$ nodes and prove the statement with induction. It is enough to observe only (spanned) trees.
Clearly this work if $n=1$. Both nodes have a degree $1$ (since it is connected).
Suppose the statement is true for all $k\leq n$ and we prove the statement for $n+1$.
So we have a node $A$ with degree $1$ and let $B$ be it neighbour. Color this edge $AB$ red and delete all other edges from $B$ and observe the rest of the graph (without $A$ and $B$ also). This graph is a forest so in each component we can color edges red so that each node has odd red edges (by induction hypothetis). So we are done, just pave all red edges.
Edit: As bof mentioned in comment this is not correct. Any Idea how to solve it?
Edit: Is this doable by probabilistic method?