AFTD Auto-Formalizing Theoretical Domains

signed_graph_balanced_partition_unique_connected

theoremverified

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

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.

  1. 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.

    lines 3–4

    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
  2. 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.

    lines 6–7

    lemma bool_xor_solve (a b c : Bool) : xor a b = c → a = xor b c := by
      cases a <;> cases b <;> cases c <;> decide
  3. 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.

    lines 9–20

    uses bool_xor_square

    lemma 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)
  4. 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)).

    lines 21–23

    uses bool_xor_solve, SimpleGraph.reachable_iff_reflTransGen

      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
  5. 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.

    lines 28–39

    uses Finset.mem_univ, Finset.mem_union.mp, Or.inl, Or.inr

    lemma 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⟩)
  6. 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 ℤ.

    lines 41–42

    lemma sign_injective {a b : Bool} (h : sign a = sign b) : a = b := by
      cases a <;> cases b <;> simp [sign] at h ⊢
  7. 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.

    lines 48–70

    uses Finset.mem_sdiff, Finset.mem_univ, true_and, Finset.disjoint_left.mp, Finset.mem_union.mp

    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) := 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
  8. 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.

    lines 71–76

    uses sign_injective, balanced_sign

      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)
  9. 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.

    lines 77–86

    uses connected_labels

      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]⟩
  10. 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).

    lines 87–102

    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.

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

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⟩
See it in the graphDiscuss this resultChallenge it