Determine the shortest distance travelled to pass through every path once and return to the starting position

Question

A $5 \times 4$ lattice points are all connected to represent possible paths. Each path is exactly $1$ meter long. Determine the shortest distance (in meters) a person needs to travel so that the person walks through each path at least once and returns to the starting position.

So quite clearly the minimum the distance has to be is $31$ meters (the sum of all the edges' lengths). And by trying out some paths I was able to figure out $38$ meters is the min. possible distance travelled, but I was wondering if there was a more 'mathematical' way because my way took a lot of time.

Answer 1

If all vertices had even degree a Eulerian circuit through the graph would exist. The question therefore is: How can we double a minimal number of edges such that all vertices obtain even degree?

Since there are $10$ vertices of odd degree we need at least $5$ additional edges. You have found a solution with $7$ additional edges; therefore the solution is one of $5$, $6$, or $7$.

I could not do better than $7$ myself.

Answer 2

Notice there are more than two vertices of odd degrees. The graph is not even semi-Eulerian. So to find the distance, we have to compare the distances of pairing of odd vertices. In this case it's easier because the given graph is a grid with equal weights.

For the bottom 3 points, that are odd, the minimum pairing that connects these points is obviously $2$ meters. For the 2 points on the leftmost side, the minimum pairing is $1$ meters. By symmetry, the minimum sum of distances of pairs of odd vertices is $6$. Adding to the sum of all the edges' lengths gives $31+6=37.$