AFTD Auto-Formalizing Theoretical Domains

signed_graph_reconstructible_balanced_mixed_twin_pair

theoremverifiedoriginal

Let G be a connected balanced signed graph on at least five vertices, with a specified balance partition. Suppose distinct vertices a and b lie in different parts, every automorphism of the underlying graph preserves the unordered pair {a, b}, and the permutation that swaps exactly a and b is itself an automorphism of the underlying graph. Then G is determined up to signed-graph isomorphism among all finite signed graphs by its vertex-switching deck: a bijection that matches every one-vertex-switched card of G to an isomorphic switched card of another signed graph H implies that G and H are isomorphic.

Statement

theorem signed_graph_reconstructible_balanced_mixed_twin_pair {V : Type*} [DecidableEq V] [Fintype V]
    (G : SignedGraph V) (hconn : G.graph.Connected)
    (A B : Finset V) (hbal : G.IsBalancedPartition A B)
    (a b : V) (hab : a ≠ b) (hsize : Fintype.card V ≥ 5)
    (hmixed : (a ∈ A ∧ b ∉ A) ∨ (a ∉ A ∧ b ∈ A))
    (hinv : ∀ g : G.graph ≃g G.graph, ∀ x, (x = a ∨ x = b) ↔ (g x = a ∨ g x = b))
    (τ : G.graph ≃g G.graph) (hτ : τ.toEquiv = Equiv.swap a b) : G.IsReconstructible
Related work
A mixed twin-pair structural subcase of OP-1525, compared with 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.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…
  • 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. Let G be a signed graph on V (a simple graph on V equipped with an edge signing function sgn : G.graph.edgeSet → Int taking values in {-1, 1}). Assume: 1. G.graph is connected (G.graph.Connected); 2. A and B are finite subsets of V such that G.IsBalancedPartition A B holds; 3. a and b are distinct vertices of V (a ≠ b); 4. V has at least 5 vertices (Fintype.card V ≥ 5); 5. Exactly one of a and b is in A (i.e. (a ∈ A ∧ b ∉ A) ∨ (a ∉ A ∧ b ∈ A)); 6. For every graph automorphism g of G.graph and every vertex x of V, x = a ∨ x = b ↔ g x = a ∨ g x = b (i.e. {a, b} is setwise invariant under every automorphism of G.graph); 7. τ is a graph automorphism of G.graph whose underlying permutation is the transposition swapping a and b (τ.toEquiv = Equiv.swap a b). 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

