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.
Best Answer
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.