Long geodesics in subgraphs of the cube.

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