Is there an Euler path solution?

Question

I am solving the following problem: A city is composed of three parallel east-west streets and four parallel north-south streets: Note there are 12 intersections and 17 street segments. A policeman needs to visit every street segment, but he wants to take the shortest path. The policeman can start at any intersection, and he can only traverse streets, going from one intersection to another. How many street segments are there in the shortest path that visits each street segment at least once?

I know that it cannot be an Euler circuit, however I am unsure if it can be an Euler path. I have been working on a solution, however I have found no paths yet.

Answer 1

I don't think there is an Euler path. The best I've been able to come up with for the moment is the following path:

It takes all the edges exactly once, except for two of them that are taken twice.

Answer 2

The graph of the city streets looks like this:

A-B-C-D
| | | |
E-F-G-H
| | | |
J-K-L-M

To make this graph have an Eulerian path, we can add two edges between BC and KL; our policeman should start at E and end at H, or the other way around.

A-B=C-D
| | | |
E-F-G-H
| | | |
J-K=L-M

An explicit tour of the streets is given by $$EABFEJKFGCBCDHGLKLMH.$$ This has 19 street segments and is minimal, since we cannot add just one edge to the graph and leave only two vertices of odd degree.

Answer 3

This graph has 6 odd-degree vertex. To find an Euler path in this graph, we must add two edges to connect two pairs of neighbour odd-vertex so they become even-degree vertex.

So the policeman can follow an Euler path on this graph. Thus, the answer is 17 + 2 = 19 segments.