We conjecture that for every perfect matching M of the d-dimensional
n-vertex hypercube, d\geq 2, there exists a second perfect matching M'
such that the union of M and M' forms a Hamiltonian circuit of the
d-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions that do not get used by M. As a consequence, if M_d is the
number of perfect matchings and H_d is the number of Hamiltonian circuits of
the d-dimensional hypercube, then M_{d-2}^4\leq H_d\leq M_d^2/4.
By known bounds on the number of perfect matchings of the d-dimensional
hypercube that show M_d={(\frac{d}{e}(1+o(1)))}^{n/2} and,
in particular, M_d\leq {(d!)}^{n/(2d)} we infer that
{(\frac{d}{e}(1-o(1)))}^{n/2}\leq H_d \leq {(d!)}^{n/(2d)}{((d-1)!)}^{n/(2(d-1))}/2.
We finally strenthen this result to a nearly tight bound
{((d\log 2/(e\log\log d))(1-o(1)))}^n\leq H_d\leq {((d/e)(1+o(1)))}^n.
We extend the results to graphs that are the Cartesian product of squares
and arbitrary bipartite regular graphs that have a Hamiltonian cycle.
We also study a labeling scheme related to matchings.