eulerian-pathgraph theory
I have the following graph:
Obviously, this graph does not have an eulerian cycle because it has vertices with odd degree. However, how can I find the cycle that visits every edge with the minimum length? It is clear that we will be repeating edges, but how can you find the path that repeats edges as few times as possible?
As the question correctly observes, there are ten odd-degree nodes that need to be revisited as part of a cyclic tour of the edges. If you double some of the edges (making a multigraph without loops), you can reduce the number of nodes with odd degree. Then for an Eulerian path on this generated multigraph, you'd need to find the least number of edges you can add to make all but two of the nodes of even degree. For an Eulerian cycle as required, you need to eliminate all odd nodes by adding such edges.
There's clearly a solution for $7$ added edges, as you say, illustrated below, and the $10$ odd nodes require at least $5$ added edges to resolve to even degree in a multigraph, so demonstrating that neither $5$ nor $6$ added edges are sufficient is required. The odd-degree nodes are here organized into four sets on the edges of the grid. If four adjacent odd nodes are connected with a doubled edge, choosing one from each set of adjacent blocks, the remaining two nodes (eg. $(0,3)$ and $(3,3)$) require 3 additional edges to connect, as per the illustration. If only three adjacent nodes are connected then both of the remaining pairs require at least two edges each to connect. In both cases $7$ doubled edges is the minimum, leading to the minimum tour length of $31+7=38$ edge traverses.
A question in which the adjacency of odd nodes was less straightforward, or in which edges are different lengths, could be significantly harder to answer.
Consider the complete graph $K_5$: it has $5$ vertices, each of degree $4$, and how many edges?
Best Answer
There are $8$ vertices of odd degree, one pair on each edge of the square. Join these pairs by an an extra edge, and find an Eulerian cycle in the new graph.
Then you can replace the traversal of the new edge by a traversal of the old edge in the same direction, and you'll have a minimum-length cycle that traverses all edges of the graph.