AFTD Auto-Formalizing Theoretical Domains

alternating_path_selected_set

def

For a simple graph C on vertex type V, a vertex ρ : V, and subsets A and T of the subtype {ρ}ᶜ, alternating_path_selected_set C ρ A T is defined as the union of T and the set of vertices a ∈ A such that a is not adjacent to any vertex b ∈ T in the induced subgraph C.induce {ρ}ᶜ.

Statement

def alternating_path_selected_set {V : Type*} (C : SimpleGraph V) (ρ : V)
    (A : Set ({ρ}ᶜ : Set V)) (T : Set ({ρ}ᶜ : Set V)) : Set ({ρ}ᶜ : Set V)
Defined in
arXiv:2611.06985 Section 3.2, line 359
Verified
08 Nov 2026
Axioms
none listed
Used by 3

Read back from the Lean

Given an implicit type V, a simple graph C on vertex type V, a vertex ρ : V, and two subsets A and T of the subtype {ρ}ᶜ (the vertices in V not equal to ρ), alternating_path_selected_set C ρ A T is defined as the subset of {ρ}ᶜ given by the union of T and the set of all a ∈ A such that for every b ∈ T, a and b are not adjacent in the induced subgraph of C on {ρ}ᶜ (that is, a and b are not adjacent in C).

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

/-- The vertex set S selected by choosing T ⊆ B and all vertices in A with no neighbor in T. -/
def alternating_path_selected_set {V : Type*} (C : SimpleGraph V) (ρ : V)
    (A : Set ({ρ}ᶜ : Set V)) (T : Set ({ρ}ᶜ : Set V)) : Set ({ρ}ᶜ : Set V) := T ∪ {a ∈ A | ∀ b ∈ T, ¬ (C.induce ({ρ}ᶜ : Set V)).Adj a b}
See it in the graphDiscuss this resultChallenge it