signed_graph_reconstructible_balanced_mixed_twin_pair
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.
reconstruct
expl
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
main theorem
expl
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open OP1525MonoPolynamespace 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