alternating_path_selected_set_empty
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
- alternating_path_selected_setFor 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…
- simple_graph_is_dominating_univIn any simple graph G, the entire vertex set is a dominating set.
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.
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.
uses
alternating_path_selected_set,simple_graph_is_dominating_univalternating_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.
- The proof is written as a sequence of fallback alternatives using `first`. After unfolding `alternating_path_selected_set`, the goal is closed entirely by standard simplification (`simpa`), which simplifies the empty set union and vacuous quantification over `∅`; the lemma `simple_graph_is_dominating_univ` provided to `simpa` is unused.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)