AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_dominating_univ

theoremverified

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.

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

    line 4

      intro v
  2. The 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.

    line 5

    uses Or.inl, Set.mem_univ

      exact 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

/-- 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)
See it in the graphDiscuss this resultChallenge it