The dodecahedral graph is the Platonic graph corresponding to the connectivity of the vertices of a dodecahedron, with 20 nodes and 30 edges. Assuming all edges have a length (weight) of 1, I want to find the shortest path that
- visits every node at least once,
- traverses every edge at least once (regardless of direction),
- never traverses the same edge twice in a row (must visit other edges before returning)
- starts and ends at the same node.
There are thirty edges, so covering all of them requires a path length of at least 30. I know that because each node is connected to three edges, at least one of those edges must be traversed more than once to cover all three. However, I don't know how many edges need to be double-counted, or if any need to be triple-counted (or more).
Is there a good way to figure this out besides brute-force checking all possible paths?
As an initial observation, as each vertex will need to be visited at least twice (at most two edges are used on first visit, so a second visit is necessary to use the third edge) so a clear lower bound would be that it needs at least 40 steps.
As a second observation, if you add ten more edges where each vertex was involved in exactly one of the newly added edges, then the graph becomes 4-regular and thus eulerian (has a circuit which uses each edge exactly once).
As a final observation, if we could find a perfect cover, those ten edges to be added could simply duplicate the edges used in the perfect cover. Indeed, trying to find a perfect cover in a greedy fashion is not difficult.
As all vertices in the graph with duplicated edges have even degree, there exists a eulerian circuit here that uses each edge exactly once and is therefore of length $40$.
This circuit corresponds to a circuit in the original graph where we simply reuse edges where we would otherwise have traveled along a parallel edge. Since we knew we needed at least $40$ steps, this proves that such a eulerian circuit is optimal.
Included now is also an explicit example of a circuit that further avoids reusing a particular edge twice in succession.