Covering hypercubes by isometric paths

An isometric path is merely any shortest path between two vertices. If the vertices of the hypercube Q_n are represented by the set of 0–1 vectors of length n, an isometric path is obtained by changing the coordinates of a vector one at a time, never changing the same coordinate more than once. The minimum number of isometric paths required to cover the vertices of Q_n is at least 2ⁿ/(n+1). We show that when n+1 is a power of 2, the lower bound is in fact the minimum. In doing so, we construct a family of disjoint isometric paths which can be used to find an upper bound for additional classes of hypercubes.