Long paths and cycles in subgraphs of the cube (Q2439832)

It is shown that if \(G\) is a subgraph of the \(n\)-dimensional \(Q_n\) with minimum degree \(d\), then \(G\) contains a path of length \(2^d - 1\) and a cycle of length at least \(2^d\). The result is sharp, as the subgraph \(Q_d\) of \(Q_n\) indicates. If \(G\) is not a subgraph \(Q_d\) and has minimum degree \(d\), then there is a path of length at least \(2^d\). It is also proved that if \(G\) has average degree at least \(d\), then \(G\) contain a path of length \(2^{d/2} - 1\). It is conjectured that \(2^{d/2} - 1\) can be improved to \(2^d - 1\) for average degree at least \(d\). Some generalizations are given to other structures besides the cube, for example to the \(n\)-dimensional grid \(Z^n\).