signed_graph_reconstructible_balanced_mono_invariant
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
LinearOrderis aTotalPreorder. - 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 thanLinearOrder— it does NOT require antisymmetry or…
- Used by 3
- signed_graph_reconstructible_balanced_mono_pair_fixedLet G be a connected balanced signed graph on at least seven vertices, with a specified balance partition. Suppose distinct vertices a and…
- signed_graph_reconstructible_balanced_three_fixedEvery connected balanced signed graph on at least seven vertices is reconstructible from its switching deck if its underlying graph has…
- signed_graph_reconstructible_balanced_mixed_twin_pairLet G be a connected balanced signed graph on at least five vertices, with a specified balance partition. Suppose distinct vertices a and…
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.
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.
cases x <;> cases y <;> cases c <;> decide
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.
cases a <;> cases b <;> cases c <;> cases d <;> decide
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.
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
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.
uses
fresh_of_threeobtain ⟨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
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.
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
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).
uses
xor_cancel_commonintro 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)
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.
uses
flip_outside_mono,transfer_mono,mono_of_two_flipshave 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
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).
uses
fresh_of_threeobtain ⟨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
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.
uses
xor_cancel_fliprefine ⟨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
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.
cases a <;> cases b <;> cases c <;> cases d <;> decide
For booleans a, b, c, if a ⊕ b = c then a = b ⊕ c. automation
Verified by exhaustive case analysis over all 8 boolean assignments.
cases a <;> cases b <;> cases c <;> decide
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).
uses
bool_xor_square,bool_xor_solveletI : 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
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.
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⟩)
The sign function mapping false to 1 and true to -1 is injective. automation
Follows from 1 ≠ -1 in the integers.
cases a <;> cases b <;> simp [sign] at h ⊢
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.
uses
balanced_signchange (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]
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.
cases a <;> cases b <;> decide
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.
cases a <;> cases b <;> decide
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.
uses
sign_flip_left,sign_flip_rightintro 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
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).
uses
sign_flip_left,sign_flip_rightintro 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]
For booleans a, b, c, (a ⊕ c) ⊕ (b ⊕ c) = a ⊕ b. automation
Verified by exhaustive case analysis on a, b, and c.
cases a <;> cases b <;> cases c <;> decide
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⁻¹.
uses
switched_sign,from_switched_isoclassical 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
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.
uses
sign_injective,switched_sign,to_switched_iso,connected_labelsrefine ⟨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⟩
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`.
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
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.
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]
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.
uses
deck_color_modelunfold 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
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.
uses
OP1525MonoPoly.reconstruct_of_invariant_monochromeobtain ⟨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.
- Several elementary boolean identities and finite case analyses (such as in `xor_cancel_common`, `xor_cancel_flip`, `fresh_of_three`, `bool_xor_square`, and `bool_xor_solve`) are closed automatically by `decide` and `aesop`.
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.
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