Long geodesics in subgraphs of the cube

We show that any subgraph of the hypercube QnQn of average degree dd contains a geodesic of length dd, where by geodesic we mean a shortest path in QnQn. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine.