Problem:
A tourist arrives in Moscow by train and wanders randomly through the streets on foot. After supper he decides to return to the station along sections of street that he has traversed an odd number of times. Prove that this is always possible. [In other words, given a path over a graph from to , find a path from to consisting of edges that are used an odd number of times in the first path.]
Solution
Solution:
Disregard all edges except those used in the path from to , and for each of those let the multiplicity be the number of times it was traversed. Let the degree of a vertex be the sum of the multiplicities of its edges. The key is to notice that the degree of every vertex except and must be even. For as we traverse the path from to we increase the degree by each time we pass through a vertex. But at the start of the path, as we leave , we only increase its degree by . Similarly as we arrive at for the last time.
Now construct a path from as follows. Since has odd degree it must have an edge of odd multiplicity. Suppose the edge connects to . Follow that edge and reduce its multiplicity by one, so that 's degree and 's degree are each reduced by one. Now has odd degree, so it must have an edge of odd multiplicity. Repeat. Since there are only finitely many edges we must eventually be unable to continue the path. But the only way that can happen is if we reach .