In this paper, we first present new proofs, much shorter and much simpler than can be found elsewhere, of two facts about Hypercubes: that for the -dimensional Hypercube, there exist sets of paths by which any \emph{permutation routing} task may be accomplished in at most steps without queueing; and, when is even, there exists an edge decomposition of the Hypercube into precisely edge-disjoint Hamiltonian cycles. The permutation routing paths are computed off-line. Whether or not these paths may be computed by an online parallel algorithm in -time has long been an open question. We conclude by speculating on whether the use of a Hamiltonian decomposition of the Hypercube might lead to such an algorithm.
