alternating_path_selected_set
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
- alternating_path_selected_set_emptyFor a simple graph C on vertex type V, a vertex ρ : V, and a subset A of the subtype {ρ}ᶜ, alternating_path_selected_set C ρ A ∅ = A.
- cycle_alternating_path_selection_independentLet C be a simple graph on vertex type V and ρ : V a vertex such that (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B holds for subsets A, B…
- cycle_alternating_path_selection_isIndepSetLet C be a simple graph on vertex type V and ρ : V a vertex such that (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B holds for subsets A, B…
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}