A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d H (x, y) ≤ d G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q n has at least clog2 n · 2n edges.
['József Balogh', 'Alexandr V. Kostochka']
On 2-Detour Subgraphs of the Hypercube