  Let $Q_n$ denote the graph of the $n$-dimensional cube with vertex set
$\{0,1\}^n$ in which two vertices are adjacent if they differ in exactly one
coordinate. Suppose $G$ is a subgraph of $Q_n$ with average degree at least
$d$. How long a path can we guarantee to find in $G$?
  Our aim in this paper is to show that $G$ must contain an exponentially long
path. In fact, we show that if $G$ has minimum degree at least $d$ then $G$
must contain a path of length $2^d-1$. Note that this bound is tight, as shown
by a $d$-dimensional subcube of $Q_n$. We also obtain the slightly stronger
result that $G$ must contain a cycle of length at least $2^d$ and prove
analogous results for other `product-type' graphs.
