Say we have a undirected, connected graph that represents a network of streets. How would you prove that there always exists a tour of the network, where one ``drives'' in both directions on every street exactly once?
Network of streets
-
0Wouldn't the ability to `drive' in one direction and not the other suggest that the graph is directed? – 2010-09-18
2 Answers
This is essentially the same as Isaac’s comment on Moron’s answer, but I’ll post it as an answer.
I assume that by “one ‘drives’ in both directions on every street exactly once,” you mean “one ‘drives’ in each direction on every street exactly once.”
A directed graph has an Eulerian circuit (i.e. a circuit which uses every edge exactly once) if and only if it is strongly connected and each vertex has equal in-degree and out-degree. This fact can be proved in the same way as the well-known fact that an undirected graph has an Eulerian circuit if and only if it is connected and each vertex has even degree. See a textbook on graph theory for a proof.
Back to your question, let G be the connected undirected graph representing the network of streets. You are looking for an Eulerian circuit (or an Eulerian path if you do not require the tour to end at the starting point) in the directed graph G′ obtained by replacing each edge in G by a pair of directed edges in both directions. It is easy to see that the directed graph G′ satisfies the two conditions above, and therefore G′ has an Eulerian circuit.
What you are looking to prove is that the graph is Eulerian, which is true as each vertex has an even degree.
-
0@Isaac: I see. Feel free to edit my answer if you think it is lacking. – 2010-09-18