Note: this is homework. Please do not give a complete answer.
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.