Question

Suppose you have a connected network of two-way streets. Show that you can drive along these streets so that you visit all streets and you drive along each side of every street exactly once. Further, show that you can do this such that, at each intersection, you do not leave by the street you first used to enter that intersection unless you have previously left via all other streets from that intersection

Answer 1

What you are looking to prove is that the graph is Eulerian.

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.