Longest path through hypercube corners
Take a Hamiltonian path $P$ of minimal length on the $n-1$-cube, which has length $2^{n-1}-1$. Construct a path $Q$ in the $n$-cube as follows. For each edge $(e_1,\dots,e_i,\dots,e_{n-1})\to(e_1,\dots,1-e_i,\dots,e_{n-1})$ in P add edges $(e_1,\dots,e_i,\dots,e_{n-1},0)\to(1-e_1,\dots,1-e_i,\dots,1-e_{n-1},1)$ and $(1-e_1,\dots,1-e_i,\dots,1-e_{n-1},1)\to(e_1,\dots,1-e_i,\dots,e_{n-1},0)$ to $Q$. Add the final long diagonal to $Q$. In the end $Q$ is Hamiltonian and has the maximal length $2^{n-1}\sqrt{n}+(2^{n-1}-1)\sqrt{n-1}$.
Illustrating @MTyson's construction for $d=n=2$. We start with an edge $(0,1)$ for the $1$-cube, and replace $(0,1)$ with $(0,0),(1,1)$ and $(1,1),(1,0)$. This leaves one final long diagonal $(1,0),(0,1)$:
And the length of the path is $$ 2^1 \sqrt{2} + (2^1 -1 ) \sqrt{1} = 2 \sqrt{2} + 1 \;. $$
For $d=n=3$, MTyson's construction yields exactly the path I illustrated: $(1, 7, 2, 8, 3, 5, 4, 6)$. Here I will use the vertex indices illustrated in the main post, rather than the coordinates.
- One starts with the $2$-cube path $(1,2,3)$.
- The $(1,2)$ edge is replaced by $(1,7,2)$.
- The $(2,3)$ edge is replaced by $(2,8,3)$.
- The $(3,4)$ edge is replaced by $(3,5,4)$.
- Finally, the last diagonal is added: $(4,6)$.
We can in fact, a corrollary from MTyson's post is that we can construct a graph $G$ isomorphic to a hypercube $H$ (where the vertices are the $d$-bit strings and two vertices are adjacent in $H$ if they differ in precisely one bit) such that every edge in $G$ has length at least $\sqrt{d-1}$ in this metric, and $G$ admits a Hamiltonian circuit where half the edges have length $\sqrt{d}$.
Vertex $(u_1,u_2,\ldots, u_d)$ is adjacent in $G$ to $(1-u_1,1-u_2,\ldots, 1-u_{i-1}, u_i, 1-u_{i+1}, \ldots, 1-u_d)$ for all $i=1,2,\ldots, d-1$, and then vertex $(u_1,u_2, \ldots, u_d)$ is also adjacent in $G$ to its opposite $\bar{u}= (1-u_1,1-u_2, \ldots, 1-u_d)$.
Then $G$ is indeed isomorphic to a hypercube $H$ and has all edges of length at least $\sqrt{d-1}$. Furthermore, as $H$ admits a Hamiltonian circuit that has all edges of the form $\{(u_1, u_2, \ldots, u_{d-1}, u_d), (u_1, u_2, \ldots, u_{d-1}, 1-u_d)\}$ (i.e., the vertices differ in precisely their last bit), it follows that $G$ admits a Hamiltonian circuit that has all edges $\{u,\bar{u}\}$.
One can also check that no Hamiltonian cycle can have longer length than $2^{d-1}(\sqrt{d} + \sqrt{d-1})$. Indeed, for each vertex $u$, there is only one other vertex that is $\sqrt{d}$ distance from $u$. So this implies that the edges $\{e = \{u,v\}; ||u-v||_2 = \sqrt{d} \}$ form a matching. Thus only half of the edges $e$ in a Hamiltonian cycle can have length $\sqrt{d}$, the remaining must have length no more than $\sqrt{d-1}$, giving the upper bound.