simple_graph_is_dominating_univ
In any simple graph G, the entire vertex set is a dominating set.
Statement
theorem simple_graph_is_dominating_univ {V : Type*} (G : SimpleGraph V) : simple_graph_is_dominating G Set.univ
- Source
- folklore
- Verified
- 26 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- simple_graph_is_dominatingA subset S of vertices in a simple graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S.
- Used by 1
- 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.
Read back from the Lean
For every type V and every simple graph G on V, the universal set Set.univ is a dominating set of G.
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
To show that the universal vertex set is dominating, we check that every vertex v satisfies the domination condition: it belongs to the set or is adjacent to a vertex in the set. Since every vertex trivially belongs to the universal set, the condition holds by the first alternative of the disjunction.
Let v be an arbitrary vertex in V.
By definition, a set S is dominating in G if every vertex v satisfies v ∈ S ∨ ∃ u ∈ S, G.Adj u v. Introducing v sets up this check for an arbitrary vertex.
intro vThe domination condition holds for v because v belongs to Set.univ.
Every element of a type belongs to Set.univ by Set.mem_univ. Applying Or.inl establishes the left branch of the disjunction v ∈ Set.univ ∨ ∃ u ∈ Set.univ, G.Adj u v, completing the proof.
uses
Or.inl,Set.mem_univexact Or.inl (Set.mem_univ v)
Or.inl- constructs a proof of the disjunction a ∨ b from a proof of the left disjunct a
Set.mem_univ- every element x of a type α belongs to the universal set Set.univ
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.
/-- The universal set of vertices is a dominating set. -/theorem simple_graph_is_dominating_univ {V : Type*} (G : SimpleGraph V) : simple_graph_is_dominating G Set.univ := by intro v exact Or.inl (Set.mem_univ v)