Checking the minimum length of a cycle in a graph with odd vertices.

Question

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?

Answer 1

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.

Answer 2

For every vertex of odd degree, at least one adjacent edge must be taken at least twice. Fortunately, all such vertices come in pairs of neighbours. So turn each edge that connects to odd vertices into a double edge; that increases the edge count by four.