signed_graph_balanced_partition_unique_connected
Any two balance partitions of the same connected signed graph agree up to exchanging their two parts.
Statement
theorem signed_graph_balanced_partition_unique_connected {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (hconn : G.graph.Connected) (A B C D : Finset V) (hAB : G.IsBalancedPartition A B) (hCD : G.IsBalancedPartition C D) : (A = C ∧ B = D) ∨ (A = D ∧ B = C)
- Source
- Balance-partition uniqueness needed to transfer the three-fixed-point subset theorem to signed graphs; see arXiv:2611.13901, Proposition 4.2.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- Used by 2
- 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…
- 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…
The proof, explained
A balanced partition of a signed graph partitions the vertex set into two complementary subsets such that the sign of every edge u ~ v is 1 when its endpoints lie in the same subset and -1 when they lie in different subsets. Expressing partition membership via Boolean colorings c_A and c_C, the edge signs enforce that c_A(u) ⊕ c_A(v) = c_C(u) ⊕ c_C(v) across all edges. Because the graph is connected, this edge-wise agreement propagates along paths to show that c_A and c_C differ by a single global Boolean constant d. If d = false, the colorings match and A = C, B = D; if d = true, the colorings are complementary and A = D, B = C.
For Booleans a, b, c, d, the equation a ⊕ b = c ⊕ d implies a ⊕ c = b ⊕ d. automation
Exhaustively verified by evaluating all 16 combinations of Boolean truth values.
lemma 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 <;> decide
For Booleans a, b, c, the equation a ⊕ b = c implies a = b ⊕ c. automation
Exhaustively verified by evaluating all 8 combinations of Boolean truth values.
lemma bool_xor_solve (a b c : Bool) : xor a b = c → a = xor b c := by cases a <;> cases b <;> cases c <;> decide
If two Boolean vertex labelings have equal XOR differences across every edge, then a(r) ⊕ b(r) = a(x) ⊕ b(x) for any vertex x reachable along a path from r.
Pick a base vertex r in the nonempty vertex set. For each edge, bool_xor_square rearranges the hypothesis to show a(u) ⊕ b(u) = a(v) ⊕ b(v). By induction on paths (the reflexive-transitive closure of the edge relation), this equality propagates from r to any reachable vertex x.
uses
bool_xor_squarelemma 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)
On a connected graph, two Boolean vertex labelings with identical edge XOR differences differ globally by a constant Boolean value c = a(r) ⊕ b(r).
Because the graph is connected, every vertex x is reachable from the chosen root r. Applying bool_xor_solve to the path invariant a(r) ⊕ b(r) = a(x) ⊕ b(x) expresses a(x) as b(x) ⊕ (a(r) ⊕ b(r)).
uses
bool_xor_solve,SimpleGraph.reachable_iff_reflTransGenrefine ⟨xor (a r) (b r), ?_⟩ intro x exact bool_xor_solve _ _ _ (hpath x ((SimpleGraph.reachable_iff_reflTransGen r x).mp (hc r x))).symm
For any balanced partition (A, B) and edge u ~ v, the edge sign equals sign(color A u ⊕ color A v). automation
Since A and B partition V, every vertex not in A lies in B. Case analysis on whether u ∈ A and v ∈ A evaluates the XOR: when both endpoints are in the same part the XOR is false and the sign is 1; when they are in different parts the XOR is true and the sign is -1, which matches the definition of a balanced partition.
uses
Finset.mem_univ,Finset.mem_union.mp,Or.inl,Or.inrlemma 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⟩)
The sign function from Bool to ℤ is injective. automation
Verified by case analysis on both Boolean arguments: true maps to -1 and false maps to 1, which are distinct in ℤ.
lemma sign_injective {a b : Bool} (h : sign a = sign b) : a = b := by cases a <;> cases b <;> simp [sign] at h ⊢
The second components of the partitions are the set complements of the first: B = V \ A and D = V \ C.
For the balanced partition (A, B), the disjointness of A and B implies that any element of B is not in A, while A ∪ B = univ implies that any element not in A must lie in B. Hence B = univ \ A. The same argument applies to (C, D) to show D = univ \ C.
uses
Finset.mem_sdiff,Finset.mem_univ,true_and,Finset.disjoint_left.mp,Finset.mem_union.mptheorem signed_graph_balanced_partition_unique_connected {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (hconn : G.graph.Connected) (A B C D : Finset V) (hAB : G.IsBalancedPartition A B) (hCD : G.IsBalancedPartition C D) : (A = C ∧ B = D) ∨ (A = D ∧ B = C) := by classical have hBA : B = Finset.univ \ A := by ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] constructor · intro hxB hxA exact (Finset.disjoint_left.mp hAB.2.1) hxA hxB · intro hxA have hx : x ∈ A ∪ B := by rw [hAB.1]; exact Finset.mem_univ x exact (Finset.mem_union.mp hx).resolve_left hxA have hDC : D = Finset.univ \ C := by ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] constructor · intro hxD hxC exact (Finset.disjoint_left.mp hCD.2.1) hxC hxD · intro hxC have hx : x ∈ C ∪ D := by rw [hCD.1]; exact Finset.mem_univ x exact (Finset.mem_union.mp hx).resolve_left hxC
For every edge u ~ v, the XOR of the endpoint colors under partition A equals the XOR under partition C.
By balanced_sign, the sign of edge (u, v) is equal to sign(color A u ⊕ color A v) and also equal to sign(color C u ⊕ color C v). Since sign is injective, the two Boolean XOR values must be equal.
uses
sign_injective,balanced_signhave he : ∀ u v, G.graph.Adj u v → xor (OP1525Unique.color A u) (OP1525Unique.color A v) = xor (OP1525Unique.color C u) (OP1525Unique.color C v) := by intro u v h apply sign_injective exact (balanced_sign G A B hAB u v h).symm.trans (balanced_sign G C D hCD u v h)
The colorings differ by a global constant d; if d = false, then A = C and B = D.
Applying connected_labels to the connected graph and the edge-wise XOR agreement yields a constant d ∈ Bool such that color A x = color C x ⊕ d for all x. When d = false, color A x = color C x everywhere, which means x ∈ A ↔ x ∈ C, so A = C. Substituting into B = univ \ A and D = univ \ C gives B = D.
uses
connected_labelsobtain ⟨d, hd⟩ := connected_labels G.graph hconn (OP1525Unique.color A) (OP1525Unique.color C) he cases d with | false => have hAC : A = C := by ext x have hx := hd x by_cases hxA : x ∈ A <;> by_cases hxC : x ∈ C <;> simp [OP1525Unique.color, hxA, hxC] at hx ⊢ left exact ⟨hAC, by rw [hBA, hDC, hAC]⟩
If d = true, then the partitions are swapped: A = D and B = C.
When d = true, color A x = color C x ⊕ true = ¬(color C x) everywhere. Thus x ∈ A ↔ x ∉ C, which means A = univ \ C = D. Similarly, x ∈ B ↔ x ∉ A ↔ x ∈ C, which shows B = C. Together with the d = false case, this proves (A = C ∧ B = D) ∨ (A = D ∧ B = C).
uses
Finset.mem_sdiff,Finset.mem_univ,true_and,Or.inr| true => have hAD : A = D := by rw [hDC] ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] have hx := hd x by_cases hxA : x ∈ A <;> by_cases hxC : x ∈ C <;> simp [OP1525Unique.color, hxA, hxC] at hx ⊢ have hBC : B = C := by rw [hBA] ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] have hx := hd x by_cases hxA : x ∈ A <;> by_cases hxC : x ∈ C <;> simp [OP1525Unique.color, hxA, hxC] at hx ⊢ exact Or.inr ⟨hAD, hBC⟩
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.
SimpleGraph.reachable_iff_reflTransGen- In a graph, vertex v is reachable from vertex u if and only if they are related by the reflexive-transitive closure of the adjacency relation.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set Finset.univ.
Finset.mem_union.mp- If an element belongs to the union s ∪ t, then it belongs to s or it belongs to t.
Or.inl- Constructs a proof of a ∨ b from a proof of the left disjunct a.
Or.inr- Constructs a proof of a ∨ b from a proof of the right disjunct b.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and does not belong to t.
true_and- The logical proposition True ∧ p simplifies to p.
Finset.disjoint_left.mp- If two finite sets are disjoint, any element of the first set does not belong to the second set.
sign_injective- The sign function mapping Bool to ℤ is injective: sign a = sign b implies a = b.
balanced_sign- In a signed graph with balanced partition (A, B), the sign of an edge (u, v) equals sign(color A u ⊕ color A v).
connected_labels- On a connected graph, if two Boolean vertex labelings have identical XOR differences across every edge, they differ globally by a single constant Boolean value.
- The Boolean identities bool_xor_square and bool_xor_solve, as well as the injectivity of sign, are proved by Lean's decide and simp automation via exhaustive truth-table case analysis.
- The proof represents the two parts of each partition via Boolean indicator functions (color), converting the signed graph balance conditions into XOR equations over Bool.
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 OP1525Uniquelemma 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⟩)lemma sign_injective {a b : Bool} (h : sign a = sign b) : a = b := by cases a <;> cases b <;> simp [sign] at h ⊢end OP1525Uniqueopen OP1525Uniquetheorem signed_graph_balanced_partition_unique_connected {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (hconn : G.graph.Connected) (A B C D : Finset V) (hAB : G.IsBalancedPartition A B) (hCD : G.IsBalancedPartition C D) : (A = C ∧ B = D) ∨ (A = D ∧ B = C) := by classical have hBA : B = Finset.univ \ A := by ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] constructor · intro hxB hxA exact (Finset.disjoint_left.mp hAB.2.1) hxA hxB · intro hxA have hx : x ∈ A ∪ B := by rw [hAB.1]; exact Finset.mem_univ x exact (Finset.mem_union.mp hx).resolve_left hxA have hDC : D = Finset.univ \ C := by ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] constructor · intro hxD hxC exact (Finset.disjoint_left.mp hCD.2.1) hxC hxD · intro hxC have hx : x ∈ C ∪ D := by rw [hCD.1]; exact Finset.mem_univ x exact (Finset.mem_union.mp hx).resolve_left hxC have he : ∀ u v, G.graph.Adj u v → xor (OP1525Unique.color A u) (OP1525Unique.color A v) = xor (OP1525Unique.color C u) (OP1525Unique.color C v) := by intro u v h apply sign_injective exact (balanced_sign G A B hAB u v h).symm.trans (balanced_sign G C D hCD u v h) obtain ⟨d, hd⟩ := connected_labels G.graph hconn (OP1525Unique.color A) (OP1525Unique.color C) he cases d with | false => have hAC : A = C := by ext x have hx := hd x by_cases hxA : x ∈ A <;> by_cases hxC : x ∈ C <;> simp [OP1525Unique.color, hxA, hxC] at hx ⊢ left exact ⟨hAC, by rw [hBA, hDC, hAC]⟩ | true => have hAD : A = D := by rw [hDC] ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] have hx := hd x by_cases hxA : x ∈ A <;> by_cases hxC : x ∈ C <;> simp [OP1525Unique.color, hxA, hxC] at hx ⊢ have hBC : B = C := by rw [hBA] ext x simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] have hx := hd x by_cases hxA : x ∈ A <;> by_cases hxC : x ∈ C <;> simp [OP1525Unique.color, hxA, hxC] at hx ⊢ exact Or.inr ⟨hAD, hBC⟩