AFTD Auto-Formalizing Theoretical Domains

signed_graph_reconstructible_balanced_mono_pair_fixed

theoremverifiedoriginal

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.

  1. 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.

    lines 18–20

      classical
      have hA' (x : V) (hx : x = a ∨ x = b) : A x = A a := by
        rcases hx with rfl | rfl <;> simp [hA]
  2. 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.

    lines 21–38

    uses xor_cancel_common

      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
  3. 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.

    lines 39–63

    uses xor_cancel_common, Bool.xor_comm, False.elim

      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'
  4. 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.

    lines 64–74

      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
  5. 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).

    lines 75–86

      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
  6. 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.

    lines 87–99

    uses xor_cancel_flip

      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 _ _ _ _ hx
  7. 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.

    lines 112–116

    uses deck_color_model

      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
  8. 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.

    lines 117–133

      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
  9. 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}.

    lines 134–163

    uses congrArg, Finset.card_image_le, Finset.card_le_three, Finset.card_union_le, Finset.card_univ, Finset.mem_union_left, Finset.mem_union_right

      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
  10. 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.

    lines 164–168

    uses OP1525PairFixed.reconstruct

      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
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

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
See it in the graphDiscuss this resultChallenge it