Given a set $\pc=\{a_i,b_i\}_{i=1}^m$ of pairs of vertices in a graph G, is there a collection of paths $\{P_i\}_{i=1}^m$ such that $P_i$ connects $a_i$ with $b_i$ and $\{V(P_i)\}_{i=1}^m$ partitions $V(G)$? We study this problem for the graph $Q_n-\ff$ obtained from the n-dimensional hypercube $Q_n$ by removing a set $\ff$ of faulty vertices. We show that an obvious necessary condition for the existence of such a partition is also sufficient provided $2|\pc|+ 3|\ff|\le n-3$. As a corollary, we obtain a similar characterization for the existence of a hamiltonian cycle and a hamiltonian path of $Q_n-\ff$ provided $|\ff|\le(n-5)/3$. On the other hand, if the size of $\ff$ is not limited, the problems are NP-complete.

Given a set ${\cal P}$ of at most 2n-3 prescribed edges ($n\ge2$), the n-dimensional hypercube Q n contains a Hamiltonian cycle passing through all edges of ${\cal P}$ iff the subgraph induced by ${\cal P}$ consists of pairwise vertex-disjoint paths. This answers a question of Caha and Koubek, who showed that for any $n\ge3$ there are 2n-2 edges of Q n not contained in any Hamiltonian cycle, but that still satisfy the above condition.