AFTD Auto-Formalizing Theoretical Domains

is_good_set_for_edge

def

For vertices u and v, a finite subset S disjoint from {u, v} is a good set for the edge uv with parameter k if |S| ≥ k, the number of odd components of (G - uv)[Sᶜ] is |S| - k + 2, and u and v lie in distinct odd connected components of (G - uv)[Sᶜ].

Statement

def is_good_set_for_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (u v : V) (S : Finset V) (k : ℕ) : Prop
Defined in
arXiv:2611.09072, Section 1
Verified
09 Nov 2026
Axioms
none listed
Used by 1
  • is_type_ii_edgeAn edge uv of a simple graph G is a type II edge with parameter k if u is adjacent to v, there exists a good set S for uv of cardinality k…

Read back from the Lean

Given a finite type V, a simple graph G on V, two vertices u, v : V, a finite set of vertices S : Finset V, and a natural number k : ℕ, is_good_set_for_edge G u v S k asserts that: 1. u ∉ S, 2. v ∉ S, 3. k ≤ S.card, and 4. there exist proofs hu : u ∉ S and hv : v ∉ S such that, if H is the subgraph of G with the edge {u, v} removed and induced on the complement (S : Set V)ᶜ, then: - the number of odd connected components of H (H.oddComponents.ncard) equals S.card - k + 2, - the connected component of H containing ⟨u, hu⟩ is an odd component, - the connected component of H containing ⟨v, hv⟩ is an odd component, and - the connected component of H containing ⟨u, hu⟩ is not equal to the connected component of H containing ⟨v, hv⟩ (i.e., u and v belong to different connected components in H).

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 subset S disjoint from {u,v} is a good set for an edge uv with parameter k if |S| ≥ k, c_o(G - S - uv) = |S| - k + 2, and u and v lie in distinct odd components of G - S - uv. -/
def is_good_set_for_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (u v : V) (S : Finset V) (k : ℕ) : Prop := u ∉ S ∧ v ∉ S ∧ k ≤ S.card ∧
    ∃ (hu : u ∉ S) (hv : v ∉ S),
      let H := (G.deleteEdges {s(u, v)}).induce (S : Set V)ᶜ
      H.oddComponents.ncard = S.card - k + 2 ∧
      H.connectedComponentMk ⟨u, hu⟩ ∈ H.oddComponents ∧
      H.connectedComponentMk ⟨v, hv⟩ ∈ H.oddComponents ∧
      H.connectedComponentMk ⟨u, hu⟩ ≠ H.connectedComponentMk ⟨v, hv⟩
See it in the graphDiscuss this resultChallenge it