AFTD Auto-Formalizing Theoretical Domains

exists_hypercube_coil

theoremverified

For every n ≥ 2, there exists a coil in the hypercube Q_n.

Statement

theorem exists_hypercube_coil (n : ℕ) (hn : 2 ≤ n) :
    ∃ S : Finset (Fin n → Bool), hypercube_coil n S
Source
arXiv:2610.36461 Section 1
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • hypercube_coilA subset S of vertices in the hypercube Q_n is a coil if it has size at least 4 and its induced subgraph is isomorphic to a cycle graph of…
  • simple_graph_hypercubeThe hypercube graph Q_n on vertex set Fin n → Bool, where two vertices are adjacent if and only if they differ at exactly one coordinate.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

For every natural number $n$ with $n \ge 2$, there exists a finite subset $S$ of vertices of the $n$-dimensional hypercube $\{0, 1\}^n$ (represented as Fin n → Bool) such that $S$ contains at least 4 vertices and the subgraph induced by $S$ is isomorphic to the cycle graph on $|S|$ vertices (i.e., $S$ forms an induced cycle, or coil, of length at least 4).

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

The proof, explained

To prove the existence of a coil (an induced cycle of length at least 4) in the hypercube Q_n for any n ≥ 2, the proof explicitly constructs an induced 4-cycle. First, it identifies the 2-dimensional hypercube Q₂ with the 4-cycle C₄ via an isomorphism verified by exhaustive computation. For any n ≥ 2, it embeds Q₂ into Q_n via an injective padding map that places the two coordinates at indices 0 and 1 and sets all other coordinates to false. Because this embedding preserves and reflects adjacency, its 4-element image induces a subgraph isomorphic to Q₂ ≃ C₄, yielding a valid coil of length 4 in Q_n.

  1. Unique existence on finite types and adjacency in the hypercube graph Q_n are decidable relations. automation

    Unfolding the definitions reveals that unique existence reduces to bounded quantification over a finite type, and hypercube adjacency is defined by unique existence of a differing coordinate; typeclass synthesis derives both decidability instances automatically.

    lines 1–11

    instance exists_hypercube_coil_decidable_exists_unique {α : Type*} [Fintype α] [DecidableEq α] (p : α → Prop) [DecidablePred p] :
        Decidable (∃! x, p x) := by
      dsimp [ExistsUnique]
      infer_instance
    
    instance exists_hypercube_coil_decidable_simple_graph_hypercube_adj (n : ℕ) :
        DecidableRel (simple_graph_hypercube n).Adj := by
      intro x y
      dsimp [simple_graph_hypercube, SimpleGraph.fromRel]
      infer_instance
    
  2. The 2-dimensional hypercube Q₂ is isomorphic as a simple graph to the 4-cycle C₄. automation

    The map `exists_hypercube_coil_e_fin` traces a 4-cycle through the vertices of Q₂. Its bijectivity and adjacency preservation are checked by exhaustive finite evaluation using `decide`, yielding the graph isomorphism `exists_hypercube_coil_e_iso`.

    lines 12–28

    def exists_hypercube_coil_e_fin : Fin 4 → (Fin 2 → Bool)
      | 0 => fun _ => false
      | 1 => fun i => i = 0
      | 2 => fun _ => true
      | 3 => fun i => i = 1
    
    lemma exists_hypercube_coil_adj_map :
        ∀ a b : Fin 4, (simple_graph_hypercube 2).Adj (exists_hypercube_coil_e_fin a) (exists_hypercube_coil_e_fin b) ↔ (SimpleGraph.cycleGraph 4).Adj a b := by
      decide
    
    lemma exists_hypercube_coil_e_fin_bij : Function.Bijective exists_hypercube_coil_e_fin := by
      decide
    
    noncomputable def exists_hypercube_coil_e_iso : simple_graph_hypercube 2 ≃g SimpleGraph.cycleGraph 4 :=
      (RelIso.mk (Equiv.ofBijective exists_hypercube_coil_e_fin exists_hypercube_coil_e_fin_bij)
        (fun {a b} => exists_hypercube_coil_adj_map a b)).symm
    
  3. For n ≥ 2, the coordinate indices 0 and 1 are well-defined and distinct elements of Fin n.

    The bounds 0 < n and 1 < n follow from 2 ≤ n by linear arithmetic (`omega`). If these two elements of Fin n were equal, their underlying natural numbers would be equal (0 = 1), contradicting `Nat.zero_ne_one`.

    lines 29–37

    uses Fin.mk.inj, Nat.zero_ne_one

    def exists_hypercube_coil_i0 (n : ℕ) (hn : 2 ≤ n) : Fin n := ⟨0, by omega⟩
    def exists_hypercube_coil_i1 (n : ℕ) (hn : 2 ≤ n) : Fin n := ⟨1, by omega⟩
    
    lemma exists_hypercube_coil_i0_ne_i1 (n : ℕ) (hn : 2 ≤ n) :
        exists_hypercube_coil_i0 n hn ≠ exists_hypercube_coil_i1 n hn := by
      intro h
      have : (0 : ℕ) = 1 := Fin.mk.inj h
      exact Nat.zero_ne_one this
    
  4. The padding map embeds 2-bit vectors into n-bit vectors by setting coordinate 0 to u(0), coordinate 1 to u(1), and all other coordinates to false.

    Evaluating the definition of `exists_hypercube_coil_pad` at index 0 simplifies via `if_pos` to u(0); at index 1 it simplifies via `if_neg` and `if_pos` to u(1); and at any other index both conditions are false, evaluating to false via `if_neg`.

    lines 38–60

    uses if_pos, if_neg, Ne.symm, exists_hypercube_coil_i0_ne_i1

    def exists_hypercube_coil_pad (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) : Fin n → Bool :=
      fun i =>
        if i = exists_hypercube_coil_i0 n hn then u 0
        else if i = exists_hypercube_coil_i1 n hn then u 1
        else false
    
    lemma exists_hypercube_coil_pad_i0 (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) :
        exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i0 n hn) = u 0 := by
      change (if (exists_hypercube_coil_i0 n hn = exists_hypercube_coil_i0 n hn) then u 0 else _) = u 0
      rw [if_pos rfl]
    
    lemma exists_hypercube_coil_pad_i1 (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) :
        exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i1 n hn) = u 1 := by
      change (if (exists_hypercube_coil_i1 n hn = exists_hypercube_coil_i0 n hn) then _
        else if (exists_hypercube_coil_i1 n hn = exists_hypercube_coil_i1 n hn) then u 1 else _) = u 1
      rw [if_neg (Ne.symm (exists_hypercube_coil_i0_ne_i1 n hn)), if_pos rfl]
    
    lemma exists_hypercube_coil_pad_other (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) (i : Fin n)
        (h0 : i ≠ exists_hypercube_coil_i0 n hn) (h1 : i ≠ exists_hypercube_coil_i1 n hn) :
        exists_hypercube_coil_pad n hn u i = false := by
      dsimp [exists_hypercube_coil_pad]
      rw [if_neg h0, if_neg h1]
    
  5. Two padded vectors can differ only at index 0 or index 1.

    Assume for contradiction that two padded vectors differ at some index i other than 0 and 1. By `exists_hypercube_coil_pad_other`, both padded vectors evaluate to false at i, so they are equal at i, yielding false ≠ false, a contradiction.

    lines 61–71

    uses Or.inl, Or.inr, exists_hypercube_coil_pad_other

    lemma exists_hypercube_coil_pad_diff (n : ℕ) (hn : 2 ≤ n) (u v : Fin 2 → Bool) (i : Fin n)
        (h : exists_hypercube_coil_pad n hn u i ≠ exists_hypercube_coil_pad n hn v i) :
        i = exists_hypercube_coil_i0 n hn ∨ i = exists_hypercube_coil_i1 n hn := by
      by_contra hc
      have h0 : i ≠ exists_hypercube_coil_i0 n hn := fun h' => hc (Or.inl h')
      have h1 : i ≠ exists_hypercube_coil_i1 n hn := fun h' => hc (Or.inr h')
      have hu := exists_hypercube_coil_pad_other n hn u i h0 h1
      have hv := exists_hypercube_coil_pad_other n hn v i h0 h1
      rw [hu, hv] at h
      exact h rfl
    
  6. The padding map from Fin 2 → Bool to Fin n → Bool is injective.

    If pad(u) = pad(v), evaluating both sides at index 0 yields u(0) = v(0) by `exists_hypercube_coil_pad_i0`, and evaluating at index 1 yields u(1) = v(1) by `exists_hypercube_coil_pad_i1`. By extensionality, u = v.

    lines 72–81

    uses congr_fun, exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i1

    lemma exists_hypercube_coil_pad_inj (n : ℕ) (hn : 2 ≤ n) :
        Function.Injective (exists_hypercube_coil_pad n hn) := by
      intro u v h
      ext ⟨i, hi⟩
      interval_cases i
      · have := congr_fun h (exists_hypercube_coil_i0 n hn)
        rwa [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0] at this
      · have := congr_fun h (exists_hypercube_coil_i1 n hn)
        rwa [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1] at this
    
  7. Two vertices of Q_n are adjacent if and only if they differ at exactly one coordinate.

    The hypercube graph is defined from the relation x ≠ y ∧ (∃! i, x i ≠ y i ∨ ∃! i, y i ≠ x i). Because inequality of booleans is symmetric, both disjuncts coincide. Moreover, if x and y differ at some coordinate, x ≠ y is immediate, making adjacency equivalent to differing at a unique coordinate.

    lines 82–95

    uses Ne.symm, Or.inl

    lemma exists_hypercube_coil_hypercube_adj_iff (n : ℕ) (x y : Fin n → Bool) :
        (simple_graph_hypercube n).Adj x y ↔ ∃! i : Fin n, x i ≠ y i := by
      dsimp [simple_graph_hypercube, SimpleGraph.fromRel]
      constructor
      · rintro ⟨-, h | h⟩
        · exact h
        · rcases h with ⟨i, hi, huniq⟩
          refine ⟨i, Ne.symm hi, fun j hj => huniq j (Ne.symm hj)⟩
      · intro h
        refine ⟨?_, Or.inl h⟩
        rintro rfl
        rcases h with ⟨i, hi, -⟩
        exact hi rfl
    
  8. The padding map preserves and reflects adjacency between Q₂ and Q_n.

    By the characterization of hypercube adjacency, two vertices are adjacent if and only if they differ at a unique coordinate. If pad(u) and pad(v) differ at a unique index i, that index must be 0 or 1, which implies u and v differ at that unique coordinate in Fin 2. Conversely, a unique differing coordinate in Fin 2 maps to index 0 or 1, and since pad(u) and pad(v) agree at all other coordinates, it remains the unique differing coordinate in Fin n.

    lines 96–147

    uses exists_hypercube_coil_hypercube_adj_iff, exists_hypercube_coil_pad_diff, exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i1, exists_hypercube_coil_i0_ne_i1

    lemma exists_hypercube_coil_pad_adj (n : ℕ) (hn : 2 ≤ n) (u v : Fin 2 → Bool) :
        (simple_graph_hypercube n).Adj (exists_hypercube_coil_pad n hn u) (exists_hypercube_coil_pad n hn v) ↔
        (simple_graph_hypercube 2).Adj u v := by
      rw [exists_hypercube_coil_hypercube_adj_iff, exists_hypercube_coil_hypercube_adj_iff]
      constructor
      · rintro ⟨i, hi, huniq⟩
        rcases exists_hypercube_coil_pad_diff n hn u v i hi with rfl | rfl
        · rw [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0] at hi
          refine ⟨0, hi, ?_⟩
          intro j hj
          fin_cases j
          · rfl
          · exfalso
            have h1 : exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i1 n hn) ≠
                exists_hypercube_coil_pad n hn v (exists_hypercube_coil_i1 n hn) := by
              rwa [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1]
            have := huniq (exists_hypercube_coil_i1 n hn) h1
            exact exists_hypercube_coil_i0_ne_i1 n hn this.symm
        · rw [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1] at hi
          refine ⟨1, hi, ?_⟩
          intro j hj
          fin_cases j
          · exfalso
            have h0 : exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i0 n hn) ≠
                exists_hypercube_coil_pad n hn v (exists_hypercube_coil_i0 n hn) := by
              rwa [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0]
            have := huniq (exists_hypercube_coil_i0 n hn) h0
            exact exists_hypercube_coil_i0_ne_i1 n hn this
          · rfl
      · rintro ⟨j, hj, huniq⟩
        fin_cases j
        · refine ⟨exists_hypercube_coil_i0 n hn, ?_, ?_⟩
          · dsimp
            rwa [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0]
          · intro i hi
            rcases exists_hypercube_coil_pad_diff n hn u v i hi with rfl | rfl
            · rfl
            · exfalso
              rw [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1] at hi
              have := huniq 1 hi
              contradiction
        · refine ⟨exists_hypercube_coil_i1 n hn, ?_, ?_⟩
          · dsimp
            rwa [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1]
          · intro i hi
            rcases exists_hypercube_coil_pad_diff n hn u v i hi with rfl | rfl
            · exfalso
              rw [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0] at hi
              have := huniq 0 hi
              contradiction
            · rfl
    
  9. Subgraphs induced by equal vertex subsets are isomorphic to the same target graph.

    Given s = t, substituting along the equality carries any graph isomorphism from the induced subgraph on t directly to the induced subgraph on s.

    lines 148–152

    lemma exists_hypercube_coil_induce_congr {V : Type*} (G : SimpleGraph V) {s t : Set V} (h : s = t)
        {W : Type*} {H : SimpleGraph W} (iso : G.induce t ≃g H) : Nonempty (G.induce s ≃g H) := by
      cases h
      exact ⟨iso⟩
    
  10. The image S of the padding map in Q_n has cardinality exactly 4, which satisfies 4 ≤ |S|.

    Let S be the image of the universal set of 2-bit vectors under the padding map. Because the padding map is injective, the cardinality of S equals the cardinality of Fin 2 → Bool, which is 2² = 4. The inequality 4 ≤ 4 is discharged by linear arithmetic.

    lines 153–166

    uses exists_hypercube_coil_pad_inj, exists_hypercube_coil_pad_adj, Finset.card_image_of_injective

    /-- Existence of a coil in Q_n for n ≥ 2. -/
    theorem exists_hypercube_coil (n : ℕ) (hn : 2 ≤ n) :
        ∃ S : Finset (Fin n → Bool), hypercube_coil n S := by
      let pad := exists_hypercube_coil_pad n hn
      have hpad_inj := exists_hypercube_coil_pad_inj n hn
      have hpad_adj := exists_hypercube_coil_pad_adj n hn
      let S : Finset (Fin n → Bool) := Finset.univ.image pad
      use S
      dsimp [hypercube_coil]
      have hcard : S.card = 4 := by
        change (Finset.univ.image pad).card = 4
        rw [Finset.card_image_of_injective _ hpad_inj]
        rfl
      refine ⟨by omega, ?_⟩
  11. The induced subgraph on S is isomorphic to C₄, completing the proof that S is a coil in Q_n.

    The padding map is an adjacency-preserving injection onto its range, which defines an isomorphism between the induced subgraph on S and Q₂. Composing this with the isomorphism between Q₂ and C₄ via `RelIso.trans` shows that the induced subgraph on S is isomorphic to C₄. Transferring along S = range(pad) concludes that S is a coil.

    lines 167–175

    uses RelIso.mk, Equiv.ofInjective, exists_hypercube_coil_e_iso, RelIso.trans, exists_hypercube_coil_induce_congr

      have hrange : (S : Set (Fin n → Bool)) = Set.range pad := by
        simp [S]
      rw [hcard]
      have iso1 : ((simple_graph_hypercube n).induce (Set.range pad)) ≃g simple_graph_hypercube 2 :=
        (RelIso.mk (Equiv.ofInjective pad hpad_inj) (fun {a b} => hpad_adj a b)).symm
      have iso2 : simple_graph_hypercube 2 ≃g SimpleGraph.cycleGraph 4 := exists_hypercube_coil_e_iso
      have iso : ((simple_graph_hypercube n).induce (Set.range pad)) ≃g SimpleGraph.cycleGraph 4 :=
        RelIso.trans iso1 iso2
      exact exists_hypercube_coil_induce_congr (simple_graph_hypercube n) hrange iso
