Q:

Minimum number of repeated edges to solve Chinese postman problem on $Q_n$

Minimum number of repeated edges to solve the Chinese postman problem on $Q_n$ ($n$-dimensional hypercube).
Chinese postman problem is very famous in graph theory, especially on Eulerian and Hamiltonian. The Chinese Postman Problem is to find the shortest route in a network that uses every arc (directed edge) and gets back to where they started (closed problem) or doesn't go back (open problem). Anybody can help me to solve my question ?

A:

You seem to ask for the directed version of the Chinese postman problem, so I will assume that
you want to use every edge of $Q_n$ in both directions.
The minimum number of repeated edges under these conditions is zero.
This is easy to see for even dimensions: $Q_{2n}$ has an Eulerian circuit, and by travelling it once
in each direction you fulfill the requirement without any duplicate edges.
For odd dimensions we see $Q_{2n+1}$ as two "floors" with a $Q_{2n}$ on each floor and vertical edges between the floors.
We start at an arbitrary vertex $x$ on the bottom floor and take the vertical edge to $y$ on the top floor.
Now we continue along the $Q_{2n}$-trail on the top floor we just found with one "enhancement": each time we
visit a vertex for the first time we take the vertical edge to the bottom floor and go back up again.
When we have returned at $y$ we take the vertical edge back to $x$.
Now we are back where we started and we have traversed all vertical edges and all edges on the top floor
exactly once. What remains is to travel the $Q_{2n}$ on the bottom floor and we already solved that.
NOTE: for the undirected version the minimum number of repeated edges is still zero for even dimensions
but it is $2^{2n}$ for $Q_{2n+1}$, using almost the same method.

