AFTD Auto-Formalizing Theoretical Domains

alternating_path_selected_set_empty

theoremverified

For 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.

Statement

theorem alternating_path_selected_set_empty {V : Type*} (C : SimpleGraph V) (ρ : V)
    (A : Set ({ρ}ᶜ : Set V)) :
    alternating_path_selected_set C ρ A ∅ = A
Source
arXiv:2611.06985 Section 3.2
Verified
09 Nov 2026
Axioms
Quot.soundpropext
Built on 2

Read back from the Lean

For any type V, any simple graph C on V, any vertex ρ : V, and any subset A of the subtype {ρ}ᶜ (the vertices in V other than ρ), the set alternating_path_selected_set C ρ A ∅ is equal to A.

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

The proof, explained

By definition, the alternating path selected set for a given subset T is the union of T and the vertices in A that have no neighbors in T. When T is the empty set, the condition that a vertex has no neighbors in T is vacuously satisfied by every element of A, so the set comprehension simplifies to A, and the union ∅ ∪ A is just A.

  1. The alternating path selected set for T = ∅ equals A, that is, alternating_path_selected_set C ρ A ∅ = A. automation

    Unfolding the definition of alternating_path_selected_set rewrites the left-hand side to ∅ ∪ {a ∈ A | ∀ b ∈ ∅, ¬(C.induce {ρ}ᶜ).Adj a b}. Since the condition ∀ b ∈ ∅, ... is vacuously true, the set comprehension reduces to A, and the union of the empty set with A is simply A. The simpa tactic finishes the proof by evaluating these set-theoretic simplifications.

    line 4

    uses alternating_path_selected_set, simple_graph_is_dominating_univ

        alternating_path_selected_set C ρ A ∅ = A := by first | exact simple_graph_is_dominating_univ | (apply simple_graph_is_dominating_univ <;> assumption) | (apply simple_graph_is_dominating_univ <;> simp_all) | simpa using simple_graph_is_dominating_univ | (simp only [alternating_path_selected_set] at *; first | exact simple_graph_is_dominating_univ | (apply simple_graph_is_dominating_univ <;> assumption) | (apply simple_graph_is_dominating_univ <;> simp_all) | simpa using simple_graph_is_dominating_univ)
alternating_path_selected_set
The alternating path selected set for graph C, root vertex ρ, and subsets A and T of {ρ}ᶜ is defined as the union of T and the set of vertices in A having no neighbor in T within the induced subgraph on {ρ}ᶜ.
simple_graph_is_dominating_univ
In any simple graph G, the universal set of all vertices Set.univ is a dominating set.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- When T is empty, the alternating path selected set equals A. -/theorem alternating_path_selected_set_empty {V : Type*} (C : SimpleGraph V) (ρ : V)    (A : Set ({ρ}ᶜ : Set V)) :    alternating_path_selected_set C ρ A ∅ = A := by first | exact simple_graph_is_dominating_univ | (apply simple_graph_is_dominating_univ <;> assumption) | (apply simple_graph_is_dominating_univ <;> simp_all) | simpa using simple_graph_is_dominating_univ | (simp only [alternating_path_selected_set] at *; first | exact simple_graph_is_dominating_univ | (apply simple_graph_is_dominating_univ <;> assumption) | (apply simple_graph_is_dominating_univ <;> simp_all) | simpa using simple_graph_is_dominating_univ)
See it in the graphDiscuss this resultChallenge it