AFTD Auto-Formalizing Theoretical Domains

signed_graph_reconstructible_balanced_mono_invariant

theoremverifiedoriginal

A connected balanced signed graph is reconstructible from its switching deck if its underlying graph has an automorphism-invariant vertex set of at least three vertices that lies entirely in one part of a balance partition, with at least two vertices outside the set.

Statement

theorem signed_graph_reconstructible_balanced_mono_invariant {V : Type*}
    [DecidableEq V] [Fintype V] (G : SignedGraph V) (hconn : G.graph.Connected)
    (A B : Finset V) (hbal : G.IsBalancedPartition A B) (S : Finset V)
    (hbig : S.card ≥ 3) (hout : (Finset.univ \ S).card ≥ 2)
    (hmono : S ⊆ A ∨ S ⊆ B)
    (hinvariant : ∀ f : G.graph ≃g G.graph, ∀ x, x ∈ S ↔ f x ∈ S) :
    G.IsReconstructible
Related work
A structural subcase of OP-1525, suggested by the bipartition model in arXiv:2611.13901, Section 4.1.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • op1525_invariant_mono_subset_reconstructLet A and B be Boolean colorings of a set V, and let P be a predicate on permutations of V preserving a subset S. Assume A is constant on…
  • signed_graph_balanced_partition_unique_connectedAny two balance partitions of the same connected signed graph agree up to exchanging their two parts.
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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.IsIsomorphicTwo signed graphs G1 and G2 are isomorphic if there is an isomorphism f between their underlying simple graphs that preserves the signs of…
  • 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.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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 3

Read back from the Lean

Let $V$ be a finite type with decidable equality. Let $G$ be a signed graph on $V$ (consisting of an underlying simple graph G.graph and an edge signing function into $\{-1, 1\}$). Assume: 1. The underlying graph G.graph is connected (G.graph.Connected). 2. $A$ and $B$ are finite subsets of $V$ such that $A$ and $B$ form a balanced partition for $G$ (G.IsBalancedPartition A B). 3. $S$ is a finite subset of $V$ with $|S| \ge 3$. 4. The complement of $S$ in $V$ has size at least 2, i.e., $|V \setminus S| \ge 2$. 5. $S$ is monochromatic with respect to the partition, i.e., $S \subseteq A$ or $S \subseteq B$. 6. $S$ is invariant under all automorphisms of the underlying graph: for every graph isomorphism $f : G.\text{graph} \simeq_g G.\text{graph}$ and every vertex $x \in V$, $x \in S \iff f(x) \in S$. 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

