Lower bound Lean Unrefereed

How few edges preserve a hypercube’s diameter?

Edition 3 · On this site since · last revised · Verify & co-author
Kind
Lower bounds with finite certificates
Status
General bound and finite certificates checked in Lean; unrefereed
Prior work
Builds on the edge-deletion bounds of Bouabdallah, Delorme and Djelloul and the construction of Charton and coauthors
On this page
  1. The statement
  2. Check it yourself
  3. Worked examples
  4. Status and who checked it
  5. Prior work
  6. Further reading

The statement

The nn-cube QnQ_n has the 2n2^n strings of nn bits as vertices, joined when they differ in one bit; its diameter is nn. Let f(n)f(n) be the fewest edges of a spanning subgraph of QnQ_n that still has diameter nn (Graham's hypercube problem).

Theorem 1. For every n≥2n \ge 2, every spanning subgraph of QnQ_n with diameter nn has at least

2n+⌈2n−2nn−1⌉2^n + \left\lceil \frac{2^n - 2n}{n - 1} \right\rceil

edges.

Theorem 2. No spanning subgraph of Q5Q_5 with diameter 5 has 38 edges. With Theorem 1, f(5)≥39f(5) \ge 39. A construction with 40 edges is known, so f(5)f(5) is 39 or 40.

Stronger bounds. Counting distance layers from opposite corners gives f(6)≥76f(6) \ge 76, f(7)≥150f(7) \ge 150 and f(8)≥294f(8) \ge 294. In dimension six an explicit graph gives f(6)≤81f(6) \le 81. The integer certificates extend through dimension 32.

Check it yourself

How the bounds compare. The general inequality applies in every dimension. The finite certificates can give a larger lower bound.

Dimension General inequality Certified lower bound Edges in a known construction
3 9 9 9
4 19 20 20
5 38 39 40
6 75 76 81
7 147 150 161
8 291 294 324

At n=4n = 4: 24+⌈(16−8)/3⌉=16+3=192^4 + \lceil (16 - 8)/3 \rceil = 16 + 3 = 19.

The first step of the proof, by hand. Every edge of QnQ_n joins a string of even weight to one of odd weight, so a path between two strings has the parity of their Hamming distance. Hence, in a subgraph of diameter nn, half of QnQ_n (the 2n−12^{n-1} strings whose distance from a vertex has the parity of n−1n - 1) lies within distance n−1n - 1 of that vertex. And every vertex has degree at least 2: a vertex with one edge, along bit ii, could not reach the string that differs from it in every bit but ii within n−1n - 1 steps.

Worked examples

  • n=3n = 3. f(3)=9f(3) = 9, and Theorem 1, the 1995 bound and the construction all give 9.
  • n=4n = 4. f(4)=20f(4) = 20 is a value the literature reports; two computations here checked it again, and a separate hand proof that f(4)≥20f(4) \ge 20 was read by two agents with no gap found. Theorem 1 alone gives 19.
  • Large nn. The distance-sphere argument raises the asymptotic lower coefficient to 3/23/2 on the scale 2n/(n−1)2^n/(n-1) above 2n2^n. Theorem 1 alone gives 2n+2n/(n−1)−O(1)2^n + 2^n/(n - 1) - O(1). The 1995 bound gives 2n+2n/(2n−1)−O(1)2^n + 2^n/(2n - 1) - O(1), so Theorem 1 roughly doubles the second term. The construction has 2n+(n⌊n/2⌋)−22^n + \binom{n}{\lfloor n/2 \rfloor} - 2 edges, so the true second term is still only known to lie between order 2n/n2^n/n and order 2n/n2^n/\sqrt{n}.

Status and who checked it

  • Written proofs, by hand. Theorem 1 counts the excess degree in balls around each vertex, using the parity fact above; Theorem 2 adds an identity special to n=5n = 5.
  • Formal verification. Lean checks the general lower bound and the integer certificates. The downloadable checker recomputes the finite inequalities, including the separate three-radius certificate in dimension seven.
  • Comparison. The 1995 lower bound is never attained for n≥4n \ge 4. Five entries of a published edge-deletion table (Bass and Sudborough, Table 1, for n=4n = 4 to 8) are false: the table equals the 1995 bound at every nn, and at n=5n = 5 it implies a graph with 35 edges.
  • Open. Whether f(5)f(5) is 39 or 40: a computer search to decide it ended "not decided" with no candidate.

Prior work

Credited. The question is from Erdős, Hamburger, Pippert and Weakley (1996), Graham and Harary (1992) and Bouabdallah, Delorme and Djelloul (1995). The 1995 bounds are Bouabdallah, Delorme and Djelloul's. The construction with 2n+(n⌊n/2⌋)−22^n + \binom{n}{\lfloor n/2 \rfloor} - 2 edges is credited by Nenadov, Sawhney, Sudakov and Wagner to the 1996 paper; their paper gives a lower bound of the same order.

Searches run. Eight works the proofs cite were sought by title or DOI, with cached sources and digests: the 1992, 1995, 1996 and 1997 papers, Djelloul's 1993 thesis, Bass and Sudborough's 2000 and 2002 papers, and Jasim and Najim (2024). The 1995 summary calls both of its formulas bounds and claims no value; Bass and Sudborough's table goes back to 2000. No lower bound on f(n)f(n) above the 1995 one turned up, and no value of f(5)f(5). No priority is claimed. On 2026-11-22, a Google Scholar sweep (5 queries) found no prior work stating this claim.

Still owed. The body of the 1995 paper, its 1990 version (a research report from Orsay) and Djelloul's thesis could not be reached on a second try; until they are read, this is a bounded reading, not an absence.

Further reading