AFTD Auto-Formalizing Theoretical Domains

hypercube_red_subgraph

def

Given n : ℕ and an edge coloring c : (hypercube_graph n).edgeSet → Bool, hypercube_red_subgraph n c is the simple graph on vertex type Fin n → Bool where vertices u and v are adjacent if and only if there exists a proof h that u and v are adjacent in hypercube_graph n such that c ⟨s(u, v), h⟩ = true.

Statement

def hypercube_red_subgraph (n : ℕ) (c : (hypercube_graph n).edgeSet → Bool) : SimpleGraph (Fin n → Bool)
Defined in
arXiv:2611.16243 Section 2
Verified
16 Nov 2026
Axioms
none listed
Built on 1
  • hypercube_graphThe 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…
Used by 1

Read back from the Lean

Given a natural number n and an edge-coloring function c : (hypercube_graph n).edgeSet → Bool, hypercube_red_subgraph n c is the simple graph on vertices Fin n → Bool where two vertices u and v are adjacent if and only if u and v are adjacent in hypercube_graph n (witnessed by h) and the edge ⟨s(u, v), h⟩ satisfies c ⟨s(u, v), h⟩ = true.

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 spanning subgraph of Q_n formed by the edges of color red (true) under edge coloring c. -/
def hypercube_red_subgraph (n : ℕ) (c : (hypercube_graph n).edgeSet → Bool) : SimpleGraph (Fin n → Bool) where
  Adj u v := ∃ h : (hypercube_graph n).Adj u v, c ⟨s(u, v), h⟩ = true
  symm := ⟨by
    intro u v ⟨h, hc⟩
    refine ⟨h.symm, ?_⟩
    have : (⟨s(v, u), h.symm⟩ : (hypercube_graph n).edgeSet) = ⟨s(u, v), h⟩ := Subtype.ext Sym2.eq_swap
    rw [this]
    exact hc⟩
  loopless := ⟨by
    intro u ⟨h, _⟩
    exact (hypercube_graph n).loopless.irrefl u h⟩
See it in the graphDiscuss this resultChallenge it