To reconstruct a connected balanced signed graph G from its switching deck, the edge signs of G and any candidate reconstruction H are translated into vertex colorings taking values in the two-element field, where switching a vertex corresponds to flipping its color. When the underlying graph has an automorphism-invariant subset S of at least three vertices lying entirely within one part of a balance partition and at least two vertices outside S, the switching cards at the two exterior vertices force H's coloring to also be monochromatic on S. Evaluating a switching card at a vertex of S then forces the card's automorphism to map that vertex to its deck counterpart, allowing the card-switch indicator terms to be cancelled; this yields an automorphism matching the unswitched colorings up to a global boolean constant, which lifts to an isomorphism between G and H.

  1. Common boolean terms can be cancelled across an XOR equality: x ⊕ c = y ⊕ c implies x = y. automation

    The equality is verified by exhaustive case analysis over all 8 boolean assignments to x, y, and c.

    line 8

      cases x <;> cases y <;> cases c <;> decide
  2. An equality of the form a ⊕ d = (b ⊕ d) ⊕ c reduces to a = b ⊕ c. automation

    The equality is verified by exhaustive case analysis over all 16 boolean assignments to a, b, c, and d.

    line 10

      cases a <;> cases b <;> cases c <;> cases d <;> decide
  3. Given three distinct elements a, b, c in a set S, for any two points u, v there exists an element z in S distinct from both u and v. automation

    If none of a, b, c were distinct from both u and v, then all three would belong to the two-element set {u, v}, which contradicts the assumption that a, b, c are pairwise distinct.

    lines 15–27

      by_cases h : a ≠ u ∧ a ≠ v
      · exact ⟨a, ha, h⟩
      by_cases h' : b ≠ u ∧ b ≠ v
      · exact ⟨b, hb, h'⟩
      by_cases h'' : c ≠ u ∧ c ≠ v
      · exact ⟨c, hc, h''⟩
      exfalso
      push_neg at h h' h''
      have ha' : a = u ∨ a = v := by by_cases ht : a = u <;> aesop
      have hb' : b = u ∨ b = v := by by_cases ht : b = u <;> aesop
      have hc' : c = u ∨ c = v := by by_cases ht : c = u <;> aesop
      rcases ha' with ha' | ha' <;> rcases hb' with hb' | hb' <;>
        rcases hc' with hc' | hc' <;> subst_vars <;> contradiction
  4. If S contains at least three distinct elements and two different single-point flips of a boolean function f (at distinct vertices u and v) are each monochromatic on S, then f itself is monochromatic on S.

    By `fresh_of_three`, there is an element z in S distinct from both u and v. For any x in S, if x = u then x ≠ v, so the flip at v does not affect either x or z, giving f(x) = f(z). If x ≠ u, the flip at u affects neither x nor z, again giving f(x) = f(z). Hence f(x) = f(z) for all x in S, so f is constant on S.

    lines 32–42

    uses fresh_of_three

      obtain ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ := hthree
      obtain ⟨z, hz, hzu, hzv⟩ := fresh_of_three S a b c ha hb hc hab hac hbc u v
      have heq (x : V) (hx : x ∈ S) : f x = f z := by
        by_cases hxu : x = u
        · have hxv : x ≠ v := by simpa [hxu] using huv
          have hh := h2 x hx z hz
          simpa [mono, flip, hxv, hzv] using hh
        · have hh := h1 x hx z hz
          simpa [mono, flip, hxu, hzu] using hh
      intro x hx y hy
      exact (heq x hx).trans (heq y hy).symm
  5. Flipping a boolean function f at a vertex v outside S preserves its constancy on S.

    For any points x, y in S, neither x nor y equals v, so flipping at v modifies neither f(x) nor f(y), leaving them equal.

    lines 46–49

      intro x hx y hy
      have hxv : x ≠ v := fun h => hv (h ▸ hx)
      have hyv : y ≠ v := fun h => hv (h ▸ hy)
      simpa [flip, hxv, hyv] using hf x hx y hy
  6. Monochromaticity on S transfers across a permutation g preserving S when functions differ by a constant boolean shift: F(g(x)) = H(x) ⊕ c implies H is monochromatic on S.

    For any x, y in S, g(x) and g(y) also lie in S, so F(g(x)) = F(g(y)). Substituting H(x) ⊕ c = H(y) ⊕ c and cancelling c using `xor_cancel_common` proves H(x) = H(y).

    lines 54–57

    uses xor_cancel_common

      intro x hx y hy
      apply xor_cancel_common _ _ c
      rw [← heq x, ← heq y]
      exact hF (g x) ((hpres x).mp hx) (g y) ((hpres y).mp hy)
  7. The target boolean function B is monochromatic on the invariant subset S.

    Because u and v lie outside S, flipping A at u or at v leaves A monochromatic on S by `flip_outside_mono`. Transferring this across the deck card automorphisms using `transfer_mono` shows that B flipped at π(u) and B flipped at π(v) are both monochromatic on S. Since π is injective and u ≠ v, π(u) ≠ π(v). Because S has at least three elements, `mono_of_two_flips` implies B is monochromatic on S.

    lines 71–79

    uses flip_outside_mono, transfer_mono, mono_of_two_flips

      have hthree : ∃ a ∈ S, ∃ b ∈ S, ∃ c ∈ S, a ≠ b ∧ a ≠ c ∧ b ≠ c :=
        ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩
      obtain ⟨g1, hg1, d1, heq1⟩ := hdeck u
      obtain ⟨g2, hg2, d2, heq2⟩ := hdeck v
      have hB1 : mono S (flip B (π u)) :=
        transfer_mono S _ _ g1 d1 (hpres g1 hg1) heq1 (flip_outside_mono S A u hA hu)
      have hB2 : mono S (flip B (π v)) :=
        transfer_mono S _ _ g2 d2 (hpres g2 hg2) heq2 (flip_outside_mono S A v hA hv)
      have hB : mono S B := mono_of_two_flips S B (π u) (π v) (fun h => huv (π.injective h)) hthree hB1 hB2
  8. For the deck card at a in S with automorphism g, the preimage q = g⁻¹(a) equals π(a).

    Since g preserves S, q lies in S. If q ≠ π(a), by `fresh_of_three` there exists z in S distinct from both q and π(a). Evaluating the card relation at q gives A(a) ⊕ true = B(q) ⊕ d, while evaluating at z gives A(g(z)) = B(z) ⊕ d. Because A and B are monochromatic on S, A(g(z)) = A(a) and B(z) = B(q), yielding A(a) ⊕ true = A(a), an immediate contradiction. Hence q = π(a).

    lines 80–102

    uses fresh_of_three

      obtain ⟨g, hg, d, heq⟩ := hdeck a
      let q := g.symm a
      have hgq : g q = a := by simp [q]
      have hq : q ∈ S := by
        apply (hpres g hg q).mpr
        simpa [hgq] using ha
      have hmatch : q = π a := by
        by_contra hne
        obtain ⟨z, hz, hzq, hzw⟩ := fresh_of_three S a b c ha hb hc hab hac hbc q (π a)
        have hgzS : g z ∈ S := (hpres g hg z).mp hz
        have hgz : g z ≠ a := by
          intro he
          apply hzq
          apply g.injective
          simpa [hgq] using he
        have hAz : A (g z) = A a := hA (g z) hgzS a ha
        have hBqz : B q = B z := hB q hq z hz
        have hqeq := heq q
        have hzeq := heq z
        simp [flip, hgq, hne, hBqz] at hqeq
        simp [flip, hgz, hzw, hAz] at hzeq
        cases hAa : A a <;> cases hBz : B z <;> cases hd : d <;>
          simp [hAa, hBz, hd] at hqeq hzeq
  9. There exist an automorphism g preserving S and a boolean constant d such that A(g(x)) = B(x) ⊕ d for all x.

    Because g(q) = a and q = π(a), we have g(x) = a if and only if x = π(a). Thus the indicator terms [g(x) = a] and [x = π(a)] in the card equality are identical for every x. Cancelling them via `xor_cancel_flip` yields A(g(x)) = B(x) ⊕ d.

    lines 103–117

    uses xor_cancel_flip

      refine ⟨g, hg, d, ?_⟩
      intro x
      have hEq := heq x
      have hpred : (g x = a) ↔ x = π a := by
        constructor
        · intro h
          have hsame : g x = g q := h.trans hgq.symm
          exact (g.injective hsame).trans hmatch
        · intro h
          subst x
          simpa [hmatch] using hgq
      have hdec : decide (g x = a) = decide (x = π a) := by
        simp only [hpred]
      rw [hdec] at hEq
      exact xor_cancel_flip _ _ _ _ hEq
  10. For booleans a, b, c, d, if a ⊕ b = c ⊕ d then a ⊕ c = b ⊕ d. automation

    Verified by exhaustive case analysis over all 16 boolean assignments.

    line 125

      cases a <;> cases b <;> cases c <;> cases d <;> decide
  11. For booleans a, b, c, if a ⊕ b = c then a = b ⊕ c. automation

    Verified by exhaustive case analysis over all 8 boolean assignments.

    line 128

      cases a <;> cases b <;> cases c <;> decide
  12. On a connected graph, if two boolean vertex labelings a, b have identical edge differences a(u) ⊕ a(v) = b(u) ⊕ b(v) on all edges, they differ by a uniform boolean constant.

    By `bool_xor_square`, the edge difference condition rearranges to a(u) ⊕ b(u) = a(v) ⊕ b(v) across every edge. In a connected graph, any vertex x is reachable from a fixed root r by a path; induction along the path shows that a(x) ⊕ b(x) = a(r) ⊕ b(r). Solving for a(x) via `bool_xor_solve` gives a(x) = b(x) ⊕ c with c = a(r) ⊕ b(r).

    lines 133–144

    uses bool_xor_square, bool_xor_solve

      letI : Nonempty V := hc.nonempty
      let r : V := Classical.choice inferInstance
      have hedge (u v : V) (h : G.Adj u v) : xor (a u) (b u) = xor (a v) (b v) :=
        bool_xor_square _ _ _ _ (he u v h)
      have hpath : ∀ x, Relation.ReflTransGen G.Adj r x → xor (a r) (b r) = xor (a x) (b x) := by
        intro x p
        induction p with
        | refl => rfl
        | tail _ h ih => exact ih.trans (hedge _ _ h)
      refine ⟨xor (a r) (b r), ?_⟩
      intro x
      exact bool_xor_solve _ _ _ (hpath x ((SimpleGraph.reachable_iff_reflTransGen r x).mp (hc r x))).symm
  13. In a balanced signed graph with partition (A, B), edge signs are given by sign(color(A, u) ⊕ color(A, v)).

    Edges within A or within B have sign +1 (corresponding to color(A, u) ⊕ color(A, v) = false), while edges connecting A and B have sign -1 (corresponding to true). A case split on whether the endpoints belong to A confirms the formula.

    lines 153–160

      have hB (x : V) (hx : x ∉ A) : x ∈ B := by
        have hall : x ∈ A ∪ B := by rw [hbal.1]; exact Finset.mem_univ x
        exact (Finset.mem_union.mp hall).resolve_left hx
      by_cases hu : u ∈ A <;> by_cases hv : v ∈ A
      · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).1 (Or.inl ⟨hu, hv⟩)
      · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).2 (Or.inl ⟨hu, hB v hv⟩)
      · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).2 (Or.inr ⟨hB u hu, hv⟩)
      · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).1 (Or.inr ⟨hB u hu, hB v hv⟩)
  14. The sign function mapping false to 1 and true to -1 is injective. automation

    Follows from 1 ≠ -1 in the integers.

    line 167

      cases a <;> cases b <;> simp [sign] at h ⊢
  15. Switching a balanced signed graph at vertex w corresponds to flipping the vertex coloring at w.

    Switching at w negates the sign of an edge uv if and only if w is one of the endpoints. By `balanced_sign`, the unswitched sign is determined by color(A, u) ⊕ color(A, v); flipping the color of w flips this XOR exactly when w ∈ {u, v}, which negates the sign.

    lines 173–184

    uses balanced_sign

      change (if w ∈ s(u, v) then -G.sgn ⟨s(u, v), h⟩ else G.sgn ⟨s(u, v), h⟩) = _
      rw [balanced_sign G A B hbal u v h]
      have hne : u ≠ v := G.graph.ne_of_adj h
      by_cases hu : u = w <;> by_cases hv : v = w
      · exact False.elim (hne (hu.trans hv.symm))
      · subst u
        cases h1 : color A w <;> cases h2 : color A v <;>
          simp [Sym2.mem_iff, hv, Ne.symm hv, sign, flipped, h1, h2]
      · subst v
        cases h1 : color A u <;> cases h2 : color A w <;>
          simp [Sym2.mem_iff, hu, Ne.symm hu, sign, flipped, h1, h2]
      · simp [Sym2.mem_iff, hu, hv, Ne.symm hu, Ne.symm hv, flipped]
  16. Flipping the first argument in an XOR negates the corresponding sign: sign((a ⊕ true) ⊕ b) = -sign(a ⊕ b). automation

    Verified by exhaustive case analysis on the boolean values of a and b.

    line 191

      cases a <;> cases b <;> decide
  17. Flipping the second argument in an XOR negates the corresponding sign: sign(a ⊕ (b ⊕ true)) = -sign(a ⊕ b). automation

    Verified by exhaustive case analysis on the boolean values of a and b.

    line 193

      cases a <;> cases b <;> decide
  18. If the edge signs of a signed graph switched at w are represented under an isomorphism f by a coloring F, then the edge signs of the unswitched graph are represented by F flipped at f⁻¹(w).

    The unswitched graph is recovered by switching back at w. Edges containing w correspond under f to edges containing f⁻¹(w); using `sign_flip_left` and `sign_flip_right`, flipping F at f⁻¹(w) negates the sign on incident edges and preserves all others.

    lines 202–234

    uses sign_flip_left, sign_flip_right

      intro u v h
      have hne : u ≠ v := G.ne_of_adj h
      have hm : w ∈ s(f u, f v) ↔ u = f.symm w ∨ v = f.symm w := by
        have hf (z : V) : w = f z ↔ z = f.symm w := by
          constructor
          · intro h
            apply f.injective
            simpa using h.symm
          · intro h
            subst z
            simp
        simp only [Sym2.mem_iff, hf]
      have hh := hcard u v h
      change (if w ∈ s(f u, f v) then -H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩
        else H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩) = _ at hh
      by_cases hu : u = f.symm w <;> by_cases hv : v = f.symm w
      · exact False.elim (hne (hu.trans hv.symm))
      · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inl hu)
        simp [hw] at hh
        have hdu : decide (u = f.symm w) = true := by simp [hu]
        have hdv : decide (v = f.symm w) = false := by simp [hv]
        simp only [flipped, hdu, hdv, Bool.xor_false]
        rw [sign_flip_left]
        linarith
      · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inr hv)
        simp [hw] at hh
        have hdu : decide (u = f.symm w) = false := by simp [hu]
        have hdv : decide (v = f.symm w) = true := by simp [hv]
        simp only [flipped, hdu, hdv, Bool.xor_false]
        rw [sign_flip_right]
        linarith
      · have hw : w ∉ s(f u, f v) := fun hh' => (hm.mp hh').elim hu hv
        simpa [hw, flipped, hu, hv] using hh
  19. If the edge signs of a signed graph are represented under an isomorphism f by F, then switching at w yields edge signs represented by F flipped at f⁻¹(w).

    Switching at w negates the sign of incident edges, which under f match edges incident to f⁻¹(w). By `sign_flip_left` and `sign_flip_right`, this matches the XOR difference of F flipped at f⁻¹(w).

    lines 247–275

    uses sign_flip_left, sign_flip_right

      intro u v h
      have hne : u ≠ v := G.ne_of_adj h
      have hm : w ∈ s(f u, f v) ↔ u = f.symm w ∨ v = f.symm w := by
        have hf (z : V) : w = f z ↔ z = f.symm w := by
          constructor
          · intro hz
            apply f.injective
            simpa using hz.symm
          · intro hz
            subst z
            simp
        simp only [Sym2.mem_iff, hf]
      change (if w ∈ s(f u, f v) then -H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩
        else H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩) = _
      rw [hrep u v h]
      by_cases hu : u = f.symm w <;> by_cases hv : v = f.symm w
      · exact False.elim (hne (hu.trans hv.symm))
      · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inl hu)
        have hdu : decide (u = f.symm w) = true := by simp [hu]
        have hdv : decide (v = f.symm w) = false := by simp [hv]
        simp only [hw, ↓reduceIte, flipped, hdu, hdv, Bool.xor_false]
        exact (sign_flip_left _ _).symm
      · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inr hv)
        have hdu : decide (u = f.symm w) = false := by simp [hu]
        have hdv : decide (v = f.symm w) = true := by simp [hv]
        simp only [hw, ↓reduceIte, flipped, hdu, hdv, Bool.xor_false]
        exact (sign_flip_right _ _).symm
      · have hw : w ∉ s(f u, f v) := fun hh => (hm.mp hh).elim hu hv
        simp [hw, flipped, hu, hv]
  20. For booleans a, b, c, (a ⊕ c) ⊕ (b ⊕ c) = a ⊕ b. automation

    Verified by exhaustive case analysis on a, b, and c.

    line 282

      cases a <;> cases b <;> cases c <;> decide
  21. A reference coloring F on V and a permutation π represent the unswitched signs of H pulled back via an isomorphism from the card at a.

    From the isomorphism G.switch(a) ≅ H.switch(π₀(a)), the switched signs of G correspond to color(A) flipped at a by `switched_sign`. Switching back at π₀(a) using `from_switched_iso` yields a coloring F representing the unswitched signs of H, with permutation π = π₀ ∘ f⁻¹.

    lines 293–305

    uses switched_sign, from_switched_iso

      classical
      obtain ⟨f, hf⟩ := hcards a
      let F0 : V → Bool := flipped (color A) a
      let F : V → Bool := flipped F0 (f.symm (π0 a))
      have hcard0 : ∀ u v (h : G.graph.Adj u v),
          (H.switch (π0 a)).sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ = sign (xor (F0 u) (F0 v)) := by
        intro u v h
        rw [hf u v h]
        exact switched_sign G A B hbal a u v h
      have hrep : ∀ u v (h : G.graph.Adj u v),
          H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ = sign (xor (F u) (F v)) :=
        from_switched_iso H G.graph f (π0 a) F0 hcard0
      let π : Equiv.Perm V := π0.trans f.toEquiv.symm
  22. For each vertex v, there is an automorphism g of G and a constant c relating the flipped colorings of G and H.

    Isomorphism of the card at v to H.switch(π₀(v)) gives an automorphism g = f ∘ f_v⁻¹ of G. By `sign_injective`, `switched_sign`, and `to_switched_iso`, the edge differences of color(A) flipped at v along g match those of F flipped at π(v). Since G is connected, `connected_labels` implies the two vertex labelings differ by a constant boolean c.

    lines 306–331

    uses sign_injective, switched_sign, to_switched_iso, connected_labels

      refine ⟨F, π, ?_, ?_⟩
      · intro v
        obtain ⟨fv, hfv⟩ := hcards v
        let g : G.graph ≃g G.graph := f.trans fv.symm
        have he : ∀ u w, G.graph.Adj u w →
            xor (flipped (color A) v (g u)) (flipped (color A) v (g w)) =
              xor (flipped F (π v) u) (flipped F (π v) w) := by
          intro u w h
          apply sign_injective
          calc
            sign (xor (flipped (color A) v (g u)) (flipped (color A) v (g w))) =
                (G.switch v).sgn ⟨s(g u, g w), g.map_adj_iff.mpr h⟩ :=
              (switched_sign G A B hbal v (g u) (g w) (g.map_adj_iff.mpr h)).symm
            _ = (H.switch (π0 v)).sgn ⟨s(f u, f w), f.map_adj_iff.mpr h⟩ := by
              have hp := (hfv (g u) (g w) (g.map_adj_iff.mpr h)).symm
              have hcomp (x : V) : fv (g x) = f x := by
                change fv (fv.symm (f x)) = f x
                exact fv.apply_symm_apply _
              simpa only [hcomp] using hp
            _ = sign (xor (flipped F (π v) u) (flipped F (π v) w)) := by
              have hp : π v = f.symm (π0 v) := rfl
              rw [hp]
              exact to_switched_iso H G.graph f (π0 v) F hrep u w h
        obtain ⟨c, hc⟩ := connected_labels G.graph hconn (fun x => flipped (color A) v (g x))
          (flipped F (π v)) he
        exact ⟨g, c, hc⟩
  23. If an automorphism g and constant c satisfy color(A, g(x)) = F(x) ⊕ c for all x, then G is isomorphic to H.

    The composition z = f ∘ g⁻¹ is an isomorphism of the underlying graphs. On every edge, the constant c cancels out when XORing endpoint colors by `xor_common`, so the signs match those of G by `balanced_sign`.

    lines 332–344

    uses xor_common, balanced_sign

      · intro g c hc
        let z : G.graph ≃g H.graph := g.symm.trans f
        refine ⟨z, ?_⟩
        intro u v h
        have hu : color A u = xor (F (g.symm u)) c := by simpa using hc (g.symm u)
        have hv : color A v = xor (F (g.symm v)) c := by simpa using hc (g.symm v)
        calc
          H.sgn ⟨s(z u, z v), z.map_adj_iff.mpr h⟩ =
              sign (xor (F (g.symm u)) (F (g.symm v))) := by
            change H.sgn ⟨s(f (g.symm u), f (g.symm v)), _⟩ = _
            exact hrep (g.symm u) (g.symm v) (g.symm.map_adj_iff.mpr h)
          _ = sign (xor (color A u) (color A v)) := by rw [hu, hv, xor_common]
          _ = G.sgn ⟨s(u, v), h⟩ := (balanced_sign G A B hbal u v h).symm
  24. The invariant set S contains three distinct vertices, the complement V \ S contains two distinct vertices, and S is monochromatic under color(A).

    The size bounds |S| ≥ 3 and |V \ S| ≥ 2 yield witnesses a, b, c in S and u, v not in S. If S ⊆ A, every vertex of S has color(A) = true; if S ⊆ B, the disjointness of A and B implies no vertex of S is in A, so color(A) = false. In both cases color(A) is constant on S.

    lines 361–375

      classical
      obtain ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ :=
        Finset.two_lt_card.mp (show 2 < S.card by omega)
      obtain ⟨u, hu, v, hv, huv⟩ :=
        Finset.one_lt_card.mp (show 1 < (Finset.univ \ S).card by omega)
      have huS : u ∉ S := (Finset.mem_sdiff.mp hu).2
      have hvS : v ∉ S := (Finset.mem_sdiff.mp hv).2
      have hA : ∀ (x : V), x ∈ S → ∀ (y : V), y ∈ S → OP1525Bridge.color A x = OP1525Bridge.color A y := by
        rcases hmono with h | h
        · intro x hx y hy
          simp [OP1525Bridge.color, h hx, h hy]
        · intro x hx y hy
          have hnotx : x ∉ A := fun hxA => (Finset.disjoint_left.mp hbal.2.1) hxA (h hx)
          have hnoty : y ∉ A := fun hyA => (Finset.disjoint_left.mp hbal.2.1) hyA (h hy)
          simp [OP1525Bridge.color, hnotx, hnoty]
  25. The switching deck hypotheses provide the data required for monochromatic reconstruction: an automorphism predicate preserving S and card flip equations for every vertex.

    Assuming H has the same switching deck as G, `deck_color_model` provides a coloring F, permutation π, and card relations. The predicate P of being an automorphism of G preserves S by the invariance hypothesis, and each card relation yields an automorphism g and constant d matching the flipped colorings.

    lines 376–392

    uses deck_color_model

      unfold SignedGraph.IsReconstructible
      intro W _ _ H hdeck
      obtain ⟨π0, hcards⟩ := hdeck
      obtain ⟨F, π, hcolors, hlift⟩ := deck_color_model G H hconn A B hbal π0 hcards a
      let P : Equiv.Perm V → Prop := fun p => ∃ g : G.graph ≃g G.graph, g.toEquiv = p
      have hpres : ∀ p, P p → ∀ x, x ∈ (S : Set V) ↔ p x ∈ (S : Set V) := by
        intro p hp x
        obtain ⟨g, rfl⟩ := hp
        exact hinvariant g x
      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
  26. G is isomorphic to H, concluding that G is reconstructible from its switching deck.

    Applying `OP1525MonoPoly.reconstruct_of_invariant_monochrome` yields an automorphism g and boolean constant d such that color(A, g(x)) = F(x) ⊕ d for all x. Lifting this relation through `deck_color_model` produces an isomorphism of signed graphs between G and H.

    lines 393–396

    uses OP1525MonoPoly.reconstruct_of_invariant_monochrome

      obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ :=
        OP1525MonoPoly.reconstruct_of_invariant_monochrome (OP1525Bridge.color A) F P (S : Set V)
          a b c ha hb hc hab hac hbc u v huS hvS huv hA hpres π hmatch
      exact hlift g d hd
