AFTD Auto-Formalizing Theoretical Domains

signed_graph_reconstructible_balanced_three_fixed

theoremverifiedoriginal

Every connected balanced signed graph on at least seven vertices is reconstructible from its switching deck if its underlying graph has three distinct vertices fixed by every graph automorphism.

Statement

theorem signed_graph_reconstructible_balanced_three_fixed {V : Type*} [DecidableEq V] [Fintype V]
    (G : SignedGraph V) (hconn : G.graph.Connected) (hsize : Fintype.card V ≥ 7)
    (A B : Finset V) (hbal : G.IsBalancedPartition A B)
    (r s t : V) (hrs : r ≠ s) (hrt : r ≠ t) (hst : s ≠ t)
    (hfix : ∀ f : G.graph ≃g G.graph, f r = r ∧ f s = s ∧ f t = t) :
    G.IsReconstructible
Related work
A structural subcase of OP-1525; compare arXiv:2611.13901, Section 4.1 and Remark 4.11.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • op1525_three_fixed_points_reconstructLet A and B be Boolean colorings of a finite set V of at least seven points, and let P be any predicate on permutations, all of whose…
  • 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…
  • 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.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.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…
  • 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}.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a signed graph on $V$ (consisting of a simple graph $G.\text{graph}$ and a signing function $G.\text{sgn} : G.\text{graph}.\text{edgeSet} \to \mathbb{Z}$ whose values are all $1$ or $-1$). Suppose that: 1. $G.\text{graph}$ is connected (SimpleGraph.Connected); 2. the number of vertices $|V| \ge 7$; 3. $A$ and $B$ are finite subsets of $V$ such that $G.\text{IsBalancedPartition}(A, B)$ holds; 4. $r, s, t \in V$ are three pairwise distinct vertices ($r \ne s$, $r \ne t$, and $s \ne t$); 5. every graph automorphism $f : G.\text{graph} \simeq_g G.\text{graph}$ fixes $r$, $s$, and $t$ (i.e., $f(r) = r$, $f(s) = s$, and $f(t) = t$). Then $G$ is reconstructible ($G.\text{IsReconstructible}$ holds).

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 reconstructibility of a balanced signed graph G from its switching deck is reduced to a Boolean coloring reconstruction problem via the bridge lemma OP1525Bridge.deck_color_model. Because the underlying graph has at least seven vertices and three anchor vertices r, s, t fixed by every automorphism, there exists an unperturbed vertex v such that neither v nor its deck image π(v) meets the anchors. Evaluating the switched deck equation at v preserves the anchor colors and establishes the invariant parity differences between r, s, and t. Applying these invariants to the switched card at r forces the deck permutation to fix r, which cancels the vertex flip and yields an automorphism matching the two signed graphs.

  1. For any booleans a, b, c, the common term c cancels when XORing differences: (a ⊕ c) ⊕ (b ⊕ c) = a ⊕ b. automation

    Because the domain Bool has only two elements, the identity is verified by exhaustively checking all 2³ = 8 truth assignments for a, b, c.

    line 4

      cases a <;> cases b <;> cases c <;> decide
  2. If a ⊕ true = (b ⊕ true) ⊕ c, then a = b ⊕ c. automation

    The negations on both sides cancel in the XOR algebra; the implication is checked by exhausting all 8 truth assignments for a, b, c.

    line 8

      cases a <;> cases b <;> cases c <;> decide
  3. There exists a vertex v that belongs neither to the anchor set {r, s, t} nor to its preimage π⁻¹({r, s, t}).

    Let anchors = {r, s, t} and bad = anchors ∪ π⁻¹(anchors). Since r, s, t are pairwise distinct, |anchors| ≤ 3. By subadditivity of cardinality under union and the fact that the image under the bijection π⁻¹ has size at most |anchors|, |bad| ≤ 3 + 3 = 6. Since |V| ≥ 7, bad cannot be all of V, so some vertex v lies outside bad.

    lines 21–41

    uses Finset.card_union_le, Finset.card_image_le, congrArg, Finset.card_univ

      classical
      let anchors : Finset V := {r, s, t}
      let bad : Finset V := anchors ∪ anchors.image π.symm
      have ha : anchors.card ≤ 3 := by
        dsimp [anchors]
        simp [hrs, hrt, hst]
      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
  4. Neither v nor π(v) is equal to r, s, or t.

    Since v ∉ bad, v is not in the first union component anchors = {r, s, t}, so v ≠ r, v ≠ s, and v ≠ t. Similarly, v is not in the second component π⁻¹(anchors), which means π(v) ∉ anchors, so π(v) ≠ r, π(v) ≠ s, and π(v) ≠ t.

    lines 42–53

    uses Finset.mem_union_left, Finset.mem_union_right, Finset.mem_image.mpr

      have hvn : v ≠ r ∧ v ≠ s ∧ v ≠ t := by
        have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h)
        simpa [anchors] using h
      have hvp : π v ≠ r ∧ π v ≠ s ∧ π v ≠ t := by
        have hnot : v ∉ anchors.image π.symm := by
          intro h
          exact hv (Finset.mem_union_right _ h)
        have hp : π v ∉ anchors := by
          intro h
          apply hnot
          exact Finset.mem_image.mpr ⟨π v, h, by simp⟩
        simpa [anchors] using hp
  5. The relative parities of A and B agree on the anchor vertices: A(r) ⊕ A(s) = B(r) ⊕ B(s) and A(r) ⊕ A(t) = B(r) ⊕ B(t).

    Specializing the deck hypothesis to vertex v yields a permutation g fixing r, s, t and a bit c. Because neither v nor π(v) is in {r, s, t}, the flip terms [g(x) = v] and [x = π(v)] vanish at x ∈ {r, s, t}, giving A(r) = B(r) ⊕ c, A(s) = B(s) ⊕ c, and A(t) = B(t) ⊕ c for the same c. Canceling c with op1525_bool_xor_common yields the invariant parity differences between r and s, and between r and t.

    lines 54–67

    uses op1525_bool_xor_common

      obtain ⟨g, hg, c, hc⟩ := hdeck v
      obtain ⟨hgr, hgs, hgt⟩ := hfix g hg
      have er := hc r
      have es := hc s
      have et := hc t
      simp [hgr, hvn.1.symm, hvp.1.symm] at er
      simp [hgs, hvn.2.1.symm, hvp.2.1.symm] at es
      simp [hgt, hvn.2.2.symm, hvp.2.2.symm] at et
      have hbase1 : xor (A r) (A s) = xor (B r) (B s) := by
        rw [er, es]
        exact op1525_bool_xor_common _ _ _
      have hbase2 : xor (A r) (A t) = xor (B r) (B t) := by
        rw [er, et]
        exact op1525_bool_xor_common _ _ _
  6. The deck card permutation fixes r: π(r) = r.

    Assume for contradiction that π(r) ≠ r. If π(r) ≠ s, evaluating the switched deck equation for card r at vertices r and s, together with the invariant A(r) ⊕ A(s) = B(r) ⊕ B(s), leads to a contradiction across all 32 truth assignments for (A(r), A(s), B(r), B(s), c'), forcing π(r) = s. The symmetric argument at vertices r and t forces π(r) = t. This implies s = t, contradicting s ≠ t. Therefore π(r) = r.

    lines 68–87

    uses Ne.symm

      obtain ⟨g', hg', c', hc'⟩ := hdeck r
      obtain ⟨hg'r, hg's, hg't⟩ := hfix g' hg'
      have e'r := hc' r
      have e's := hc' s
      have e't := hc' t
      have hπr : π r = r := by
        by_contra hn
        have hs : π r = s := by
          by_contra hs
          simp [hg'r, hg's, hrs.symm, Ne.symm hn, Ne.symm hs] at e'r e's
          cases hAr : A r <;> cases hAs : A s <;> cases hBr : B r <;>
            cases hBs : B s <;> cases hcc : c' <;>
              simp [hAr, hAs, hBr, hBs, hcc] at hbase1 e'r e's
        have ht : π r = t := by
          by_contra ht
          simp [hg'r, hg't, hrt.symm, Ne.symm hn, Ne.symm ht] at e'r e't
          cases hAr : A r <;> cases hAt : A t <;> cases hBr : B r <;>
            cases hBt : B t <;> cases hcc : c' <;>
              simp [hAr, hAt, hBr, hBt, hcc] at hbase2 e'r e't
        exact hst (hs.symm.trans ht)
  7. The automorphism g' and bit c' from the deck card at r satisfy A(g'(x)) = B(x) ⊕ c' for all x ∈ V.

    Since π(r) = r and g' is an injective permutation fixing r, g'(x) = r if and only if x = r. When x = r, both indicator terms are true, so A(g'(r)) ⊕ true = (B(r) ⊕ true) ⊕ c', which by op1525_bool_xor_cancel_flip gives A(g'(r)) = B(r) ⊕ c'. When x ≠ r, neither indicator flips, giving A(g'(x)) = B(x) ⊕ c' directly. This establishes op1525_three_fixed_points_reconstruct.

    lines 88–106

    uses op1525_bool_xor_cancel_flip

      refine ⟨g', hg', c', ?_⟩
      intro x
      have heq := hc' x
      rw [hπr] at heq
      have he : (g' x = r) ↔ x = r := by
        constructor
        · intro h
          apply g'.injective
          simpa [hg'r] using h
        · intro h
          simpa [h] using hg'r
      by_cases hx : x = r
      · have hgx : g' x = r := he.mpr hx
        have h1 : decide (g' x = r) = true := by simp [hgx]
        have h2 : decide (x = r) = true := by simp [hx]
        rw [h1, h2] at heq
        exact op1525_bool_xor_cancel_flip _ _ _ heq
      · have hgx : g' x ≠ r := fun h => hx (he.mp h)
        simpa [hx, hgx] using heq
  8. Translating the switching deck hypothesis through the bridge model yields a Boolean coloring problem satisfying the fixed-point and deck-matching conditions.

    To show G is reconstructible, consider an arbitrary signed graph H with the same switching deck as G under a bijection π₀. The bridge lemma deck_color_model produces a coloring F on H, a card bijection π, and card isomorphism witnesses. Since every graph automorphism of G fixes r, s, t, the set of automorphisms P satisfies the three-fixed-point hypothesis, and each switching isomorphism translates into the flipped coloring deck condition.

    lines 118–135

    uses SignedGraph.IsReconstructible, OP1525Bridge.deck_color_model, OP1525Bridge.flipped

      classical
      unfold SignedGraph.IsReconstructible
      intro W _ _ H hdeck
      obtain ⟨π0, hcards⟩ := hdeck
      obtain ⟨F, π, hcolors, hlift⟩ := OP1525Bridge.deck_color_model G H hconn A B hbal π0 hcards r
      let P : Equiv.Perm V → Prop := fun p => ∃ g : G.graph ≃g G.graph, g.toEquiv = p
      have hfixed : ∀ p, P p → p r = r ∧ p s = s ∧ p t = t := by
        intro p hp
        obtain ⟨g, rfl⟩ := hp
        exact hfix 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 [OP1525Bridge.flipped] using hg x
  9. The signed graph G is isomorphic to H, and therefore G is reconstructible.

    Applying op1525_three_fixed_points_reconstruct provides an automorphism g of G and a bit d such that A(g(x)) = F(x) ⊕ d for all x. Feeding g and d into the lifting property hlift from the bridge model proves G ≅ H, which completes the reconstructibility proof.

    lines 136–139

    uses OP1525ThreePoly.op1525_three_fixed_points_reconstruct

      obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ :=
        OP1525ThreePoly.op1525_three_fixed_points_reconstruct (OP1525Bridge.color A) F P
          r s t hrs hrt hst hsize hfixed π hmatch
      exact hlift g d hd
op1525_bool_xor_common
For any booleans a, b, c, XORing both a and b with a common bit c preserves their XOR difference: (a ⊕ c) ⊕ (b ⊕ c) = a ⊕ b.
op1525_bool_xor_cancel_flip
If a ⊕ true = (b ⊕ true) ⊕ c, then a = b ⊕ c.
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_image_le
The cardinality of the image of a finite set under any function is at most the cardinality of the original set: |f(s)| ≤ |s|.
congrArg
Equal inputs to a function yield equal outputs: if a₁ = a₂ then f(a₁) = f(a₂).
Finset.card_univ
The cardinality of the universal finset of a finite type is equal to the number of elements in the type: |univ| = |V|.
Finset.mem_union_left
If an element belongs to a finite set s, it belongs to the union s ∪ t.
Finset.mem_union_right
If an element belongs to a finite set t, it belongs to the union s ∪ t.
Finset.mem_image.mpr
If an element a ∈ s satisfies f(a) = b, then b ∈ f(s).
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
SignedGraph.IsReconstructible
A signed graph G is reconstructible from its switching deck if every signed graph with the same switching deck as G is isomorphic to G.
OP1525Bridge.deck_color_model
For a connected balanced signed graph G and a signed graph H with isomorphic switching cards, there exist a vertex coloring F on H, a card bijection π, and card-wise automorphisms with flips relating the switched colorings to F, such that finding an automorphism matching the coloring of G with F up to a constant bit implies G ≅ H.
OP1525Bridge.flipped
The coloring obtained by flipping the color at vertex w: flipped(f, w, x) = f(x) ⊕ [x = w].
OP1525ThreePoly.op1525_three_fixed_points_reconstruct
Reconstruction theorem for Boolean colorings on a finite set of at least seven elements with three distinct anchor points fixed by every allowed permutation: if each single-point flip of A matches a single-point flip of B under an allowed permutation up to a constant bit, then A equals B up to an allowed permutation and a constant bit.

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

namespace OP1525ThreePolylemma op1525_bool_xor_common (a b c : Bool) : xor (xor a c) (xor b c) = xor a b := by  cases a <;> cases b <;> cases c <;> decidelemma op1525_bool_xor_cancel_flip (a b c : Bool) :    xor a true = xor (xor b true) c → a = xor b c := by  cases a <;> cases b <;> cases c <;> decidetheorem op1525_three_fixed_points_reconstruct    {V : Type*} [DecidableEq V] [Fintype V]    (A B : V → Bool) (P : Equiv.Perm V → Prop)    (r s t : V) (hrs : r ≠ s) (hrt : r ≠ t) (hst : s ≠ t)    (hsize : Fintype.card V ≥ 7)    (hfix : ∀ g, P g → g r = r ∧ g s = s ∧ g t = t)    (π : Equiv.Perm V)    (hdeck : ∀ v, ∃ g, P g ∧ ∃ c : Bool, ∀ x,      xor (A (g x)) (decide (g x = v)) =        xor (xor (B x) (decide (x = π v))) c) :    ∃ g, P g ∧ ∃ c : Bool, ∀ x, A (g x) = xor (B x) c := by  classical  let anchors : Finset V := {r, s, t}  let bad : Finset V := anchors ∪ anchors.image π.symm  have ha : anchors.card ≤ 3 := by    dsimp [anchors]    simp [hrs, hrt, hst]  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 ≠ r ∧ v ≠ s ∧ v ≠ t := by    have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h)    simpa [anchors] using h  have hvp : π v ≠ r ∧ π v ≠ s ∧ π v ≠ t := by    have hnot : v ∉ anchors.image π.symm := by      intro h      exact hv (Finset.mem_union_right _ h)    have hp : π v ∉ anchors := by      intro h      apply hnot      exact Finset.mem_image.mpr ⟨π v, h, by simp⟩    simpa [anchors] using hp  obtain ⟨g, hg, c, hc⟩ := hdeck v  obtain ⟨hgr, hgs, hgt⟩ := hfix g hg  have er := hc r  have es := hc s  have et := hc t  simp [hgr, hvn.1.symm, hvp.1.symm] at er  simp [hgs, hvn.2.1.symm, hvp.2.1.symm] at es  simp [hgt, hvn.2.2.symm, hvp.2.2.symm] at et  have hbase1 : xor (A r) (A s) = xor (B r) (B s) := by    rw [er, es]    exact op1525_bool_xor_common _ _ _  have hbase2 : xor (A r) (A t) = xor (B r) (B t) := by    rw [er, et]    exact op1525_bool_xor_common _ _ _  obtain ⟨g', hg', c', hc'⟩ := hdeck r  obtain ⟨hg'r, hg's, hg't⟩ := hfix g' hg'  have e'r := hc' r  have e's := hc' s  have e't := hc' t  have hπr : π r = r := by    by_contra hn    have hs : π r = s := by      by_contra hs      simp [hg'r, hg's, hrs.symm, Ne.symm hn, Ne.symm hs] at e'r e's      cases hAr : A r <;> cases hAs : A s <;> cases hBr : B r <;>        cases hBs : B s <;> cases hcc : c' <;>          simp [hAr, hAs, hBr, hBs, hcc] at hbase1 e'r e's    have ht : π r = t := by      by_contra ht      simp [hg'r, hg't, hrt.symm, Ne.symm hn, Ne.symm ht] at e'r e't      cases hAr : A r <;> cases hAt : A t <;> cases hBr : B r <;>        cases hBt : B t <;> cases hcc : c' <;>          simp [hAr, hAt, hBr, hBt, hcc] at hbase2 e'r e't    exact hst (hs.symm.trans ht)  refine ⟨g', hg', c', ?_⟩  intro x  have heq := hc' x  rw [hπr] at heq  have he : (g' x = r) ↔ x = r := by    constructor    · intro h      apply g'.injective      simpa [hg'r] using h    · intro h      simpa [h] using hg'r  by_cases hx : x = r  · have hgx : g' x = r := he.mpr hx    have h1 : decide (g' x = r) = true := by simp [hgx]    have h2 : decide (x = r) = true := by simp [hx]    rw [h1, h2] at heq    exact op1525_bool_xor_cancel_flip _ _ _ heq  · have hgx : g' x ≠ r := fun h => hx (he.mp h)    simpa [hx, hgx] using heqend OP1525ThreePolyopen OP1525Bridgetheorem signed_graph_reconstructible_balanced_three_fixed {V : Type*} [DecidableEq V] [Fintype V]    (G : SignedGraph V) (hconn : G.graph.Connected) (hsize : Fintype.card V ≥ 7)    (A B : Finset V) (hbal : G.IsBalancedPartition A B)    (r s t : V) (hrs : r ≠ s) (hrt : r ≠ t) (hst : s ≠ t)    (hfix : ∀ f : G.graph ≃g G.graph, f r = r ∧ f s = s ∧ f t = t) :    G.IsReconstructible := by  classical  unfold SignedGraph.IsReconstructible  intro W _ _ H hdeck  obtain ⟨π0, hcards⟩ := hdeck  obtain ⟨F, π, hcolors, hlift⟩ := OP1525Bridge.deck_color_model G H hconn A B hbal π0 hcards r  let P : Equiv.Perm V → Prop := fun p => ∃ g : G.graph ≃g G.graph, g.toEquiv = p  have hfixed : ∀ p, P p → p r = r ∧ p s = s ∧ p t = t := by    intro p hp    obtain ⟨g, rfl⟩ := hp    exact hfix 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 [OP1525Bridge.flipped] using hg x  obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ :=    OP1525ThreePoly.op1525_three_fixed_points_reconstruct (OP1525Bridge.color A) F P      r s t hrs hrt hst hsize hfixed π hmatch  exact hlift g d hd
See it in the graphDiscuss this resultChallenge it