bibd_isomorphic_of_block_clique_graph_iso_of_three_le
Recoverability of a BIBD from its modified block-clique graph when the block size k is at least 3: if two BIBDs D₁, D₂ with the same parameters (v, b, r, k, λ), k ≥ 3, have isomorphic block-clique graphs (bibd_block_clique_graph), then the designs are isomorphic (bibd_isomorphic).
Statement
theorem bibd_isomorphic_of_block_clique_graph_iso_of_three_le {X₁ B₁ X₂ B₂ : Type*} {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (hk : 3 ≤ k) (h : Nonempty (bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂)) : bibd_isomorphic D₁ D₂
- Related work
- arXiv:2611.05762, Conjecture 6.30.1 (Sec. 6.30, Algebraic Recoverability), for the construction of Sec. 6.9. The paper leaves this as a conjecture for a suitably restricted class; here the class is block size at least 3.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- bibd_block_clique_graphThe modified block-clique graph K_v^*(D) of a balanced incomplete block design D with parameters (v, b, r, k, λ) is the simple graph on…
- bibd_isomorphicTwo balanced incomplete block designs D₁ and D₂ with parameters (v, b, r, k, λ) are isomorphic if there exist a bijection f between their…
- BIBDA structure BIBD parameterized by types X and B and natural numbers v, b, r, k, lam, with fields: card_points asserting Nat.card X = v;…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 1
- bibd_isomorphic_of_block_clique_graph_isoOP-1148: if two BIBDs D₁, D₂ with the same parameters (v, b, r, k, λ) on finite block sets have isomorphic modified block-clique graphs…
Read back from the Lean
For any types $X_1, B_1, X_2, B_2$ and natural numbers $v, b, r, k, \lambda$, if $D_1$ is a balanced incomplete block design (BIBD) on points $X_1$ and blocks $B_1$ with parameters $(v, b, r, k, \lambda)$, $D_2$ is a BIBD on points $X_2$ and blocks $B_2$ with the same parameters $(v, b, r, k, \lambda)$, $k \ge 3$, and there exists a graph isomorphism between the block-clique graph of $D_1$ and the block-clique graph of $D_2$, then $D_1$ and $D_2$ are isomorphic as block designs.
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
The proof recovers the design isomorphism from a graph isomorphism φ by distinguishing point vertices from block vertices via local triangles. When the block size satisfies k ≥ 3, every block vertex belongs to a clique of size k and hence to a triangle, whereas point vertices belong to no triangles; this forces φ to map point vertices to point vertices and block vertices to block vertices. Since the k vertices of each block form an interconnected clique, their images under φ must all share the same block coordinate, giving well-defined bijections on points and blocks. Finally, incidence between points and blocks corresponds precisely to graph adjacency, so φ preserves incidences in both directions, establishing that the two BIBDs are isomorphic.
No point vertex in the block-clique graph belongs to any triangle.
Suppose for contradiction that a point vertex inl(x) forms a triangle with vertices a and c. In the block-clique graph, there are no edges between point vertices, so both a and c must be block vertices, say (b₁, j₁) and (b₂, j₂). For a and c to be adjacent, they must belong to the same block (b₁ = b₂) with j₁ ≠ j₂. However, since both are adjacent to inl(x), both positions in block b₁ map to the same point x. By the injectivity of the block's point mapping, j₁ = j₂, a contradiction.
theorem bibd_block_clique_graph_point_no_triangle {X B : Type*} {v b r k lam : ℕ} (D : BIBD X B v b r k lam) (x : X) (a c : X ⊕ (B × Fin k)) (h1 : (bibd_block_clique_graph D).Adj (Sum.inl x) a) (h2 : (bibd_block_clique_graph D).Adj (Sum.inl x) c) (h3 : (bibd_block_clique_graph D).Adj a c) : False := by rcases a with y | ⟨b1, j1⟩ · simp [bibd_block_clique_graph] at h1 rcases c with y | ⟨b2, j2⟩ · simp [bibd_block_clique_graph] at h2 simp only [bibd_block_clique_graph] at h1 h2 h3 obtain ⟨rfl, hne⟩ := h3 exact hne (D.block_inj _ (h1.trans h2.symm))
When k ≥ 3, every block vertex belongs to at least one triangle in the block-clique graph.
Given a block vertex inr(β, j), removing j from Fin k yields a set of size k - 1 ≥ 2. Hence by Finset.card_erase_of_mem and Finset.one_lt_card.mp there exist two distinct indices j₁, j₂ distinct from j. The three block vertices (β, j), (β, j₁), and (β, j₂) all belong to the same block and have pairwise distinct indices, so they form a clique of size 3 in the block-clique graph.
uses
Finset.card_erase_of_mem,Finset.one_lt_card.mp,Finset.ne_of_mem_erasetheorem bibd_block_clique_graph_local_triangle {X B : Type*} {v b r k lam : ℕ} (D : BIBD X B v b r k lam) (hk : 3 ≤ k) (β : B) (j : Fin k) : ∃ a c : X ⊕ (B × Fin k), (bibd_block_clique_graph D).Adj (Sum.inr (β, j)) a ∧ (bibd_block_clique_graph D).Adj (Sum.inr (β, j)) c ∧ (bibd_block_clique_graph D).Adj a c := by obtain ⟨j1, j2, h1, h2, h3⟩ : ∃ j1 j2 : Fin k, j ≠ j1 ∧ j ≠ j2 ∧ j1 ≠ j2 := by have hc : 2 < (Finset.univ.erase j : Finset (Fin k)).card + 1 := by simp [Finset.card_erase_of_mem]; omega have hc' : 1 < (Finset.univ.erase j : Finset (Fin k)).card := by omega obtain ⟨p, hp, q, hq, hpq⟩ := Finset.one_lt_card.mp hc' exact ⟨p, q, (Finset.ne_of_mem_erase hp).symm, (Finset.ne_of_mem_erase hq).symm, hpq⟩ refine ⟨Sum.inr (β, j1), Sum.inr (β, j2), ?_, ?_, ?_⟩ · simpa [bibd_block_clique_graph] using h1 · simpa [bibd_block_clique_graph] using h2 · simpa [bibd_block_clique_graph] using h3
Any isomorphism of block-clique graphs maps point vertices to point vertices when k ≥ 3.
Case split on the image φ(inl(x)). If it is a point vertex, the claim holds. If it were a block vertex inr(β, j), it would belong to a triangle in D₂ by bibd_block_clique_graph_local_triangle. Pulling this triangle back via the inverse isomorphism φ⁻¹ (using RelIso.symm_apply_apply) would produce a triangle containing the point vertex inl(x) in D₁, contradicting bibd_block_clique_graph_point_no_triangle.
uses
bibd_block_clique_graph_local_triangle,bibd_block_clique_graph_point_no_triangle,RelIso.symm_apply_applytheorem bibd_block_clique_graph_iso_point {X₁ B₁ X₂ B₂ : Type*} {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (hk : 3 ≤ k) (φ : bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂) (x : X₁) : ∃ y, φ (Sum.inl x) = Sum.inl y := by rcases h : φ (Sum.inl x) with y | ⟨β, j⟩ · exact ⟨y, rfl⟩ · exfalso obtain ⟨a, c, h1, h2, h3⟩ := bibd_block_clique_graph_local_triangle D₂ hk β j rw [← h] at h1 h2 exact bibd_block_clique_graph_point_no_triangle D₁ x (φ.symm a) (φ.symm c) (by have t := φ.symm.map_rel_iff.2 h1; rwa [RelIso.symm_apply_apply] at t) (by have t := φ.symm.map_rel_iff.2 h2; rwa [RelIso.symm_apply_apply] at t) (φ.symm.map_rel_iff.2 h3)
Any isomorphism of block-clique graphs maps block vertices to block vertices when k ≥ 3.
Case split on φ(inr(β, j)). If it were a point vertex inl(y), the local triangle at (β, j) guaranteed by bibd_block_clique_graph_local_triangle would map under φ to a triangle containing inl(y) in D₂, contradicting bibd_block_clique_graph_point_no_triangle. Thus the image must be a block vertex.
uses
bibd_block_clique_graph_local_triangle,bibd_block_clique_graph_point_no_triangletheorem bibd_block_clique_graph_iso_local {X₁ B₁ X₂ B₂ : Type*} {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (hk : 3 ≤ k) (φ : bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂) (β : B₁) (j : Fin k) : ∃ β' j', φ (Sum.inr (β, j)) = Sum.inr (β', j') := by rcases h : φ (Sum.inr (β, j)) with y | ⟨β', j'⟩ · exfalso obtain ⟨a, c, h1, h2, h3⟩ := bibd_block_clique_graph_local_triangle D₁ hk β j exact bibd_block_clique_graph_point_no_triangle D₂ y (φ a) (φ c) (by rw [← h]; exact φ.map_rel_iff.2 h1) (by rw [← h]; exact φ.map_rel_iff.2 h2) (φ.map_rel_iff.2 h3) · exact ⟨β', j', rfl⟩
Extract the graph isomorphism and define point maps and block maps in both directions.
From the assumption that the block-clique graphs are isomorphic, obtain an isomorphism φ. Pick a base index j₀ = 0 in Fin k (valid since k ≥ 3 > 0). Using bibd_block_clique_graph_iso_point in both directions gives point maps f : X₁ → X₂ and f' : X₂ → X₁. Using bibd_block_clique_graph_iso_local in both directions yields block maps g : B₁ → Fin k → B₂ and g' : B₂ → Fin k → B₁ together with index maps κ, κ'.
uses
bibd_block_clique_graph_iso_point,bibd_block_clique_graph_iso_localtheorem bibd_isomorphic_of_block_clique_graph_iso_of_three_le {X₁ B₁ X₂ B₂ : Type*} {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (hk : 3 ≤ k) (h : Nonempty (bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂)) : bibd_isomorphic D₁ D₂ := by obtain ⟨φ⟩ := h let j0 : Fin k := ⟨0, by omega⟩ choose f hf using bibd_block_clique_graph_iso_point D₁ D₂ hk φ choose f' hf' using bibd_block_clique_graph_iso_point D₂ D₁ hk φ.symm choose g κ hg using bibd_block_clique_graph_iso_local D₁ D₂ hk φ choose g' κ' hg' using bibd_block_clique_graph_iso_local D₂ D₁ hk φ.symm
The image block g(β, j) is independent of the index j.
For any block β and index j, if j = j₀ the claim is trivial. If j ≠ j₀, the vertices (β, j) and (β, j₀) are adjacent in the block-clique graph of D₁. Since φ preserves adjacency, their images (g(β, j), κ(β, j)) and (g(β, j₀), κ(β, j₀)) must be adjacent in D₂. In the block-clique graph, two block vertices can only be adjacent if their block coordinates coincide, so g(β, j) = g(β, j₀).
have same : ∀ (β : B₁) (j : Fin k), g β j = g β j0 := by intro β j by_cases e : j = j0 · rw [e] · have hadj : (bibd_block_clique_graph D₁).Adj (Sum.inr (β, j)) (Sum.inr (β, j0)) := by simpa [bibd_block_clique_graph] using e have := φ.map_rel_iff.2 hadj rw [hg, hg] at this simp only [bibd_block_clique_graph] at this exact this.1
The reverse image block g'(β, j) is independent of the index j.
Symmetrically, for any block β ∈ B₂ and index j, if j ≠ j₀ then (β, j) and (β, j₀) are adjacent in D₂, so their images under φ⁻¹ are adjacent in D₁, forcing g'(β, j) = g'(β, j₀).
have same' : ∀ (β : B₂) (j : Fin k), g' β j = g' β j0 := by intro β j by_cases e : j = j0 · rw [e] · have hadj : (bibd_block_clique_graph D₂).Adj (Sum.inr (β, j)) (Sum.inr (β, j0)) := by simpa [bibd_block_clique_graph] using e have := φ.symm.map_rel_iff.2 hadj rw [hg', hg'] at this simp only [bibd_block_clique_graph] at this exact this.1
The point map f is a bijection between X₁ and X₂ with inverse f'.
We construct an equivalence F : X₁ ≃ X₂. For any x ∈ X₁, applying φ⁻¹ to φ(inl(x)) = inl(f(x)) yields inl(x). But by definition of f', φ⁻¹(inl(f(x))) = inl(f'(f(x))). Injectivity of Sum.inl (Sum.inl.inj) gives f'(f(x)) = x. Symmetrically, f(f'(y)) = y.
uses
Sum.inl.injlet F : X₁ ≃ X₂ := { toFun := f, invFun := f' left_inv := by intro x have h1 : φ.symm (Sum.inl (f x)) = Sum.inl x := by rw [← hf]; simp rw [hf' (f x)] at h1 exact Sum.inl.inj h1 right_inv := by intro y have h1 : φ (Sum.inl (f' y)) = Sum.inl y := by rw [← hf']; simp rw [hf (f' y)] at h1 exact Sum.inl.inj h1 }
The block map β ↦ g(β, j₀) is a bijection between B₁ and B₂ with inverse β' ↦ g'(β', j₀).
We construct an equivalence G : B₁ ≃ B₂. For any β ∈ B₁, applying φ⁻¹ to φ(inr(β, j₀)) = inr(g(β, j₀), κ(β, j₀)) returns inr(β, j₀). On the other hand, φ⁻¹ of that vertex produces inr(g'(g(β, j₀), κ(β, j₀)), κ'(...)). Equating the first components using Sum.inr.inj and Prod.mk.inj gives g'(g(β, j₀), κ(β, j₀)) = β. Because g' is independent of the index argument, this simplifies to g'(g(β, j₀), j₀) = β. The right inverse follows symmetrically.
uses
Sum.inr.inj,Prod.mk.injlet G : B₁ ≃ B₂ := { toFun := fun β => g β j0, invFun := fun β => g' β j0 left_inv := by intro β have h1 : φ.symm (Sum.inr (g β j0, κ β j0)) = Sum.inr (β, j0) := by rw [← hg]; simp rw [hg'] at h1 have h2 := (Prod.mk.inj (Sum.inr.inj h1)).1 show g' (g β j0) j0 = β rw [same' _ (κ β j0)] at * exact h2 right_inv := by intro β have h1 : φ (Sum.inr (g' β j0, κ' β j0)) = Sum.inr (β, j0) := by rw [← hg']; simp rw [hg] at h1 have h2 := (Prod.mk.inj (Sum.inr.inj h1)).1 show g (g' β j0) j0 = β rw [same _ (κ' β j0)] at * exact h2 }
Incidence is preserved forward: if x is in block β of D₁, then f(x) is in block G(β) of D₂.
If D₁.block_pts(β, j) = x, then (β, j) is adjacent to inl(x) in the block-clique graph of D₁. Applying φ shows that (g(β, j), κ(β, j)) is adjacent to inl(f(x)) in D₂, which means D₂.block_pts(g(β, j), κ(β, j)) = f(x). Since g(β, j) = g(β, j₀) = G(β), taking j' = κ(β, j) witnesses that f(x) belongs to block G(β).
refine ⟨F, G, fun β x => ?_⟩ show (∃ j, D₁.block_pts β j = x) ↔ ∃ j', D₂.block_pts (g β j0) j' = f x constructor · rintro ⟨j, rfl⟩ have hadj : (bibd_block_clique_graph D₁).Adj (Sum.inr (β, j)) (Sum.inl (D₁.block_pts β j)) := by simp [bibd_block_clique_graph] have := φ.map_rel_iff.2 hadj rw [hg, hf] at this simp only [bibd_block_clique_graph] at this exact ⟨κ β j, by rw [← same β j]; exact this⟩
Incidence is preserved backward: if f(x) is in block G(β) of D₂, then x is in block β of D₁.
If D₂.block_pts(g(β, j₀), j') = f(x), then (g(β, j₀), j') is adjacent to inl(f(x)) in D₂. Applying φ⁻¹ shows their preimages are adjacent in D₁. The preimage of inl(f(x)) is inl(x), while the preimage of (g(β, j₀), j') has block coordinate g'(g(β, j₀), j'). By the index-independence and left-inverse property of the block map (using Sum.inr.inj and Prod.mk.inj), this block coordinate is β. Thus (β, κ'(g(β, j₀), j')) is adjacent to inl(x) in D₁, witnessing that x belongs to block β in D₁.
uses
Sum.inr.inj,Prod.mk.inj· rintro ⟨j', hj'⟩ have hadj : (bibd_block_clique_graph D₂).Adj (Sum.inr (g β j0, j')) (Sum.inl (f x)) := by simpa [bibd_block_clique_graph] using hj' have := φ.symm.map_rel_iff.2 hadj have e1 : φ.symm (Sum.inl (f x)) = Sum.inl x := by rw [← hf]; simp rw [e1, hg'] at this simp only [bibd_block_clique_graph] at this refine ⟨κ' (g β j0) j', ?_⟩ have e2 : g' (g β j0) j' = β := by have h1 : φ.symm (Sum.inr (g β j0, κ β j0)) = Sum.inr (β, j0) := by rw [← hg]; simp rw [hg'] at h1 rw [same' _ j', ← same' _ (κ β j0)] exact (Prod.mk.inj (Sum.inr.inj h1)).1 rw [e2] at this exact this
bibd_block_clique_graph_point_no_triangle- In the block-clique graph of a BIBD, no point vertex belongs to a triangle (three mutually adjacent vertices).
bibd_block_clique_graph_local_triangle- In the block-clique graph of a BIBD with block size k ≥ 3, every block vertex belongs to at least one triangle.
Finset.card_erase_of_mem- Erasing an element from a finite set that contains it decreases the set's cardinality by one.
Finset.one_lt_card.mp- A finite set with cardinality strictly greater than one contains at least two distinct elements.
Finset.ne_of_mem_erase- Any element of a set obtained by erasing an element a is not equal to a.
bibd_block_clique_graph_iso_point- When k ≥ 3, any isomorphism of block-clique graphs maps point vertices to point vertices.
RelIso.symm_apply_apply- Applying the inverse of a relational isomorphism after the isomorphism itself yields the original element.
bibd_block_clique_graph_iso_local- When k ≥ 3, any isomorphism of block-clique graphs maps block vertices to block vertices.
Sum.inl.inj- The canonical injection Sum.inl into a disjoint sum is injective.
Sum.inr.inj- The canonical injection Sum.inr into a disjoint sum is injective.
Prod.mk.inj- If two ordered pairs are equal, their first components are equal and their second components are equal.
- The choice of index j0 = 0 in Fin k is well-defined because k ≥ 3 > 0, and serves as an arbitrary representative to define the bijection on blocks.
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.
theorem bibd_block_clique_graph_point_no_triangle {X B : Type*} {v b r k lam : ℕ} (D : BIBD X B v b r k lam) (x : X) (a c : X ⊕ (B × Fin k)) (h1 : (bibd_block_clique_graph D).Adj (Sum.inl x) a) (h2 : (bibd_block_clique_graph D).Adj (Sum.inl x) c) (h3 : (bibd_block_clique_graph D).Adj a c) : False := by rcases a with y | ⟨b1, j1⟩ · simp [bibd_block_clique_graph] at h1 rcases c with y | ⟨b2, j2⟩ · simp [bibd_block_clique_graph] at h2 simp only [bibd_block_clique_graph] at h1 h2 h3 obtain ⟨rfl, hne⟩ := h3 exact hne (D.block_inj _ (h1.trans h2.symm))theorem bibd_block_clique_graph_local_triangle {X B : Type*} {v b r k lam : ℕ} (D : BIBD X B v b r k lam) (hk : 3 ≤ k) (β : B) (j : Fin k) : ∃ a c : X ⊕ (B × Fin k), (bibd_block_clique_graph D).Adj (Sum.inr (β, j)) a ∧ (bibd_block_clique_graph D).Adj (Sum.inr (β, j)) c ∧ (bibd_block_clique_graph D).Adj a c := by obtain ⟨j1, j2, h1, h2, h3⟩ : ∃ j1 j2 : Fin k, j ≠ j1 ∧ j ≠ j2 ∧ j1 ≠ j2 := by have hc : 2 < (Finset.univ.erase j : Finset (Fin k)).card + 1 := by simp [Finset.card_erase_of_mem]; omega have hc' : 1 < (Finset.univ.erase j : Finset (Fin k)).card := by omega obtain ⟨p, hp, q, hq, hpq⟩ := Finset.one_lt_card.mp hc' exact ⟨p, q, (Finset.ne_of_mem_erase hp).symm, (Finset.ne_of_mem_erase hq).symm, hpq⟩ refine ⟨Sum.inr (β, j1), Sum.inr (β, j2), ?_, ?_, ?_⟩ · simpa [bibd_block_clique_graph] using h1 · simpa [bibd_block_clique_graph] using h2 · simpa [bibd_block_clique_graph] using h3theorem bibd_block_clique_graph_iso_point {X₁ B₁ X₂ B₂ : Type*} {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (hk : 3 ≤ k) (φ : bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂) (x : X₁) : ∃ y, φ (Sum.inl x) = Sum.inl y := by rcases h : φ (Sum.inl x) with y | ⟨β, j⟩ · exact ⟨y, rfl⟩ · exfalso obtain ⟨a, c, h1, h2, h3⟩ := bibd_block_clique_graph_local_triangle D₂ hk β j rw [← h] at h1 h2 exact bibd_block_clique_graph_point_no_triangle D₁ x (φ.symm a) (φ.symm c) (by have t := φ.symm.map_rel_iff.2 h1; rwa [RelIso.symm_apply_apply] at t) (by have t := φ.symm.map_rel_iff.2 h2; rwa [RelIso.symm_apply_apply] at t) (φ.symm.map_rel_iff.2 h3)theorem bibd_block_clique_graph_iso_local {X₁ B₁ X₂ B₂ : Type*} {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (hk : 3 ≤ k) (φ : bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂) (β : B₁) (j : Fin k) : ∃ β' j', φ (Sum.inr (β, j)) = Sum.inr (β', j') := by rcases h : φ (Sum.inr (β, j)) with y | ⟨β', j'⟩ · exfalso obtain ⟨a, c, h1, h2, h3⟩ := bibd_block_clique_graph_local_triangle D₁ hk β j exact bibd_block_clique_graph_point_no_triangle D₂ y (φ a) (φ c) (by rw [← h]; exact φ.map_rel_iff.2 h1) (by rw [← h]; exact φ.map_rel_iff.2 h2) (φ.map_rel_iff.2 h3) · exact ⟨β', j', rfl⟩theorem bibd_isomorphic_of_block_clique_graph_iso_of_three_le {X₁ B₁ X₂ B₂ : Type*} {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (hk : 3 ≤ k) (h : Nonempty (bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂)) : bibd_isomorphic D₁ D₂ := by obtain ⟨φ⟩ := h let j0 : Fin k := ⟨0, by omega⟩ choose f hf using bibd_block_clique_graph_iso_point D₁ D₂ hk φ choose f' hf' using bibd_block_clique_graph_iso_point D₂ D₁ hk φ.symm choose g κ hg using bibd_block_clique_graph_iso_local D₁ D₂ hk φ choose g' κ' hg' using bibd_block_clique_graph_iso_local D₂ D₁ hk φ.symm have same : ∀ (β : B₁) (j : Fin k), g β j = g β j0 := by intro β j by_cases e : j = j0 · rw [e] · have hadj : (bibd_block_clique_graph D₁).Adj (Sum.inr (β, j)) (Sum.inr (β, j0)) := by simpa [bibd_block_clique_graph] using e have := φ.map_rel_iff.2 hadj rw [hg, hg] at this simp only [bibd_block_clique_graph] at this exact this.1 have same' : ∀ (β : B₂) (j : Fin k), g' β j = g' β j0 := by intro β j by_cases e : j = j0 · rw [e] · have hadj : (bibd_block_clique_graph D₂).Adj (Sum.inr (β, j)) (Sum.inr (β, j0)) := by simpa [bibd_block_clique_graph] using e have := φ.symm.map_rel_iff.2 hadj rw [hg', hg'] at this simp only [bibd_block_clique_graph] at this exact this.1 let F : X₁ ≃ X₂ := { toFun := f, invFun := f' left_inv := by intro x have h1 : φ.symm (Sum.inl (f x)) = Sum.inl x := by rw [← hf]; simp rw [hf' (f x)] at h1 exact Sum.inl.inj h1 right_inv := by intro y have h1 : φ (Sum.inl (f' y)) = Sum.inl y := by rw [← hf']; simp rw [hf (f' y)] at h1 exact Sum.inl.inj h1 } let G : B₁ ≃ B₂ := { toFun := fun β => g β j0, invFun := fun β => g' β j0 left_inv := by intro β have h1 : φ.symm (Sum.inr (g β j0, κ β j0)) = Sum.inr (β, j0) := by rw [← hg]; simp rw [hg'] at h1 have h2 := (Prod.mk.inj (Sum.inr.inj h1)).1 show g' (g β j0) j0 = β rw [same' _ (κ β j0)] at * exact h2 right_inv := by intro β have h1 : φ (Sum.inr (g' β j0, κ' β j0)) = Sum.inr (β, j0) := by rw [← hg']; simp rw [hg] at h1 have h2 := (Prod.mk.inj (Sum.inr.inj h1)).1 show g (g' β j0) j0 = β rw [same _ (κ' β j0)] at * exact h2 } refine ⟨F, G, fun β x => ?_⟩ show (∃ j, D₁.block_pts β j = x) ↔ ∃ j', D₂.block_pts (g β j0) j' = f x constructor · rintro ⟨j, rfl⟩ have hadj : (bibd_block_clique_graph D₁).Adj (Sum.inr (β, j)) (Sum.inl (D₁.block_pts β j)) := by simp [bibd_block_clique_graph] have := φ.map_rel_iff.2 hadj rw [hg, hf] at this simp only [bibd_block_clique_graph] at this exact ⟨κ β j, by rw [← same β j]; exact this⟩ · rintro ⟨j', hj'⟩ have hadj : (bibd_block_clique_graph D₂).Adj (Sum.inr (g β j0, j')) (Sum.inl (f x)) := by simpa [bibd_block_clique_graph] using hj' have := φ.symm.map_rel_iff.2 hadj have e1 : φ.symm (Sum.inl (f x)) = Sum.inl x := by rw [← hf]; simp rw [e1, hg'] at this simp only [bibd_block_clique_graph] at this refine ⟨κ' (g β j0) j', ?_⟩ have e2 : g' (g β j0) j' = β := by have h1 : φ.symm (Sum.inr (g β j0, κ β j0)) = Sum.inr (β, j0) := by rw [← hg]; simp rw [hg'] at h1 rw [same' _ j', ← same' _ (κ β j0)] exact (Prod.mk.inj (Sum.inr.inj h1)).1 rw [e2] at this exact this