AFTD Auto-Formalizing Theoretical Domains

hypercube_graph

def

The n-dimensional hypercube graph Q_n has vertex set {0, 1}^n, with two vertices adjacent if and only if their Hamming distance is 1 (they differ in exactly one coordinate).

Statement

def hypercube_graph (n : ℕ) : SimpleGraph (Fin n → Bool)
Defined in
arXiv:2611.16243 Section 1
Verified
16 Nov 2026
Axioms
none listed
Used by 3
  • is_antipodal_coloringGiven n : ℕ, an edge coloring c : (hypercube_graph n).edgeSet → Bool is antipodal if for all vertices u, v : Fin n → Bool, given proofs h…
  • antipodal_coloring_exists_red_path_of_pair_labellingConditional form of the antipodal-coloring theorem: if for every K ≥ 2 there is no labelling of the vertices of Q_K by ordered pairs of…
  • hypercube_red_subgraphGiven n : ℕ and an edge coloring c : (hypercube_graph n).edgeSet → Bool, hypercube_red_subgraph n c is the simple graph on vertex type Fin…

Read back from the Lean

hypercube_graph n is the simple graph whose vertex type is Fin n → Bool, where two vertices u and v are adjacent if and only if the Hamming distance between u and v is equal to 1.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The n-dimensional hypercube graph Q_n on {0, 1}^n with edges between vertices at Hamming distance 1. -/
def hypercube_graph (n : ℕ) : SimpleGraph (Fin n → Bool) where
  Adj u v := hammingDist u v = 1
  symm := ⟨by intro u v h; rw [hammingDist_comm]; exact h⟩
  loopless := ⟨by intro u h; rw [hammingDist_self] at h; contradiction⟩
See it in the graphDiscuss this resultChallenge it