# Spanning subgraph with all degrees odd

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?

• After deleting $A$ and $B$, you are left with a forest. Does each component of that forest have an even number of nodes? If not, how does the induction hypothesis apply? For example, say $n=3$ and you have nodes $A,B,C,D,E,F$ and edges $AB,BC,BD,DE,EF$. – bof Dec 20 '18 at 20:45
• I see your point. Thanks. @bof – Aqua Dec 20 '18 at 20:48
• Hint: Start by selecting a spanning, rooted tree ... – Henning Makholm Dec 20 '18 at 20:53

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.
• It's not even necessary to think about the degree of the nodes for your first solution. Just call the nodes $A_1, B_1, A_2, B_2, \dots, A_{50}, B_{50}$ in an arbitrary order, find an $A_i,B_i$-path for each $i$, and color each edge red if it belongs to an odd number of the paths (that is, take the symmetric difference of the paths). Each path changes the red degree of its endpoints to an odd number, but doesn't change the parity for its internal vertices. – Misha Lavrov Dec 20 '18 at 23:50