Spanning subgraph with all degrees odd

Question

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?

Answer 1

The number of odd-degree nodes is even. Since the total number of nodes is even, the number of even-degree nodes is even. Let $A_1,B_1,A_2,B_2,\dots,A_m,B_m$ be the even-degree nodes. Since the graph is connected, for each $i\in\{1,2,\dots,m\}$ we can choose a path $P_i$ from $A_i$ to $B_i$. Color an edge red if it belongs to an even number of the paths $P_i$. Then each node is incident with an odd number of red edges.

Alternatively: First, replace the graph with a spanning tree. Then, color an edge red if there are an even number of nodes on either side of it. Assuming that the number of nodes is even, each node is incident with an odd number of red edges.

Answer 2

Assume without loss of generality that the road network is a tree. (You can always achieve this by ignoring some of the roads).

Now start deciding whether each road in the tree are paved or not, by taking those roads that are farthest from the capital first. At each step there is exactly one way to keep the goal satisfied for the town at the country end of the road you're looking at. At the end the only town you haven't given an odd number of paved roads by construction is the capital, but it's not possible to have 99 towns with odd numbers of paved roads and a single town with an even number, so the capital automatically satisfies the rule.