Long paths and cycles in subgraphs of the cube

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 2d − 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 2d.