Long geodesics in subgraphs of the cube

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