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

2 Answers

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.

• 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

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.