Fin.mk.inj
two elements of Fin n are equal if and only if their underlying natural numbers are equal
Nat.zero_ne_one
zero is not equal to one
if_pos
an if-then-else with a true condition evaluates to its then-branch
if_neg
an if-then-else with a false condition evaluates to its else-branch
Ne.symm
inequality is a symmetric relation
exists_hypercube_coil_i0_ne_i1
for n ≥ 2, the coordinate indices 0 and 1 in Fin n are distinct
Or.inl
left injection into a disjunction (A implies A ∨ B)
Or.inr
right injection into a disjunction (B implies A ∨ B)
exists_hypercube_coil_pad_other
the padding map assigns false to any coordinate other than the first two
congr_fun
equal functions produce equal values on the same argument
exists_hypercube_coil_pad_i0
the padding map at coordinate 0 equals the 0-th coordinate of the 2-bit input
exists_hypercube_coil_pad_i1
the padding map at coordinate 1 equals the 1-st coordinate of the 2-bit input
exists_hypercube_coil_hypercube_adj_iff
two vertices in the hypercube Q_n are adjacent if and only if they differ at exactly one coordinate
exists_hypercube_coil_pad_diff
two padded vertices can differ only at coordinate 0 or coordinate 1
exists_hypercube_coil_pad_inj
the padding map embedding Q₂ into Q_n is injective
exists_hypercube_coil_pad_adj
two padded vertices are adjacent in Q_n if and only if their 2-bit preimages are adjacent in Q₂
Finset.card_image_of_injective
an injective map preserves the cardinality of a finite set
RelIso.mk
constructs an isomorphism of relations from a bijection that preserves and reflects the relation
Equiv.ofInjective
an injective function defines an equivalence with its image range
exists_hypercube_coil_e_iso
graph isomorphism between the 2-cube Q₂ and the cycle graph C₄
RelIso.trans
composition of relational isomorphisms is a relational isomorphism
exists_hypercube_coil_induce_congr
an isomorphism on an induced subgraph extends across equal vertex subsets

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

