AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_perfect_dominating_fin1

theoremverified

In the edgeless graph on one vertex, the singleton vertex set is a perfect dominating set.

Statement

theorem simple_graph_is_perfect_dominating_fin1 :
    simple_graph_is_perfect_dominating (⊥ : SimpleGraph (Fin 1)) {0}
Source
arXiv:2611.11191, Section 2
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

For the empty simple graph on the single-vertex type Fin 1 (the graph with no edges, ⊥), the set {0} is a perfect dominating set: for every vertex v : Fin 1, there exists a unique u ∈ ({0} : Set (Fin 1)) such that either v is adjacent to u in ⊥ or v = u.

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 singleton set $\{0\}$ is a perfect dominating set in the empty graph on the single vertex of $\mathrm{Fin}\;1$, we unfold the definition of a perfect dominating set. Since there is only one vertex $0$ in the entire graph, $0 \in \{0\}$ and $0 = 0$ uniquely and trivially satisfy the closed neighborhood requirement, which is discharged by the simplifier.

  1. In the edgeless graph on $\mathrm{Fin}\;1$, $\{0\}$ is a perfect dominating set. automation

    Unfolding the definition of a perfect dominating set with `simp only [simple_graph_is_perfect_dominating] at *`, the goal becomes showing that for every vertex $v \in \mathrm{Fin}\;1$, there is a unique $u \in \{0\}$ such that $v$ is adjacent to $u$ or $v = u$. Since $\mathrm{Fin}\;1$ consists solely of the single vertex $0$, the only possibility is $v = 0$ and $u = 0$, for which $v = u$ holds reflexively. Lean's simplifier (`simpa`) evaluates the conditions on this singleton domain and finishes the proof automatically.

    line 3

    uses simple_graph_is_perfect_dominating, simple_graph_triangle_degree_complete_fin_four

        simple_graph_is_perfect_dominating (⊥ : SimpleGraph (Fin 1)) {0} := by first | exact simple_graph_triangle_degree_complete_fin_four | (apply simple_graph_triangle_degree_complete_fin_four <;> assumption) | (apply simple_graph_triangle_degree_complete_fin_four <;> simp_all) | simpa using simple_graph_triangle_degree_complete_fin_four | (simp only [simple_graph_is_perfect_dominating] at *; first | exact simple_graph_triangle_degree_complete_fin_four | (apply simple_graph_triangle_degree_complete_fin_four <;> assumption) | (apply simple_graph_triangle_degree_complete_fin_four <;> simp_all) | simpa using simple_graph_triangle_degree_complete_fin_four)
simple_graph_is_perfect_dominating
A set of vertices $D$ in a graph $G$ is a perfect dominating set if every vertex $v$ has a unique element of $D$ in its closed neighborhood, meaning $\exists! u \in D, G.\mathrm{Adj}\;v\;u \lor v = u$.
simple_graph_triangle_degree_complete_fin_four
In the complete graph on four vertices, every vertex has triangle degree equal to 3.

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

/-- Sanity check: the singleton vertex set of a one-vertex graph is a perfect dominating set. -/theorem simple_graph_is_perfect_dominating_fin1 :    simple_graph_is_perfect_dominating (⊥ : SimpleGraph (Fin 1)) {0} := by first | exact simple_graph_triangle_degree_complete_fin_four | (apply simple_graph_triangle_degree_complete_fin_four <;> assumption) | (apply simple_graph_triangle_degree_complete_fin_four <;> simp_all) | simpa using simple_graph_triangle_degree_complete_fin_four | (simp only [simple_graph_is_perfect_dominating] at *; first | exact simple_graph_triangle_degree_complete_fin_four | (apply simple_graph_triangle_degree_complete_fin_four <;> assumption) | (apply simple_graph_triangle_degree_complete_fin_four <;> simp_all) | simpa using simple_graph_triangle_degree_complete_fin_four)
See it in the graphDiscuss this resultChallenge it