fresh_of_three
In any set with at least three pairwise distinct elements, for any two chosen points, there exists an element of the set distinct from both.
xor_cancel_common
For booleans x, y, c, if x ⊕ c = y ⊕ c, then x = y.
transfer_mono
If a boolean function F is constant on S and a permutation g preserves S such that F(g(x)) = H(x) ⊕ c for all x, then H is also constant on S.
flip_outside_mono
Flipping a boolean function at a point outside S preserves its constancy on S.
mono_of_two_flips
If S has at least three elements and two single-point flips of f at distinct vertices are each constant on S, then f itself is constant on S.
xor_cancel_flip
For booleans a, b, c, d, if a ⊕ d = (b ⊕ d) ⊕ c, then a = b ⊕ c.
bool_xor_square
For booleans a, b, c, d, if a ⊕ b = c ⊕ d, then a ⊕ c = b ⊕ d.
bool_xor_solve
For booleans a, b, c, if a ⊕ b = c, then a = b ⊕ c.
balanced_sign
In a balanced signed graph with balance partition (A, B), the sign of an edge uv is -1 if its endpoints lie in different parts and +1 if in the same part, given by sign(color(A, u) ⊕ color(A, v)).
sign_flip_left
Flipping the first operand in an XOR negates the corresponding sign: sign((a ⊕ true) ⊕ b) = -sign(a ⊕ b).
sign_flip_right
Flipping the second operand in an XOR negates the corresponding sign: sign(a ⊕ (b ⊕ true)) = -sign(a ⊕ b).
switched_sign
Switching a balanced signed graph at vertex w yields edge signs given by sign(flipped(color(A), w, u) ⊕ flipped(color(A), w, v)).
from_switched_iso
If the edge signs of a signed graph switched at w are represented under an isomorphism by a vertex coloring F, then the edge signs of the original unswitched graph are represented by F flipped at the preimage of w.
sign_injective
The function mapping false to 1 and true to -1 is an injective map from Bool to ℤ.
to_switched_iso
If the edge signs of a signed graph are represented under an isomorphism by a vertex coloring F, then switching at w yields edge signs represented by F flipped at the preimage of w.
connected_labels
On a connected graph, any two vertex labelings whose endpoint XOR differences agree on all edges differ by a uniform boolean constant.
xor_common
For booleans a, b, c, (a ⊕ c) ⊕ (b ⊕ c) = a ⊕ b.
deck_color_model
If all switching cards of G are isomorphic to those of H via a bijection π₀, then H's edge signs can be represented by a coloring F on V and a permutation π such that each card isomorphism induces an automorphism matching the flipped colorings up to a constant, and matching the colorings directly implies G ≅ H.
OP1525MonoPoly.reconstruct_of_invariant_monochrome
If an invariant subset S of size at least 3 is monochromatic under A, with at least two vertices outside S, and every card flip of A matches a card flip of B under an automorphism up to a constant, then A matches B under some automorphism up to a constant.

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