instance exists_hypercube_coil_decidable_exists_unique {α : Type*} [Fintype α] [DecidableEq α] (p : α → Prop) [DecidablePred p] :    Decidable (∃! x, p x) := by  dsimp [ExistsUnique]  infer_instanceinstance exists_hypercube_coil_decidable_simple_graph_hypercube_adj (n : ℕ) :    DecidableRel (simple_graph_hypercube n).Adj := by  intro x y  dsimp [simple_graph_hypercube, SimpleGraph.fromRel]  infer_instancedef exists_hypercube_coil_e_fin : Fin 4 → (Fin 2 → Bool)  | 0 => fun _ => false  | 1 => fun i => i = 0  | 2 => fun _ => true  | 3 => fun i => i = 1lemma exists_hypercube_coil_adj_map :    ∀ a b : Fin 4, (simple_graph_hypercube 2).Adj (exists_hypercube_coil_e_fin a) (exists_hypercube_coil_e_fin b) ↔ (SimpleGraph.cycleGraph 4).Adj a b := by  decidelemma exists_hypercube_coil_e_fin_bij : Function.Bijective exists_hypercube_coil_e_fin := by  decidenoncomputable def exists_hypercube_coil_e_iso : simple_graph_hypercube 2 ≃g SimpleGraph.cycleGraph 4 :=  (RelIso.mk (Equiv.ofBijective exists_hypercube_coil_e_fin exists_hypercube_coil_e_fin_bij)    (fun {a b} => exists_hypercube_coil_adj_map a b)).symmdef exists_hypercube_coil_i0 (n : ℕ) (hn : 2 ≤ n) : Fin n := ⟨0, by omega⟩def exists_hypercube_coil_i1 (n : ℕ) (hn : 2 ≤ n) : Fin n := ⟨1, by omega⟩lemma exists_hypercube_coil_i0_ne_i1 (n : ℕ) (hn : 2 ≤ n) :    exists_hypercube_coil_i0 n hn ≠ exists_hypercube_coil_i1 n hn := by  intro h  have : (0 : ℕ) = 1 := Fin.mk.inj h  exact Nat.zero_ne_one thisdef exists_hypercube_coil_pad (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) : Fin n → Bool :=  fun i =>    if i = exists_hypercube_coil_i0 n hn then u 0    else if i = exists_hypercube_coil_i1 n hn then u 1    else falselemma exists_hypercube_coil_pad_i0 (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) :    exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i0 n hn) = u 0 := by  change (if (exists_hypercube_coil_i0 n hn = exists_hypercube_coil_i0 n hn) then u 0 else _) = u 0  rw [if_pos rfl]lemma exists_hypercube_coil_pad_i1 (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) :    exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i1 n hn) = u 1 := by  change (if (exists_hypercube_coil_i1 n hn = exists_hypercube_coil_i0 n hn) then _    else if (exists_hypercube_coil_i1 n hn = exists_hypercube_coil_i1 n hn) then u 1 else _) = u 1  rw [if_neg (Ne.symm (exists_hypercube_coil_i0_ne_i1 n hn)), if_pos rfl]lemma exists_hypercube_coil_pad_other (n : ℕ) (hn : 2 ≤ n) (u : Fin 2 → Bool) (i : Fin n)    (h0 : i ≠ exists_hypercube_coil_i0 n hn) (h1 : i ≠ exists_hypercube_coil_i1 n hn) :    exists_hypercube_coil_pad n hn u i = false := by  dsimp [exists_hypercube_coil_pad]  rw [if_neg h0, if_neg h1]lemma exists_hypercube_coil_pad_diff (n : ℕ) (hn : 2 ≤ n) (u v : Fin 2 → Bool) (i : Fin n)    (h : exists_hypercube_coil_pad n hn u i ≠ exists_hypercube_coil_pad n hn v i) :    i = exists_hypercube_coil_i0 n hn ∨ i = exists_hypercube_coil_i1 n hn := by  by_contra hc  have h0 : i ≠ exists_hypercube_coil_i0 n hn := fun h' => hc (Or.inl h')  have h1 : i ≠ exists_hypercube_coil_i1 n hn := fun h' => hc (Or.inr h')  have hu := exists_hypercube_coil_pad_other n hn u i h0 h1  have hv := exists_hypercube_coil_pad_other n hn v i h0 h1  rw [hu, hv] at h  exact h rfllemma exists_hypercube_coil_pad_inj (n : ℕ) (hn : 2 ≤ n) :    Function.Injective (exists_hypercube_coil_pad n hn) := by  intro u v h  ext ⟨i, hi⟩  interval_cases i  · have := congr_fun h (exists_hypercube_coil_i0 n hn)    rwa [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0] at this  · have := congr_fun h (exists_hypercube_coil_i1 n hn)    rwa [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1] at thislemma exists_hypercube_coil_hypercube_adj_iff (n : ℕ) (x y : Fin n → Bool) :    (simple_graph_hypercube n).Adj x y ↔ ∃! i : Fin n, x i ≠ y i := by  dsimp [simple_graph_hypercube, SimpleGraph.fromRel]  constructor  · rintro ⟨-, h | h⟩    · exact h    · rcases h with ⟨i, hi, huniq⟩      refine ⟨i, Ne.symm hi, fun j hj => huniq j (Ne.symm hj)⟩  · intro h    refine ⟨?_, Or.inl h⟩    rintro rfl    rcases h with ⟨i, hi, -⟩    exact hi rfllemma exists_hypercube_coil_pad_adj (n : ℕ) (hn : 2 ≤ n) (u v : Fin 2 → Bool) :    (simple_graph_hypercube n).Adj (exists_hypercube_coil_pad n hn u) (exists_hypercube_coil_pad n hn v) ↔    (simple_graph_hypercube 2).Adj u v := by  rw [exists_hypercube_coil_hypercube_adj_iff, exists_hypercube_coil_hypercube_adj_iff]  constructor  · rintro ⟨i, hi, huniq⟩    rcases exists_hypercube_coil_pad_diff n hn u v i hi with rfl | rfl    · rw [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0] at hi      refine ⟨0, hi, ?_⟩      intro j hj      fin_cases j      · rfl      · exfalso        have h1 : exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i1 n hn) ≠            exists_hypercube_coil_pad n hn v (exists_hypercube_coil_i1 n hn) := by          rwa [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1]        have := huniq (exists_hypercube_coil_i1 n hn) h1        exact exists_hypercube_coil_i0_ne_i1 n hn this.symm    · rw [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1] at hi      refine ⟨1, hi, ?_⟩      intro j hj      fin_cases j      · exfalso        have h0 : exists_hypercube_coil_pad n hn u (exists_hypercube_coil_i0 n hn) ≠            exists_hypercube_coil_pad n hn v (exists_hypercube_coil_i0 n hn) := by          rwa [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0]        have := huniq (exists_hypercube_coil_i0 n hn) h0        exact exists_hypercube_coil_i0_ne_i1 n hn this      · rfl  · rintro ⟨j, hj, huniq⟩    fin_cases j    · refine ⟨exists_hypercube_coil_i0 n hn, ?_, ?_⟩      · dsimp        rwa [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0]      · intro i hi        rcases exists_hypercube_coil_pad_diff n hn u v i hi with rfl | rfl        · rfl        · exfalso          rw [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1] at hi          have := huniq 1 hi          contradiction    · refine ⟨exists_hypercube_coil_i1 n hn, ?_, ?_⟩      · dsimp        rwa [exists_hypercube_coil_pad_i1, exists_hypercube_coil_pad_i1]      · intro i hi        rcases exists_hypercube_coil_pad_diff n hn u v i hi with rfl | rfl        · exfalso          rw [exists_hypercube_coil_pad_i0, exists_hypercube_coil_pad_i0] at hi          have := huniq 0 hi          contradiction        · rfllemma exists_hypercube_coil_induce_congr {V : Type*} (G : SimpleGraph V) {s t : Set V} (h : s = t)    {W : Type*} {H : SimpleGraph W} (iso : G.induce t ≃g H) : Nonempty (G.induce s ≃g H) := by  cases h  exact ⟨iso⟩/-- Existence of a coil in Q_n for n ≥ 2. -/theorem exists_hypercube_coil (n : ℕ) (hn : 2 ≤ n) :    ∃ S : Finset (Fin n → Bool), hypercube_coil n S := by  let pad := exists_hypercube_coil_pad n hn  have hpad_inj := exists_hypercube_coil_pad_inj n hn  have hpad_adj := exists_hypercube_coil_pad_adj n hn  let S : Finset (Fin n → Bool) := Finset.univ.image pad  use S  dsimp [hypercube_coil]  have hcard : S.card = 4 := by    change (Finset.univ.image pad).card = 4    rw [Finset.card_image_of_injective _ hpad_inj]    rfl  refine ⟨by omega, ?_⟩  have hrange : (S : Set (Fin n → Bool)) = Set.range pad := by    simp [S]  rw [hcard]  have iso1 : ((simple_graph_hypercube n).induce (Set.range pad)) ≃g simple_graph_hypercube 2 :=    (RelIso.mk (Equiv.ofInjective pad hpad_inj) (fun {a b} => hpad_adj a b)).symm  have iso2 : simple_graph_hypercube 2 ≃g SimpleGraph.cycleGraph 4 := exists_hypercube_coil_e_iso  have iso : ((simple_graph_hypercube n).induce (Set.range pad)) ≃g SimpleGraph.cycleGraph 4 :=    RelIso.trans iso1 iso2  exact exists_hypercube_coil_induce_congr (simple_graph_hypercube n) hrange iso
See it in the graphDiscuss this resultChallenge it