Finding the shortest cycle in a graph using every edge

Question

I've had a brief introduction in graph theory. We have been given to find a shortest cycle visiting all edges and starting and finishing in $(0,0)$ in the following graph:

Since there are vertices like $(0,1)$ with an odd degree, there can't exist an Eulerian cycle. Therefore, the length has to be longer than 31, which is the amount of edges in the graph.

It's quite easy to find a cycle with length 38 by trying, visiting seven edges twice, however, I can't think of a way to prove that this actually is the shortest possible cycle.

I'm thinking: there are ten vertices with an odd degree, to which at least one edge that is visited twice must be connected. If we would take these edges as ((0,1),(0,2)), ((0,2),(0,3)), ((1,0),(2,0)), ((1,4),(2,4)), ((3,1),(3,2)), ((3,2),(3,3)) - that is, the edges between points with an odd parity -, that creates another problem: Now, the vertices (0,2) and (3,2) have already been visited twice, but the edges ((0,2),(1,2)) and ((2,2),(3,2)) have not been used yet. Now these edges would need to be visited twice as well, so there are at least 8 edges that have to be visited twice, making this a longer cycle than the one of length 38.

However, am I right in thinking that this at least means that the shortest cycle has a minimum length of 31+6=37? And how can I proceed in finding the shortest path, if it has length 37, or in proving that length 37 isn't possible?

I also noticed that this is a bipartite graph. We could colour the vertices $(p,q)$ for which $2\mid p+q$ blue, and the others red. I'm not sure if this is useful, or how to proceed from this, though.

EDIT: When this question was originally posted, it was marked as a homework question, and OP requested that a complete answer not be given. Well, many years have passed since this question was posted, so it is probably safe to post a complete answer at this time.

Answer 1

You want to find a multigraph that contains the graph in question and has all vertices with even degree. Another way to think of it is that you have to add a graph to the one you allready have in which the only vertices of odd degree are the ones which have odd degree in the original graph.

---

Seeing Leon Droogendijik comment what I told you is what wikipedia says, you need to find the multigraph with the least edges on the same vertex set that is a supergraph of the graph in question. To solve this problem you need to find the smallest multigraph whose only odd vertices are the vertices that are odd in your graph.

Answer 2

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.