Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Wouldn't the ability to `drive' in one direction and not the other suggest that the graph is directed? –  Joshua Shane Liberman Sep 18 '10 at 0:55
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

What you are looking to prove is that the graph is Eulerian, which is true as each vertex has an even degree.

share|improve this answer
    
If you have to traverse each street once in each direction, then you aren't simply doubling the edges, but replacing each undirected edge with a pair of edges in opposite directions--does this in fact give you the connected graph where every vertex has even degree? –  Isaac Sep 18 '10 at 1:14
    
@Isaac: I believe you can always pick the street you came from, though I haven't thought much about it. You might be right. –  Aryabhata Sep 18 '10 at 2:31
5  
Looking at the Wikipedia page to which you linked, it appears that the even-degree criteria is for undirected graphs, but that the problem satisfies this one: An Eulerian path exists in a directed graph if and only if the graph's underlying undirected graph is connected, at most one vertex has out degree-in degree=1, at most one vertex has in degree-out degree=1 and every other vertex has equal in degree and out degree. –  Isaac Sep 18 '10 at 3:17
    
@Isaac: I see. Feel free to edit my answer if you think it is lacking. –  Aryabhata Sep 18 '10 at 18:03
add comment

How do you represent the fact that you want to traverse each edge twice? How do you know whether you can trace a graph with a single continuous path?

share|improve this answer
1  
Shouldn't this be a comment rather than an answer? –  Yaser Sulaiman Sep 18 '10 at 0:41
2  
@Yaser, Users are unable to comment until they have acquired 50 reputation. To the original post, assuming that I can take a U-turn when I finish a Eulerian Circuit in one direction would give a Eulerian Circuit in the other. –  Joshua Shane Liberman Sep 18 '10 at 0:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.