signed_graph_reconstructible_balanced_mono_pair_fixed
Let G be a connected balanced signed graph on at least seven vertices, with a specified balance partition. Suppose distinct vertices a and b lie in the same part and every automorphism of the underlying graph preserves the unordered pair {a, b}, and suppose a third vertex t, distinct from both a and b, is fixed by every automorphism of the underlying graph. Then G is determined up to signed-graph isomorphism among all finite signed graphs by the multiset obtained by switching the sign of every incident edge at each vertex.
Statement
theorem signed_graph_reconstructible_balanced_mono_pair_fixed {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (hconn : G.graph.Connected) (A B : Finset V) (hbal : G.IsBalancedPartition A B) (a b t : V) (hab : a ≠ b) (hta : t ≠ a) (htb : t ≠ b) (hsize : Fintype.card V ≥ 7) (hmono : a ∈ A ↔ b ∈ A) (hinv : ∀ g : G.graph ≃g G.graph, ∀ x, (x = a ∨ x = b) ↔ (g x = a ∨ g x = b)) (hfixed : ∀ g : G.graph ≃g G.graph, g t = t) : G.IsReconstructible
- Related work
- A structural case of OP-1525, comparing arXiv:2611.13901, Section 4.1.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- SignedGraphA signed graph on vertex type V consists of an underlying simple graph and a signature assigning to each edge a value in {1, -1}.
- SignedGraph.IsBalancedPartitionA pair of disjoint finsets A and B partitioning the vertex set Finset.univ of a signed graph G is a balance partition if every edge whose…
- SignedGraph.IsReconstructibleA signed graph G on a finite type V with decidable equality is reconstructible from its switching deck if every signed graph G' on a…
- signed_graph_reconstructible_balanced_mono_invariantA connected balanced signed graph is reconstructible from its switching deck if its underlying graph has an automorphism-invariant vertex…
- SignedGraph.switchThe switching of a signed graph G at a vertex v is the signed graph with the same underlying graph where the sign of every edge incident…
- SignedGraph.SameDeckTwo signed graphs G1 and G2 on finite types V1 and V2 with decidable equality have the same switching deck if there exists an equivalence…
- SignedGraph.IsIsomorphicTwo signed graphs G1 and G2 are isomorphic if there is an isomorphism f between their underlying simple graphs that preserves the signs of…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For any finite type V with decidable equality, and any signed graph G on V (a simple graph equipped with an edge labeling sgn assigning each edge to either 1 or -1):
If:
1. hconn: the underlying graph G.graph is connected,
2. A and B are finite subsets (Finset V) such that G.IsBalancedPartition A B holds,
3. a, b, and t are vertices in V such that:
- hab: a ≠ b,
- hta: t ≠ a,
- htb: t ≠ b (so a, b, and t are pairwise distinct),
- hsize: the vertex set has cardinality at least 7 (Fintype.card V ≥ 7),
- hmono: a and b are monochromatic with respect to A, i.e., a ∈ A ↔ b ∈ A,
- hinv: every graph automorphism g of G.graph preserves the two-element set {a, b} (i.e., for every g : G.graph ≃g G.graph and every x : V, (x = a ∨ x = b) ↔ (g x = a ∨ g x = b)),
- hfixed: every graph automorphism g of G.graph fixes t (i.e., g t = t),
Then:
G is reconstructible (G.IsReconstructible).
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 translates the signed-graph reconstruction problem into a boolean vertex-coloring problem via deck_color_model, where switching at a vertex corresponds to flipping its boolean indicator color. Because |V| ≥ 7, a counting argument shows that the anchor set {a, b, t} and its pre-image under π contain at most 3 + 3 = 6 vertices, leaving an off-anchor vertex v whose card can be evaluated without any flip indicators at a, b, and t. The combinatorial lemma OP1525PairFixed.reconstruct uses this off-anchor card to establish baseline color agreements, shows that the card at a forces π(a) = g⁻¹(a) ∈ {a, b}, and cancels the flip terms to produce an underlying graph automorphism aligning the balance partitions, which lifts to an isomorphism between G and H.
Any vertex in the pair {a, b} shares the same color under A: A(x) = A(a) for all x ∈ {a, b}.
Assume classical logic. Since A(a) = A(b) by hypothesis hA, case analysis on x = a or x = b confirms that A(x) = A(a) in both cases.
classical have hA' (x : V) (hx : x = a ∨ x = b) : A x = A a := by rcases hx with rfl | rfl <;> simp [hA]
The colors under B satisfy B(a) = B(b), and the relative difference between a and t is preserved: A(a) ⊕ A(t) = B(a) ⊕ B(t).
Evaluate the deck hypothesis at the off-anchor vertex w to obtain an automorphism g₀ and shift d₀. Since g₀ preserves the unordered pair {a, b} and fixes t, and neither w nor π(w) belongs to {a, b, t}, all flip indicators vanish at a, b, and t. Evaluating the card equation at a, b, and t yields A(a) = B(a) ⊕ d₀, A(a) = B(b) ⊕ d₀, and A(t) = B(t) ⊕ d₀. Canceling d₀ gives B(a) = B(b), and combining the equations for a and t shows A(a) ⊕ A(t) = B(a) ⊕ B(t) by boolean case exhaustion.
uses
xor_cancel_commonobtain ⟨g₀, hg₀, d₀, h₀⟩ := hdeck w have hg₀a : g₀ a = a ∨ g₀ a = b := (hinv g₀ hg₀ a).mp (Or.inl rfl) have hg₀b : g₀ b = a ∨ g₀ b = b := (hinv g₀ hg₀ b).mp (Or.inr rfl) have h₀a : A a = xor (B a) d₀ := by have he := h₀ a have hne : g₀ a ≠ w := by rcases hg₀a with h | h <;> rw [h] <;> first | exact Ne.symm hw.1 | exact Ne.symm hw.2.1 simpa [hA' (g₀ a) hg₀a, hne, Ne.symm hπw.1] using he have h₀b : A a = xor (B b) d₀ := by have he := h₀ b have hne : g₀ b ≠ w := by rcases hg₀b with h | h <;> rw [h] <;> first | exact Ne.symm hw.1 | exact Ne.symm hw.2.1 simpa [hA' (g₀ b) hg₀b, hne, Ne.symm hπw.2.1] using he have h₀t : A t = xor (B t) d₀ := by have he := h₀ t simpa [hfixed g₀ hg₀, Ne.symm hw.2.2, Ne.symm hπw.2.2] using he have hB : B a = B b := xor_cancel_common _ _ d₀ (h₀a.symm.trans h₀b) have hrel : xor (A a) (A t) = xor (B a) (B t) := by rw [h₀a, h₀t] cases B a <;> cases B t <;> cases d₀ <;> decide
Under the permutation π, the image of a lies in the invariant pair: π(a) ∈ {a, b}.
Take the deck equation at vertex a, witnessed by automorphism g and shift d. Suppose for contradiction that π(a) ∉ {a, b}. Then the indicator [x = π(a)] is false at both x = a and x = b. Since g preserves {a, b} and A(a) = A(b), the terms A(g(a)) and A(g(b)) both equal A(a), and B(b) = B(a). Evaluating at x = a and x = b would then force [g(a) = a] = [g(b) = a]. But g acts injectively on the two-element set {a, b}, so exactly one of g(a) or g(b) equals a, making one indicator true and the other false, a contradiction.
uses
xor_cancel_common,Bool.xor_comm,False.elimobtain ⟨g, hg, d, heq⟩ := hdeck a have hga : g a = a ∨ g a = b := (hinv g hg a).mp (Or.inl rfl) have hgb : g b = a ∨ g b = b := (hinv g hg b).mp (Or.inr rfl) have hgdistinct : g a ≠ g b := fun he => hab (g.injective he) have hπa : π a = a ∨ π a = b := by by_contra hn push_neg at hn have ha' : xor (A a) (decide (g a = a)) = xor (B a) d := by simpa [hA' (g a) hga, Ne.symm hn.1] using heq a have hb' : xor (A a) (decide (g b = a)) = xor (B a) d := by simpa [hA' (g b) hgb, Ne.symm hn.2, hB] using heq b have hd' : decide (g a = a) = decide (g b = a) := by apply xor_cancel_common _ _ (A a) simpa [Bool.xor_comm] using ha'.trans hb'.symm have hor : g a = a ∨ g b = a := by rcases hga with ha | ha · exact Or.inl ha · rcases hgb with hb | hb · exact Or.inr hb · exact False.elim (hgdistinct (ha.trans hb.symm)) rcases hor with ha | hb · have hb : g b ≠ a := fun h => hgdistinct (ha.trans h.symm) simp [ha, hb] at hd' · have ha : g a ≠ a := fun h => hgdistinct (h.trans hb.symm) simp [ha, hb] at hd'
The colors at t and a align with B up to the shift d: A(t) = B(t) ⊕ d and A(a) = B(a) ⊕ d.
Since π(a) ∈ {a, b} and t ∉ {a, b}, we have π(a) ≠ t. Because g fixes t and t ≠ a, the flip indicators [g(t) = a] and [t = π(a)] both vanish at x = t. Evaluating the card equation for a at x = t gives A(t) = B(t) ⊕ d. Combining this with the relative equality A(a) ⊕ A(t) = B(a) ⊕ B(t) established in Step 2 determines that A(a) = B(a) ⊕ d by boolean simplification.
have hπat : π a ≠ t := by intro h rcases hπa with ha | hb · exact hta (h.symm.trans ha) · exact htb (h.symm.trans hb) have ht : A t = xor (B t) d := by have he := heq t simpa [hfixed g hg, hta, Ne.symm hπat] using he have hAa : A a = xor (B a) d := by cases hA0 : A a <;> cases hAt : A t <;> cases hB0 : B a <;> cases hBt : B t <;> cases hd : d <;> simp_all
The pre-image of a under g coincides with π(a): g⁻¹(a) = π(a).
Let q = g⁻¹(a). Because g preserves {a, b}, q lies in {a, b}, which implies B(q) = B(a). Suppose for contradiction that q ≠ π(a). Evaluating the card equation for a at x = q gives A(g(q)) ⊕ [g(q) = a] = B(q) ⊕ [q = π(a)] ⊕ d. Since g(q) = a, the left flip indicator is true, while the right indicator is false. Substituting A(a) = B(a) ⊕ d and B(q) = B(a) yields (B(a) ⊕ d) ⊕ true = B(a) ⊕ false ⊕ d, which simplifies to true = false, a contradiction. Hence q = π(a).
let q := g.symm a have hgq : g q = a := by simp [q] have hq : q = a ∨ q = b := (hinv g hg q).mpr (Or.inl hgq) have hBq : B q = B a := by rcases hq with h | h · rw [h] · rw [h, ← hB] have hmatch : q = π a := by by_contra hn have he := heq q rw [hgq, hBq, hAa] at he cases hBa : B a <;> cases hd : d <;> simp [hn, hBa, hd] at he
There exist an automorphism g and boolean shift d such that A(g(x)) = B(x) ⊕ d for all x.
Since g⁻¹(a) = π(a), the condition g(x) = a is equivalent to x = π(a) for every x ∈ V. Therefore, the two flip indicators [g(x) = a] and [x = π(a)] in the card equation for a are identical and cancel out via xor_cancel_flip, leaving A(g(x)) = B(x) ⊕ d identically across V.
uses
xor_cancel_fliprefine ⟨g, hg, d, ?_⟩ intro x have he : (g x = a) ↔ x = π a := by constructor · intro hh have : g x = g q := hh.trans hgq.symm exact (g.injective this).trans hmatch · intro hh rw [← hmatch] at hh simpa [hh] using hgq have hx := heq x rw [show decide (g x = a) = decide (x = π a) by simp only [he]] at hx exact xor_cancel_flip _ _ _ _ hx
The reconstruction problem on G is modeled by a boolean coloring F and permutation π whose deck satisfies the card-matching equation.
Unfold the definition of reconstructibility and assume a signed graph H shares the deck of G, witnessed by a card bijection π₀. By deck_color_model with anchor a, there exist a vertex coloring F and permutation π on V such that each card switch corresponds to an underlying graph automorphism matching flipped colorings up to a sign flip, and any global alignment of the colorings implies that G is isomorphic to H.
uses
deck_color_modelclassical unfold SignedGraph.IsReconstructible intro W _ _ H hdeck obtain ⟨π₀, hcards⟩ := hdeck obtain ⟨F, π, hcolors, hlift⟩ := deck_color_model G H hconn A B hbal π₀ hcards a
The automorphism group of G satisfies the invariance hypotheses of reconstruct, preserving {a, b} and fixing t.
Define the predicate P on permutations of V as representing automorphisms of the underlying graph of G. By the theorem's hypotheses, every such automorphism preserves the unordered pair {a, b} and fixes the vertex t. The card-matching conditions from deck_color_model are then rewritten into the exact XOR-flip form required by OP1525PairFixed.reconstruct.
let P : Equiv.Perm V → Prop := fun p => ∃ g : G.graph ≃g G.graph, g.toEquiv = p have hp : ∀ p, P p → ∀ x, (x = a ∨ x = b) ↔ (p x = a ∨ p x = b) := by intro p hp x obtain ⟨g, rfl⟩ := hp exact hinv g x have hfix : ∀ p, P p → p t = t := by intro p hp obtain ⟨g, rfl⟩ := hp exact hfixed g have hmatch : ∀ w, ∃ g, P g ∧ ∃ d : Bool, ∀ x, xor (OP1525Bridge.color A (g x)) (decide (g x = w)) = xor (xor (F x) (decide (x = π w))) d := by intro w obtain ⟨g, d, hg⟩ := hcolors w refine ⟨g.toEquiv, ⟨g, rfl⟩, d, ?_⟩ intro x simpa [flipped] using hg x
There exists a vertex v such that neither v nor π(v) belongs to the anchor set {a, b, t}.
Let anchors = {a, b, t}, which has cardinality at most 3. Define the bad set as the union of anchors and its pre-image under π, which has cardinality at most 3 + 3 = 6. Since |V| ≥ 7, the bad set cannot be all of V, so there exists an element v ∉ bad. This vertex v satisfies v ∉ {a, b, t} and π(v) ∉ {a, b, t}.
uses
congrArg,Finset.card_image_le,Finset.card_le_three,Finset.card_union_le,Finset.card_univ,Finset.mem_union_left,Finset.mem_union_rightlet anchors : Finset V := {a, b, t} let bad : Finset V := anchors ∪ anchors.image π.symm have ha : anchors.card ≤ 3 := Finset.card_le_three have hb : bad.card ≤ 6 := by have hu := Finset.card_union_le anchors (anchors.image π.symm) have hi := Finset.card_image_le (s := anchors) (f := π.symm) dsimp [bad] omega have hv : ∃ v, v ∉ bad := by by_contra h push_neg at h have he : bad = Finset.univ := by ext x simp [h x] have hc := congrArg Finset.card he simp only [Finset.card_univ] at hc omega obtain ⟨v, hv⟩ := hv have hvn : v ≠ a ∧ v ≠ b ∧ v ≠ t := by have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h) simpa [anchors] using h have hvp : π v ≠ a ∧ π v ≠ b ∧ π v ≠ t := by have hnot : v ∉ anchors.image π.symm := by intro h exact hv (Finset.mem_union_right _ h) have hh : π v ∉ anchors := by intro h apply hnot exact Finset.mem_image.mpr ⟨π v, h, by simp⟩ simpa [anchors] using hh
The signed graph G is isomorphic to H, concluding reconstructibility.
Since distinct vertices a and b lie in the same partition set of the balanced graph G, their indicator colors coincide: color(A, a) = color(A, b). Applying OP1525PairFixed.reconstruct with the off-anchor vertex v produces an automorphism g of G and a boolean shift d such that color(A, g(x)) = F(x) ⊕ d for all x. Finally, the lifting lemma hlift from deck_color_model translates this coloring alignment into an isomorphism between G and H.
uses
OP1525PairFixed.reconstructhave hA : OP1525Bridge.color A a = OP1525Bridge.color A b := by simp [OP1525Bridge.color, hmono] obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ := OP1525PairFixed.reconstruct (OP1525Bridge.color A) F P a b t hab hta htb hA hp hfix π v hvn hvp hmatch exact hlift g d hd
Bool.xor_comm- Exclusive or on booleans is commutative: x ⊕ y = y ⊕ x.
congrArg- If x = y, then f(x) = f(y) for any function f.
deck_color_model- For a connected balanced signed graph G, its switching deck can be modeled by a boolean vertex coloring F and permutation π such that card isomorphisms correspond to automorphisms of G matching flipped colorings up to a global boolean negation, and alignment of the colorings implies signed-graph isomorphism.
False.elim- From a contradiction (False), any proposition follows.
Finset.card_image_le- The cardinality of the image of a finite set under any function is at most the cardinality of the domain set.
Finset.card_le_three- The cardinality of a set with at most three listed elements {a, b, c} is at most 3.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities: |s ∪ t| ≤ |s| + |t|.
Finset.card_univ- The cardinality of the universal set univ on a finite type α equals Fintype.card α.
Finset.mem_union_left- If an element belongs to s, it belongs to the union s ∪ t.
Finset.mem_union_right- If an element belongs to t, it belongs to the union s ∪ t.
OP1525PairFixed.reconstruct- If a boolean coloring problem on V has an invariant pair {a, b} of equal color, a fixed third vertex t, and a matching card condition from a deck, with an off-anchor vertex w outside {a, b, t} whose image under π also avoids {a, b, t}, then there exists an automorphism g and a shift d aligning the colorings globally: A(g(x)) = B(x) ⊕ d.
xor_cancel_common- If x ⊕ c = y ⊕ c for booleans x, y, and c, then x = y.
xor_cancel_flip- If a ⊕ d = b ⊕ d ⊕ c for booleans a, b, c, and d, then a = b ⊕ c.
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.
open OP1525MonoPolynamespace OP1525PairFixedvariable {V : Type*} [DecidableEq V]theorem reconstruct (A B : V → Bool) (P : Equiv.Perm V → Prop) (a b t : V) (hab : a ≠ b) (hta : t ≠ a) (htb : t ≠ b) (hA : A a = A b) (hinv : ∀ g, P g → ∀ x, (x = a ∨ x = b) ↔ (g x = a ∨ g x = b)) (hfixed : ∀ g, P g → g t = t) (π : Equiv.Perm V) (w : V) (hw : w ≠ a ∧ w ≠ b ∧ w ≠ t) (hπw : π w ≠ a ∧ π w ≠ b ∧ π w ≠ t) (hdeck : ∀ z, ∃ g, P g ∧ ∃ d : Bool, ∀ x, xor (A (g x)) (decide (g x = z)) = xor (xor (B x) (decide (x = π z))) d) : ∃ g, P g ∧ ∃ d : Bool, ∀ x, A (g x) = xor (B x) d := by classical have hA' (x : V) (hx : x = a ∨ x = b) : A x = A a := by rcases hx with rfl | rfl <;> simp [hA] obtain ⟨g₀, hg₀, d₀, h₀⟩ := hdeck w have hg₀a : g₀ a = a ∨ g₀ a = b := (hinv g₀ hg₀ a).mp (Or.inl rfl) have hg₀b : g₀ b = a ∨ g₀ b = b := (hinv g₀ hg₀ b).mp (Or.inr rfl) have h₀a : A a = xor (B a) d₀ := by have he := h₀ a have hne : g₀ a ≠ w := by rcases hg₀a with h | h <;> rw [h] <;> first | exact Ne.symm hw.1 | exact Ne.symm hw.2.1 simpa [hA' (g₀ a) hg₀a, hne, Ne.symm hπw.1] using he have h₀b : A a = xor (B b) d₀ := by have he := h₀ b have hne : g₀ b ≠ w := by rcases hg₀b with h | h <;> rw [h] <;> first | exact Ne.symm hw.1 | exact Ne.symm hw.2.1 simpa [hA' (g₀ b) hg₀b, hne, Ne.symm hπw.2.1] using he have h₀t : A t = xor (B t) d₀ := by have he := h₀ t simpa [hfixed g₀ hg₀, Ne.symm hw.2.2, Ne.symm hπw.2.2] using he have hB : B a = B b := xor_cancel_common _ _ d₀ (h₀a.symm.trans h₀b) have hrel : xor (A a) (A t) = xor (B a) (B t) := by rw [h₀a, h₀t] cases B a <;> cases B t <;> cases d₀ <;> decide obtain ⟨g, hg, d, heq⟩ := hdeck a have hga : g a = a ∨ g a = b := (hinv g hg a).mp (Or.inl rfl) have hgb : g b = a ∨ g b = b := (hinv g hg b).mp (Or.inr rfl) have hgdistinct : g a ≠ g b := fun he => hab (g.injective he) have hπa : π a = a ∨ π a = b := by by_contra hn push_neg at hn have ha' : xor (A a) (decide (g a = a)) = xor (B a) d := by simpa [hA' (g a) hga, Ne.symm hn.1] using heq a have hb' : xor (A a) (decide (g b = a)) = xor (B a) d := by simpa [hA' (g b) hgb, Ne.symm hn.2, hB] using heq b have hd' : decide (g a = a) = decide (g b = a) := by apply xor_cancel_common _ _ (A a) simpa [Bool.xor_comm] using ha'.trans hb'.symm have hor : g a = a ∨ g b = a := by rcases hga with ha | ha · exact Or.inl ha · rcases hgb with hb | hb · exact Or.inr hb · exact False.elim (hgdistinct (ha.trans hb.symm)) rcases hor with ha | hb · have hb : g b ≠ a := fun h => hgdistinct (ha.trans h.symm) simp [ha, hb] at hd' · have ha : g a ≠ a := fun h => hgdistinct (h.trans hb.symm) simp [ha, hb] at hd' have hπat : π a ≠ t := by intro h rcases hπa with ha | hb · exact hta (h.symm.trans ha) · exact htb (h.symm.trans hb) have ht : A t = xor (B t) d := by have he := heq t simpa [hfixed g hg, hta, Ne.symm hπat] using he have hAa : A a = xor (B a) d := by cases hA0 : A a <;> cases hAt : A t <;> cases hB0 : B a <;> cases hBt : B t <;> cases hd : d <;> simp_all let q := g.symm a have hgq : g q = a := by simp [q] have hq : q = a ∨ q = b := (hinv g hg q).mpr (Or.inl hgq) have hBq : B q = B a := by rcases hq with h | h · rw [h] · rw [h, ← hB] have hmatch : q = π a := by by_contra hn have he := heq q rw [hgq, hBq, hAa] at he cases hBa : B a <;> cases hd : d <;> simp [hn, hBa, hd] at he refine ⟨g, hg, d, ?_⟩ intro x have he : (g x = a) ↔ x = π a := by constructor · intro hh have : g x = g q := hh.trans hgq.symm exact (g.injective this).trans hmatch · intro hh rw [← hmatch] at hh simpa [hh] using hgq have hx := heq x rw [show decide (g x = a) = decide (x = π a) by simp only [he]] at hx exact xor_cancel_flip _ _ _ _ hxend OP1525PairFixedopen OP1525Bridgetheorem signed_graph_reconstructible_balanced_mono_pair_fixed {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (hconn : G.graph.Connected) (A B : Finset V) (hbal : G.IsBalancedPartition A B) (a b t : V) (hab : a ≠ b) (hta : t ≠ a) (htb : t ≠ b) (hsize : Fintype.card V ≥ 7) (hmono : a ∈ A ↔ b ∈ A) (hinv : ∀ g : G.graph ≃g G.graph, ∀ x, (x = a ∨ x = b) ↔ (g x = a ∨ g x = b)) (hfixed : ∀ g : G.graph ≃g G.graph, g t = t) : G.IsReconstructible := by classical unfold SignedGraph.IsReconstructible intro W _ _ H hdeck obtain ⟨π₀, hcards⟩ := hdeck obtain ⟨F, π, hcolors, hlift⟩ := deck_color_model G H hconn A B hbal π₀ hcards a let P : Equiv.Perm V → Prop := fun p => ∃ g : G.graph ≃g G.graph, g.toEquiv = p have hp : ∀ p, P p → ∀ x, (x = a ∨ x = b) ↔ (p x = a ∨ p x = b) := by intro p hp x obtain ⟨g, rfl⟩ := hp exact hinv g x have hfix : ∀ p, P p → p t = t := by intro p hp obtain ⟨g, rfl⟩ := hp exact hfixed g have hmatch : ∀ w, ∃ g, P g ∧ ∃ d : Bool, ∀ x, xor (OP1525Bridge.color A (g x)) (decide (g x = w)) = xor (xor (F x) (decide (x = π w))) d := by intro w obtain ⟨g, d, hg⟩ := hcolors w refine ⟨g.toEquiv, ⟨g, rfl⟩, d, ?_⟩ intro x simpa [flipped] using hg x let anchors : Finset V := {a, b, t} let bad : Finset V := anchors ∪ anchors.image π.symm have ha : anchors.card ≤ 3 := Finset.card_le_three have hb : bad.card ≤ 6 := by have hu := Finset.card_union_le anchors (anchors.image π.symm) have hi := Finset.card_image_le (s := anchors) (f := π.symm) dsimp [bad] omega have hv : ∃ v, v ∉ bad := by by_contra h push_neg at h have he : bad = Finset.univ := by ext x simp [h x] have hc := congrArg Finset.card he simp only [Finset.card_univ] at hc omega obtain ⟨v, hv⟩ := hv have hvn : v ≠ a ∧ v ≠ b ∧ v ≠ t := by have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h) simpa [anchors] using h have hvp : π v ≠ a ∧ π v ≠ b ∧ π v ≠ t := by have hnot : v ∉ anchors.image π.symm := by intro h exact hv (Finset.mem_union_right _ h) have hh : π v ∉ anchors := by intro h apply hnot exact Finset.mem_image.mpr ⟨π v, h, by simp⟩ simpa [anchors] using hh have hA : OP1525Bridge.color A a = OP1525Bridge.color A b := by simp [OP1525Bridge.color, hmono] obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ := OP1525PairFixed.reconstruct (OP1525Bridge.color A) F P a b t hab hta htb hA hp hfix π v hvn hvp hmatch exact hlift g d hd