signed_graph_reconstructible_balanced_three_fixed
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.
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.
cases a <;> cases b <;> cases c <;> decide
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.
cases a <;> cases b <;> cases c <;> decide
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.
uses
Finset.card_union_le,Finset.card_image_le,congrArg,Finset.card_univclassical 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
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.
uses
Finset.mem_union_left,Finset.mem_union_right,Finset.mem_image.mprhave 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
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.
uses
op1525_bool_xor_commonobtain ⟨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 _ _ _
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.
uses
Ne.symmobtain ⟨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)
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.
uses
op1525_bool_xor_cancel_fliprefine ⟨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
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.
uses
SignedGraph.IsReconstructible,OP1525Bridge.deck_color_model,OP1525Bridge.flippedclassical 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
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.
uses
OP1525ThreePoly.op1525_three_fixed_points_reconstructobtain ⟨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.
- The boolean lemmas (op1525_bool_xor_common, op1525_bool_xor_cancel_flip) and the contradiction branches ruling out π(r) = s and π(r) = t rely on exhaustive truth-table checking over Bool handled by the decide and simp tactics.
- The bridge lemma OP1525Bridge.deck_color_model translates the graph-theoretic switching deck isomorphism into an equivalent Boolean coloring model on the vertex set.
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.
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