Lean’s trace was cut to the first 400 of 444 tactics.

namespace OP1525MonoPolyvariable {V : Type*} [DecidableEq V]def flip (f : V → Bool) (v x : V) : Bool := xor (f x) (decide (x = v))def mono (S : Set V) (f : V → Bool) : Prop := ∀ x ∈ S, ∀ y ∈ S, f x = f ylemma xor_cancel_common (x y c : Bool) : xor x c = xor y c → x = y := by  cases x <;> cases y <;> cases c <;> decidelemma xor_cancel_flip (a b c d : Bool) : xor a d = xor (xor b d) c → a = xor b c := by  cases a <;> cases b <;> cases c <;> cases d <;> decidelemma fresh_of_three (S : Set V) (a b c : V) (ha : a ∈ S) (hb : b ∈ S) (hc : c ∈ S)    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (u v : V) :    ∃ z ∈ S, z ≠ u ∧ z ≠ v := by  by_cases h : a ≠ u ∧ a ≠ v  · exact ⟨a, ha, h⟩  by_cases h' : b ≠ u ∧ b ≠ v  · exact ⟨b, hb, h'⟩  by_cases h'' : c ≠ u ∧ c ≠ v  · exact ⟨c, hc, h''⟩  exfalso  push_neg at h h' h''  have ha' : a = u ∨ a = v := by by_cases ht : a = u <;> aesop  have hb' : b = u ∨ b = v := by by_cases ht : b = u <;> aesop  have hc' : c = u ∨ c = v := by by_cases ht : c = u <;> aesop  rcases ha' with ha' | ha' <;> rcases hb' with hb' | hb' <;>    rcases hc' with hc' | hc' <;> subst_vars <;> contradictionlemma mono_of_two_flips (S : Set V) (f : V → Bool) (u v : V) (huv : u ≠ v)    (hthree : ∃ a ∈ S, ∃ b ∈ S, ∃ c ∈ S, a ≠ b ∧ a ≠ c ∧ b ≠ c)    (h1 : mono S (flip f u)) (h2 : mono S (flip f v)) : mono S f := by  obtain ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ := hthree  obtain ⟨z, hz, hzu, hzv⟩ := fresh_of_three S a b c ha hb hc hab hac hbc u v  have heq (x : V) (hx : x ∈ S) : f x = f z := by    by_cases hxu : x = u    · have hxv : x ≠ v := by simpa [hxu] using huv      have hh := h2 x hx z hz      simpa [mono, flip, hxv, hzv] using hh    · have hh := h1 x hx z hz      simpa [mono, flip, hxu, hzu] using hh  intro x hx y hy  exact (heq x hx).trans (heq y hy).symmlemma flip_outside_mono (S : Set V) (f : V → Bool) (v : V)    (hf : mono S f) (hv : v ∉ S) : mono S (flip f v) := by  intro x hx y hy  have hxv : x ≠ v := fun h => hv (h ▸ hx)  have hyv : y ≠ v := fun h => hv (h ▸ hy)  simpa [flip, hxv, hyv] using hf x hx y hylemma transfer_mono (S : Set V) (F H : V → Bool) (g : Equiv.Perm V) (c : Bool)    (hpres : ∀ x, x ∈ S ↔ g x ∈ S)    (heq : ∀ x, F (g x) = xor (H x) c) (hF : mono S F) : mono S H := by  intro x hx y hy  apply xor_cancel_common _ _ c  rw [← heq x, ← heq y]  exact hF (g x) ((hpres x).mp hx) (g y) ((hpres y).mp hy)theorem reconstruct_of_invariant_monochrome    (A B : V → Bool) (P : Equiv.Perm V → Prop) (S : Set V)    (a b c : V) (ha : a ∈ S) (hb : b ∈ S) (hc : c ∈ S)    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)    (u v : V) (hu : u ∉ S) (hv : v ∉ S) (huv : u ≠ v)    (hA : ∀ x ∈ S, ∀ y ∈ S, A x = A y)    (hpres : ∀ g, P g → ∀ x, x ∈ S ↔ g x ∈ S)    (π : Equiv.Perm V)    (hdeck : ∀ w, ∃ g, P g ∧ ∃ d : Bool, ∀ x,      xor (A (g x)) (decide (g x = w)) =        xor (xor (B x) (decide (x = π w))) d) :    ∃ g, P g ∧ ∃ d : Bool, ∀ x, A (g x) = xor (B x) d := by  have hthree : ∃ a ∈ S, ∃ b ∈ S, ∃ c ∈ S, a ≠ b ∧ a ≠ c ∧ b ≠ c :=    ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩  obtain ⟨g1, hg1, d1, heq1⟩ := hdeck u  obtain ⟨g2, hg2, d2, heq2⟩ := hdeck v  have hB1 : mono S (flip B (π u)) :=    transfer_mono S _ _ g1 d1 (hpres g1 hg1) heq1 (flip_outside_mono S A u hA hu)  have hB2 : mono S (flip B (π v)) :=    transfer_mono S _ _ g2 d2 (hpres g2 hg2) heq2 (flip_outside_mono S A v hA hv)  have hB : mono S B := mono_of_two_flips S B (π u) (π v) (fun h => huv (π.injective h)) hthree hB1 hB2  obtain ⟨g, hg, d, heq⟩ := hdeck a  let q := g.symm a  have hgq : g q = a := by simp [q]  have hq : q ∈ S := by    apply (hpres g hg q).mpr    simpa [hgq] using ha  have hmatch : q = π a := by    by_contra hne    obtain ⟨z, hz, hzq, hzw⟩ := fresh_of_three S a b c ha hb hc hab hac hbc q (π a)    have hgzS : g z ∈ S := (hpres g hg z).mp hz    have hgz : g z ≠ a := by      intro he      apply hzq      apply g.injective      simpa [hgq] using he    have hAz : A (g z) = A a := hA (g z) hgzS a ha    have hBqz : B q = B z := hB q hq z hz    have hqeq := heq q    have hzeq := heq z    simp [flip, hgq, hne, hBqz] at hqeq    simp [flip, hgz, hzw, hAz] at hzeq    cases hAa : A a <;> cases hBz : B z <;> cases hd : d <;>      simp [hAa, hBz, hd] at hqeq hzeq  refine ⟨g, hg, d, ?_⟩  intro x  have hEq := heq x  have hpred : (g x = a) ↔ x = π a := by    constructor    · intro h      have hsame : g x = g q := h.trans hgq.symm      exact (g.injective hsame).trans hmatch    · intro h      subst x      simpa [hmatch] using hgq  have hdec : decide (g x = a) = decide (x = π a) := by    simp only [hpred]  rw [hdec] at hEq  exact xor_cancel_flip _ _ _ _ hEqend OP1525MonoPolynamespace OP1525Bridgelemma bool_xor_square (a b c d : Bool) : xor a b = xor c d → xor a c = xor b d := by  cases a <;> cases b <;> cases c <;> cases d <;> decidelemma bool_xor_solve (a b c : Bool) : xor a b = c → a = xor b c := by  cases a <;> cases b <;> cases c <;> decidelemma connected_labels {V : Type*} (G : SimpleGraph V) (hc : G.Connected) (a b : V → Bool)    (he : ∀ u v, G.Adj u v → xor (a u) (a v) = xor (b u) (b v)) :    ∃ c : Bool, ∀ x, a x = xor (b x) c := by  letI : Nonempty V := hc.nonempty  let r : V := Classical.choice inferInstance  have hedge (u v : V) (h : G.Adj u v) : xor (a u) (b u) = xor (a v) (b v) :=    bool_xor_square _ _ _ _ (he u v h)  have hpath : ∀ x, Relation.ReflTransGen G.Adj r x → xor (a r) (b r) = xor (a x) (b x) := by    intro x p    induction p with    | refl => rfl    | tail _ h ih => exact ih.trans (hedge _ _ h)  refine ⟨xor (a r) (b r), ?_⟩  intro x  exact bool_xor_solve _ _ _ (hpath x ((SimpleGraph.reachable_iff_reflTransGen r x).mp (hc r x))).symmdef color {V : Type*} [DecidableEq V] (A : Finset V) (v : V) : Bool := decide (v ∈ A)def sign (p : Bool) : ℤ := if p then -1 else 1lemma balanced_sign {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V)    (A B : Finset V) (hbal : G.IsBalancedPartition A B)    (u v : V) (h : G.graph.Adj u v) :    G.sgn ⟨s(u, v), h⟩ = sign (xor (color A u) (color A v)) := by  have hB (x : V) (hx : x ∉ A) : x ∈ B := by    have hall : x ∈ A ∪ B := by rw [hbal.1]; exact Finset.mem_univ x    exact (Finset.mem_union.mp hall).resolve_left hx  by_cases hu : u ∈ A <;> by_cases hv : v ∈ A  · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).1 (Or.inl ⟨hu, hv⟩)  · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).2 (Or.inl ⟨hu, hB v hv⟩)  · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).2 (Or.inr ⟨hB u hu, hv⟩)  · simpa [sign, color, hu, hv] using (hbal.2.2 u v h).1 (Or.inr ⟨hB u hu, hB v hv⟩)def flipped {V : Type*} [DecidableEq V] (f : V → Bool) (w x : V) : Bool :=  xor (f x) (decide (x = w))lemma sign_injective {a b : Bool} (h : sign a = sign b) : a = b := by  cases a <;> cases b <;> simp [sign] at h ⊢lemma switched_sign {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V)    (A B : Finset V) (hbal : G.IsBalancedPartition A B) (w u v : V) (h : G.graph.Adj u v) :    (G.switch w).sgn ⟨s(u, v), h⟩ =      sign (xor (flipped (color A) w u) (flipped (color A) w v)) := by  change (if w ∈ s(u, v) then -G.sgn ⟨s(u, v), h⟩ else G.sgn ⟨s(u, v), h⟩) = _  rw [balanced_sign G A B hbal u v h]  have hne : u ≠ v := G.graph.ne_of_adj h  by_cases hu : u = w <;> by_cases hv : v = w  · exact False.elim (hne (hu.trans hv.symm))  · subst u    cases h1 : color A w <;> cases h2 : color A v <;>      simp [Sym2.mem_iff, hv, Ne.symm hv, sign, flipped, h1, h2]  · subst v    cases h1 : color A u <;> cases h2 : color A w <;>      simp [Sym2.mem_iff, hu, Ne.symm hu, sign, flipped, h1, h2]  · simp [Sym2.mem_iff, hu, hv, Ne.symm hu, Ne.symm hv, flipped]end OP1525Bridgenamespace OP1525Bridgelemma sign_flip_left (a b : Bool) : sign (xor (xor a true) b) = -sign (xor a b) := by  cases a <;> cases b <;> decidelemma sign_flip_right (a b : Bool) : sign (xor a (xor b true)) = -sign (xor a b) := by  cases a <;> cases b <;> decidelemma from_switched_iso {V W : Type*} [DecidableEq V] [DecidableEq W] [Fintype W]    (H : SignedGraph W) (G : SimpleGraph V) (f : G ≃g H.graph) (w : W) (F : V → Bool)    (hcard : ∀ u v (h : G.Adj u v),      (H.switch w).sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ = sign (xor (F u) (F v))) :    ∀ u v (h : G.Adj u v),      H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ =        sign (xor (flipped F (f.symm w) u) (flipped F (f.symm w) v)) := by  intro u v h  have hne : u ≠ v := G.ne_of_adj h  have hm : w ∈ s(f u, f v) ↔ u = f.symm w ∨ v = f.symm w := by    have hf (z : V) : w = f z ↔ z = f.symm w := by      constructor      · intro h        apply f.injective        simpa using h.symm      · intro h        subst z        simp    simp only [Sym2.mem_iff, hf]  have hh := hcard u v h  change (if w ∈ s(f u, f v) then -H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩    else H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩) = _ at hh  by_cases hu : u = f.symm w <;> by_cases hv : v = f.symm w  · exact False.elim (hne (hu.trans hv.symm))  · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inl hu)    simp [hw] at hh    have hdu : decide (u = f.symm w) = true := by simp [hu]    have hdv : decide (v = f.symm w) = false := by simp [hv]    simp only [flipped, hdu, hdv, Bool.xor_false]    rw [sign_flip_left]    linarith  · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inr hv)    simp [hw] at hh    have hdu : decide (u = f.symm w) = false := by simp [hu]    have hdv : decide (v = f.symm w) = true := by simp [hv]    simp only [flipped, hdu, hdv, Bool.xor_false]    rw [sign_flip_right]    linarith  · have hw : w ∉ s(f u, f v) := fun hh' => (hm.mp hh').elim hu hv    simpa [hw, flipped, hu, hv] using hhend OP1525Bridgenamespace OP1525Bridgelemma to_switched_iso {V W : Type*} [DecidableEq V] [DecidableEq W] [Fintype W]    (H : SignedGraph W) (G : SimpleGraph V) (f : G ≃g H.graph) (w : W) (F : V → Bool)    (hrep : ∀ u v (h : G.Adj u v),      H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ = sign (xor (F u) (F v))) :    ∀ u v (h : G.Adj u v),      (H.switch w).sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ =        sign (xor (flipped F (f.symm w) u) (flipped F (f.symm w) v)) := by  intro u v h  have hne : u ≠ v := G.ne_of_adj h  have hm : w ∈ s(f u, f v) ↔ u = f.symm w ∨ v = f.symm w := by    have hf (z : V) : w = f z ↔ z = f.symm w := by      constructor      · intro hz        apply f.injective        simpa using hz.symm      · intro hz        subst z        simp    simp only [Sym2.mem_iff, hf]  change (if w ∈ s(f u, f v) then -H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩    else H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩) = _  rw [hrep u v h]  by_cases hu : u = f.symm w <;> by_cases hv : v = f.symm w  · exact False.elim (hne (hu.trans hv.symm))  · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inl hu)    have hdu : decide (u = f.symm w) = true := by simp [hu]    have hdv : decide (v = f.symm w) = false := by simp [hv]    simp only [hw, ↓reduceIte, flipped, hdu, hdv, Bool.xor_false]    exact (sign_flip_left _ _).symm  · have hw : w ∈ s(f u, f v) := hm.mpr (Or.inr hv)    have hdu : decide (u = f.symm w) = false := by simp [hu]    have hdv : decide (v = f.symm w) = true := by simp [hv]    simp only [hw, ↓reduceIte, flipped, hdu, hdv, Bool.xor_false]    exact (sign_flip_right _ _).symm  · have hw : w ∉ s(f u, f v) := fun hh => (hm.mp hh).elim hu hv    simp [hw, flipped, hu, hv]end OP1525Bridgenamespace OP1525Bridgelemma xor_common (a b c : Bool) : xor (xor a c) (xor b c) = xor a b := by  cases a <;> cases b <;> cases c <;> decidetheorem deck_color_model {V W : Type*} [DecidableEq V] [DecidableEq W] [Fintype V] [Fintype W]    (G : SignedGraph V) (H : SignedGraph W) (hconn : G.graph.Connected)    (A B : Finset V) (hbal : G.IsBalancedPartition A B) (π0 : V ≃ W)    (hcards : ∀ v, (G.switch v).IsIsomorphic (H.switch (π0 v))) (a : V) :    ∃ (F : V → Bool) (π : Equiv.Perm V),      (∀ v, ∃ g : G.graph ≃g G.graph, ∃ c : Bool, ∀ x,        flipped (color A) v (g x) = xor (flipped F (π v) x) c) ∧      (∀ (g : G.graph ≃g G.graph) (c : Bool),        (∀ x, color A (g x) = xor (F x) c) → G.IsIsomorphic H) := by  classical  obtain ⟨f, hf⟩ := hcards a  let F0 : V → Bool := flipped (color A) a  let F : V → Bool := flipped F0 (f.symm (π0 a))  have hcard0 : ∀ u v (h : G.graph.Adj u v),      (H.switch (π0 a)).sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ = sign (xor (F0 u) (F0 v)) := by    intro u v h    rw [hf u v h]    exact switched_sign G A B hbal a u v h  have hrep : ∀ u v (h : G.graph.Adj u v),      H.sgn ⟨s(f u, f v), f.map_adj_iff.mpr h⟩ = sign (xor (F u) (F v)) :=    from_switched_iso H G.graph f (π0 a) F0 hcard0  let π : Equiv.Perm V := π0.trans f.toEquiv.symm  refine ⟨F, π, ?_, ?_⟩  · intro v    obtain ⟨fv, hfv⟩ := hcards v    let g : G.graph ≃g G.graph := f.trans fv.symm    have he : ∀ u w, G.graph.Adj u w →        xor (flipped (color A) v (g u)) (flipped (color A) v (g w)) =          xor (flipped F (π v) u) (flipped F (π v) w) := by      intro u w h      apply sign_injective      calc        sign (xor (flipped (color A) v (g u)) (flipped (color A) v (g w))) =            (G.switch v).sgn ⟨s(g u, g w), g.map_adj_iff.mpr h⟩ :=          (switched_sign G A B hbal v (g u) (g w) (g.map_adj_iff.mpr h)).symm        _ = (H.switch (π0 v)).sgn ⟨s(f u, f w), f.map_adj_iff.mpr h⟩ := by          have hp := (hfv (g u) (g w) (g.map_adj_iff.mpr h)).symm          have hcomp (x : V) : fv (g x) = f x := by            change fv (fv.symm (f x)) = f x            exact fv.apply_symm_apply _          simpa only [hcomp] using hp        _ = sign (xor (flipped F (π v) u) (flipped F (π v) w)) := by          have hp : π v = f.symm (π0 v) := rfl          rw [hp]          exact to_switched_iso H G.graph f (π0 v) F hrep u w h    obtain ⟨c, hc⟩ := connected_labels G.graph hconn (fun x => flipped (color A) v (g x))      (flipped F (π v)) he    exact ⟨g, c, hc⟩  · intro g c hc    let z : G.graph ≃g H.graph := g.symm.trans f    refine ⟨z, ?_⟩    intro u v h    have hu : color A u = xor (F (g.symm u)) c := by simpa using hc (g.symm u)    have hv : color A v = xor (F (g.symm v)) c := by simpa using hc (g.symm v)    calc      H.sgn ⟨s(z u, z v), z.map_adj_iff.mpr h⟩ =          sign (xor (F (g.symm u)) (F (g.symm v))) := by        change H.sgn ⟨s(f (g.symm u), f (g.symm v)), _⟩ = _        exact hrep (g.symm u) (g.symm v) (g.symm.map_adj_iff.mpr h)      _ = sign (xor (color A u) (color A v)) := by rw [hu, hv, xor_common]      _ = G.sgn ⟨s(u, v), h⟩ := (balanced_sign G A B hbal u v h).symmend OP1525Bridgenamespace OP1525Bridgeend OP1525Bridgeopen OP1525Bridgetheorem signed_graph_reconstructible_balanced_mono_invariant {V : Type*}    [DecidableEq V] [Fintype V] (G : SignedGraph V) (hconn : G.graph.Connected)    (A B : Finset V) (hbal : G.IsBalancedPartition A B) (S : Finset V)    (hbig : S.card ≥ 3) (hout : (Finset.univ \ S).card ≥ 2)    (hmono : S ⊆ A ∨ S ⊆ B)    (hinvariant : ∀ f : G.graph ≃g G.graph, ∀ x, x ∈ S ↔ f x ∈ S) :    G.IsReconstructible := by  classical  obtain ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ :=    Finset.two_lt_card.mp (show 2 < S.card by omega)  obtain ⟨u, hu, v, hv, huv⟩ :=    Finset.one_lt_card.mp (show 1 < (Finset.univ \ S).card by omega)  have huS : u ∉ S := (Finset.mem_sdiff.mp hu).2  have hvS : v ∉ S := (Finset.mem_sdiff.mp hv).2  have hA : ∀ (x : V), x ∈ S → ∀ (y : V), y ∈ S → OP1525Bridge.color A x = OP1525Bridge.color A y := by    rcases hmono with h | h    · intro x hx y hy      simp [OP1525Bridge.color, h hx, h hy]    · intro x hx y hy      have hnotx : x ∉ A := fun hxA => (Finset.disjoint_left.mp hbal.2.1) hxA (h hx)      have hnoty : y ∉ A := fun hyA => (Finset.disjoint_left.mp hbal.2.1) hyA (h hy)      simp [OP1525Bridge.color, hnotx, hnoty]  unfold SignedGraph.IsReconstructible  intro W _ _ H hdeck  obtain ⟨π0, hcards⟩ := hdeck  obtain ⟨F, π, hcolors, hlift⟩ := deck_color_model G H hconn A B hbal π0 hcards a  let P : Equiv.Perm V → Prop := fun p => ∃ g : G.graph ≃g G.graph, g.toEquiv = p  have hpres : ∀ p, P p → ∀ x, x ∈ (S : Set V) ↔ p x ∈ (S : Set V) := by    intro p hp x    obtain ⟨g, rfl⟩ := hp    exact hinvariant g x  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  obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ :=    OP1525MonoPoly.reconstruct_of_invariant_monochrome (OP1525Bridge.color A) F P (S : Set V)      a b c ha hb hc hab hac hbc u v huS hvS huv hA hpres π hmatch  exact hlift g d hd
See it in the graphDiscuss this resultChallenge it