3
$\begingroup$

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?

  • 0
    Wouldn't the ability to `drive' in one direction and not the other suggest that the graph is directed?2010-09-18

2 Answers 2

3

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.

3

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

  • 0
    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?2010-09-18
  • 0
    @Isaac: I believe you can always pick the street you came from, though I haven't thought much about it. You might be right.2010-09-18
  • 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.`2010-09-18
  • 0
    @Isaac: I see. Feel free to edit my answer if you think it is lacking.2010-09-18