AFTD Auto-Formalizing Theoretical Domains

is_type_ii_edge

def

An 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 + 1, every good set for uv has cardinality at least k + 1, and for every good set S of cardinality k + 1, the graph (G - uv)[Sᶜ] has exactly 3 connected components, and the connected components containing u and v have supports equal to the singletons {u} and {v} respectively.

Statement

def is_type_ii_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (u v : V) (k : ℕ) : Prop
Defined in
arXiv:2611.09072, Lemma 2.8(ii)
Verified
09 Nov 2026
Axioms
none listed
Built on 1
  • is_good_set_for_edgeFor 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…

Read back from the Lean

Let V be a finite type, G be a simple graph on V, u, v : V, and k : ℕ. The predicate is_type_ii_edge G u v k asserts that all of the following hold: 1. u and v are adjacent in G (G.Adj u v); 2. There exists a finset S : Finset V such that S is a good set for the edge (u, v) with respect to k (is_good_set_for_edge G u v S k) and |S| = k + 1; 3. For every finset S : Finset V, if S is a good set for (u, v) with respect to k, then |S| ≥ k + 1 (meaning the minimum cardinality of any good set is k + 1); 4. For every finset S : Finset V, if S is a good set for (u, v) with respect to k and |S| = k + 1, then (since u ∉ S and v ∉ S), in the subgraph H of G induced on the complement V \ S after removing the edge {u, v}: - H has exactly 3 connected components (Nat.card H.ConnectedComponent = 3); - The connected component containing u in H consists solely of {u} (i.e., its vertex support is {⟨u, hu⟩}); - The connected component containing v in H consists solely of {v} (i.e., its vertex support is {⟨v, hv⟩}).

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

/-- An edge uv in G is a type II edge with parameter k if G.Adj u v, the minimum cardinality of any good set is k + 1, and every good set of cardinality k + 1 separates G - uv into 3 components, two being singletons {u} and {v}. -/
def is_type_ii_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (u v : V) (k : ℕ) : Prop := G.Adj u v ∧
  (∃ S : Finset V, is_good_set_for_edge G u v S k ∧ S.card = k + 1) ∧
  (∀ S : Finset V, is_good_set_for_edge G u v S k → k + 1 ≤ S.card) ∧
  (∀ S : Finset V, is_good_set_for_edge G u v S k → S.card = k + 1 →
    ∃ (hu : u ∉ S) (hv : v ∉ S),
      let H := (G.deleteEdges {s(u, v)}).induce (S : Set V)ᶜ
      Nat.card H.ConnectedComponent = 3 ∧
      (H.connectedComponentMk ⟨u, hu⟩).supp = {⟨u, hu⟩} ∧
      (H.connectedComponentMk ⟨v, hv⟩).supp = {⟨v, hv⟩})
See it in the graphDiscuss this resultChallenge it