exists_hypercube_coil
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.
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.
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
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`.
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
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`.
uses
Fin.mk.inj,Nat.zero_ne_onedef 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
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`.
uses
if_pos,if_neg,Ne.symm,exists_hypercube_coil_i0_ne_i1def 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]
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.
uses
Or.inl,Or.inr,exists_hypercube_coil_pad_otherlemma 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
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.
uses
congr_fun,exists_hypercube_coil_pad_i0,exists_hypercube_coil_pad_i1lemma 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
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.
uses
Ne.symm,Or.inllemma 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
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.
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_i1lemma 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
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.
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⟩
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.
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, ?_⟩
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.
uses
RelIso.mk,Equiv.ofInjective,exists_hypercube_coil_e_iso,RelIso.trans,exists_hypercube_coil_induce_congrhave 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
- The equivalence between the 2-cube Q₂ and the 4-cycle C₄ is verified by finite exhaustive computation via `decide`.
- The definition of a coil in Q_n requires an induced cycle of length at least 4; this proof constructs a minimal coil of length exactly 4.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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