AFTD Auto-Formalizing Theoretical Domains

SignedGraph.IsBalancedPartition

def

A 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 endpoints both lie in A or both lie in B has sign 1, and every edge with one endpoint in A and one in B has sign -1.

Statement

def SignedGraph.IsBalancedPartition {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (A B : Finset V) : Prop
Defined in
arXiv:2611.13901, Sec. 2.1 and Sec. 4.1
Verified
11 Nov 2026
Axioms
none listed
Built on 1
  • 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}.
Used by 5

Read back from the Lean

Given a finite type $V$ with decidable equality, a signed graph $G$ on $V$ (a simple graph with an edge-weight function into $\{-1, 1\}$), and two finite subsets $A, B \subseteq V$, SignedGraph.IsBalancedPartition G A B asserts that: 1. $A$ and $B$ partition the vertex set $V$, meaning $A \cup B = V$ and $A \cap B = \emptyset$ (Disjoint A B); 2. For every pair of vertices $u, v \in V$ adjacent in $G$, - if both $u, v \in A$ or both $u, v \in B$, then the sign of the edge $\{u, v\}$ is $1$; - if one of $u, v$ is in $A$ and the other is in $B$, then the sign of the edge $\{u, v\}$ is $-1$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A bipartition of vertices where internal edges are positive and cross edges are negative. -/
def SignedGraph.IsBalancedPartition {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (A B : Finset V) : Prop :=
  (A ∪ B = Finset.univ) ∧ Disjoint A B ∧
  (∀ (u v : V) (h : G.graph.Adj u v),
    ((u ∈ A ∧ v ∈ A) ∨ (u ∈ B ∧ v ∈ B) → G.sgn ⟨s(u, v), h⟩ = 1) ∧
    ((u ∈ A ∧ v ∈ B) ∨ (u ∈ B ∧ v ∈ A) → G.sgn ⟨s(u, v), h⟩ = -1))
See it in the graphDiscuss this resultChallenge it