test summary of the proof that has more words and describes the overall argument in several sentences. It shows reconstructibility of balanced signed graphs with mixed twin pairs.

  1. reconstruct

    expl

    lines 16–111

      classical
      have hneg (x : V) (hx : x = a ∨ x = b) : A (Equiv.swap a b x) = !(A x) := by
        rcases hx with hx | hx <;> rw [hx]
        · cases ha : A a <;> cases hb : A b <;> simp [ha, hb] at hA ⊢
        · cases ha : A a <;> cases hb : A b <;> simp [ha, hb] at 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 hdistinct : g₀ a ≠ g₀ b := fun hh => hab (g₀.injective hh)
      have hdiff : A (g₀ a) ≠ A (g₀ b) := by
        rcases hg₀a with ha | ha <;> rcases hg₀b with hb | hb
        · exact False.elim (hdistinct (ha.trans hb.symm))
        · simpa [ha, hb] using hA
        · simpa [ha, hb] using Ne.symm hA
        · exact False.elim (hdistinct (ha.trans hb.symm))
      have ha₀ : A (g₀ a) = xor (B a) d₀ := by
        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
        simpa [hne, Ne.symm hπw.1] using h₀ a
      have hb₀ : A (g₀ b) = xor (B b) d₀ := by
        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
        simpa [hne, Ne.symm hπw.2] using h₀ b
      have hB : B a ≠ B b := by
        intro he
        apply hdiff
        rw [ha₀, hb₀, he]
      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 hga_ne : g a ≠ g b := fun hh => hab (g.injective hh)
      have hπa : π a = a ∨ π a = b := by
        by_contra hn
        push_neg at hn
        have ea := heq a
        have eb := heq b
        rcases hga with ha | ha <;> rcases hgb with hb | hb
        · exact hga_ne (ha.trans hb.symm)
        · simp only [ha, hb, hab, Ne.symm hab, decide_true, decide_false,
            Ne.symm hn.1, Ne.symm hn.2, Bool.xor_false] at ea eb
          cases hAa : A a <;> cases hAb : A b <;> cases hBa : B a <;>
            cases hBb : B b <;> cases hd : d <;>
              simp [hAa, hAb, hBa, hBb, hd] at hA hB ea eb
        · simp only [ha, hb, hab, Ne.symm hab, decide_true, decide_false,
            Ne.symm hn.1, Ne.symm hn.2, Bool.xor_false] at ea eb
          cases hAa : A a <;> cases hAb : A b <;> cases hBa : B a <;>
            cases hBb : B b <;> cases hd : d <;>
              simp [hAa, hAb, hBa, hBb, hd] at hA hB ea eb
        · exact hga_ne (ha.trans hb.symm)
      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 hequiv (x : V) : (g x = a) ↔ x = q := by
        constructor
        · intro h
          exact g.injective (h.trans hgq.symm)
        · intro h
          rw [h, hgq]
      by_cases hmatch : q = π a
      · refine ⟨g, hg, d, ?_⟩
        intro x
        have hx := heq x
        rw [show decide (g x = a) = decide (x = π a) by simp only [hequiv, hmatch]] at hx
        exact xor_cancel_flip _ _ _ _ hx
      · let g' : Equiv.Perm V := g.trans (Equiv.swap a b)
        have hg' : P g' := hswap g hg
        refine ⟨g', hg', d, ?_⟩
        intro x
        by_cases hx : x = a ∨ x = b
        · have hgx : g x = a ∨ g x = b := (hinv g hg x).mp hx
          have hcomp : (x = q) ↔ x ≠ π a := by
            rcases hq with hq | hq <;> rcases hπa with hp | hp <;>
              rcases hx with hx | hx <;>
              simp [hq, hp, hx, hab, Ne.symm hab] at hmatch ⊢
          have hdec : decide (g x = a) = !(decide (x = π a)) := by
            by_cases he : x = π a
            · have hnot : x ≠ q := by
                intro h
                exact (hcomp.mp h) he
              have hga : g x ≠ a := fun h => hnot ((hequiv x).mp h)
              subst x
              simp [hga]
            · have hxq : x = q := hcomp.mpr he
              have hga : g x = a := (hequiv x).mpr hxq
              simp [hga, he]
          have he := heq x
          rw [hdec] at he
          change A (Equiv.swap a b (g x)) = xor (B x) d
          rw [hneg (g x) hgx]
          cases ha : A (g x) <;> cases hb : B x <;> cases hc : d <;>
            cases hd : decide (x = π a) <;> simp [ha, hb, hc, hd] at he ⊢
        · have hgx : ¬(g x = a ∨ g x = b) := fun h => hx ((hinv g hg x).mpr h)
          have hxa : g x ≠ a := fun h => hgx (Or.inl h)
          have hxb : g x ≠ b := fun h => hgx (Or.inr h)
          have hxp : x ≠ π a := by intro h; apply hx; rw [h]; exact hπa
          change A (Equiv.swap a b (g x)) = xor (B x) d
          rw [Equiv.swap_apply_of_ne_of_ne hxa hxb]
          simpa [hxa, hxp] using heq x
  2. main theorem

    expl

    lines 126–184

      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 hswap : ∀ p, P p → P (p.trans (Equiv.swap a b)) := by
        intro p hp
        obtain ⟨g, rfl⟩ := hp
        refine ⟨g.trans τ, ?_⟩
        change g.toEquiv.trans τ.toEquiv = _
        rw [hτ]
      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}
      let bad : Finset V := anchors ∪ anchors.image π.symm
      have ha : anchors.card ≤ 2 := Finset.card_le_two
      have hb : bad.card ≤ 4 := 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 := by
        have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h)
        simpa [anchors] using h
      have hvp : π v ≠ a ∧ π v ≠ b := 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
        rcases hmixed with h | h <;> simp [OP1525Bridge.color, h.1, h.2]
      obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ := OP1525MixedTwinPair.reconstruct
        (OP1525Bridge.color A) F P a b hab hA hp hswap π v hvn hvp hmatch
      exact hlift g d hd

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 OP1525MixedTwinPairvariable {V : Type*} [DecidableEq V]theorem reconstruct (A B : V → Bool) (P : Equiv.Perm V → Prop)    (a b : V) (hab : a ≠ b) (hA : A a ≠ A b)    (hinv : ∀ g, P g → ∀ x, (x = a ∨ x = b) ↔ (g x = a ∨ g x = b))    (hswap : ∀ g, P g → P (g.trans (Equiv.swap a b)))    (π : Equiv.Perm V) (w : V)    (hw : w ≠ a ∧ w ≠ b) (hπw : π w ≠ a ∧ π w ≠ b)    (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 hneg (x : V) (hx : x = a ∨ x = b) : A (Equiv.swap a b x) = !(A x) := by    rcases hx with hx | hx <;> rw [hx]    · cases ha : A a <;> cases hb : A b <;> simp [ha, hb] at hA ⊢    · cases ha : A a <;> cases hb : A b <;> simp [ha, hb] at 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 hdistinct : g₀ a ≠ g₀ b := fun hh => hab (g₀.injective hh)  have hdiff : A (g₀ a) ≠ A (g₀ b) := by    rcases hg₀a with ha | ha <;> rcases hg₀b with hb | hb    · exact False.elim (hdistinct (ha.trans hb.symm))    · simpa [ha, hb] using hA    · simpa [ha, hb] using Ne.symm hA    · exact False.elim (hdistinct (ha.trans hb.symm))  have ha₀ : A (g₀ a) = xor (B a) d₀ := by    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    simpa [hne, Ne.symm hπw.1] using h₀ a  have hb₀ : A (g₀ b) = xor (B b) d₀ := by    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    simpa [hne, Ne.symm hπw.2] using h₀ b  have hB : B a ≠ B b := by    intro he    apply hdiff    rw [ha₀, hb₀, he]  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 hga_ne : g a ≠ g b := fun hh => hab (g.injective hh)  have hπa : π a = a ∨ π a = b := by    by_contra hn    push_neg at hn    have ea := heq a    have eb := heq b    rcases hga with ha | ha <;> rcases hgb with hb | hb    · exact hga_ne (ha.trans hb.symm)    · simp only [ha, hb, hab, Ne.symm hab, decide_true, decide_false,        Ne.symm hn.1, Ne.symm hn.2, Bool.xor_false] at ea eb      cases hAa : A a <;> cases hAb : A b <;> cases hBa : B a <;>        cases hBb : B b <;> cases hd : d <;>          simp [hAa, hAb, hBa, hBb, hd] at hA hB ea eb    · simp only [ha, hb, hab, Ne.symm hab, decide_true, decide_false,        Ne.symm hn.1, Ne.symm hn.2, Bool.xor_false] at ea eb      cases hAa : A a <;> cases hAb : A b <;> cases hBa : B a <;>        cases hBb : B b <;> cases hd : d <;>          simp [hAa, hAb, hBa, hBb, hd] at hA hB ea eb    · exact hga_ne (ha.trans hb.symm)  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 hequiv (x : V) : (g x = a) ↔ x = q := by    constructor    · intro h      exact g.injective (h.trans hgq.symm)    · intro h      rw [h, hgq]  by_cases hmatch : q = π a  · refine ⟨g, hg, d, ?_⟩    intro x    have hx := heq x    rw [show decide (g x = a) = decide (x = π a) by simp only [hequiv, hmatch]] at hx    exact xor_cancel_flip _ _ _ _ hx  · let g' : Equiv.Perm V := g.trans (Equiv.swap a b)    have hg' : P g' := hswap g hg    refine ⟨g', hg', d, ?_⟩    intro x    by_cases hx : x = a ∨ x = b    · have hgx : g x = a ∨ g x = b := (hinv g hg x).mp hx      have hcomp : (x = q) ↔ x ≠ π a := by        rcases hq with hq | hq <;> rcases hπa with hp | hp <;>          rcases hx with hx | hx <;>          simp [hq, hp, hx, hab, Ne.symm hab] at hmatch ⊢      have hdec : decide (g x = a) = !(decide (x = π a)) := by        by_cases he : x = π a        · have hnot : x ≠ q := by            intro h            exact (hcomp.mp h) he          have hga : g x ≠ a := fun h => hnot ((hequiv x).mp h)          subst x          simp [hga]        · have hxq : x = q := hcomp.mpr he          have hga : g x = a := (hequiv x).mpr hxq          simp [hga, he]      have he := heq x      rw [hdec] at he      change A (Equiv.swap a b (g x)) = xor (B x) d      rw [hneg (g x) hgx]      cases ha : A (g x) <;> cases hb : B x <;> cases hc : d <;>        cases hd : decide (x = π a) <;> simp [ha, hb, hc, hd] at he ⊢    · have hgx : ¬(g x = a ∨ g x = b) := fun h => hx ((hinv g hg x).mpr h)      have hxa : g x ≠ a := fun h => hgx (Or.inl h)      have hxb : g x ≠ b := fun h => hgx (Or.inr h)      have hxp : x ≠ π a := by intro h; apply hx; rw [h]; exact hπa      change A (Equiv.swap a b (g x)) = xor (B x) d      rw [Equiv.swap_apply_of_ne_of_ne hxa hxb]      simpa [hxa, hxp] using heq xend OP1525MixedTwinPair#print axioms OP1525MixedTwinPair.reconstructopen OP1525Bridgetheorem signed_graph_reconstructible_balanced_mixed_twin_pair {V : Type*} [DecidableEq V] [Fintype V]    (G : SignedGraph V) (hconn : G.graph.Connected)    (A B : Finset V) (hbal : G.IsBalancedPartition A B)    (a b : V) (hab : a ≠ b) (hsize : Fintype.card V ≥ 5)    (hmixed : (a ∈ A ∧ b ∉ A) ∨ (a ∉ A ∧ b ∈ A))    (hinv : ∀ g : G.graph ≃g G.graph, ∀ x, (x = a ∨ x = b) ↔ (g x = a ∨ g x = b))    (τ : G.graph ≃g G.graph) (hτ : τ.toEquiv = Equiv.swap a b) : 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 hswap : ∀ p, P p → P (p.trans (Equiv.swap a b)) := by    intro p hp    obtain ⟨g, rfl⟩ := hp    refine ⟨g.trans τ, ?_⟩    change g.toEquiv.trans τ.toEquiv = _    rw [hτ]  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}  let bad : Finset V := anchors ∪ anchors.image π.symm  have ha : anchors.card ≤ 2 := Finset.card_le_two  have hb : bad.card ≤ 4 := 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 := by    have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h)    simpa [anchors] using h  have hvp : π v ≠ a ∧ π v ≠ b := 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    rcases hmixed with h | h <;> simp [OP1525Bridge.color, h.1, h.2]  obtain ⟨p, ⟨g, rfl⟩, d, hd⟩ := OP1525MixedTwinPair.reconstruct    (OP1525Bridge.color A) F P a b hab hA hp hswap π v hvn hvp hmatch  exact hlift g d hd
See it in the graphDiscuss this resultChallenge it