AFTD Auto-Formalizing Theoretical Domains

not_simple_graph_vertex_dominated_of_isolated

theoremverified

An isolated vertex in a simple graph $H$ (a vertex with empty open neighbourhood) is not dominated by any vertex.

Statement

theorem not_simple_graph_vertex_dominated_of_isolated {V : Type*} (H : SimpleGraph V) (u : V)
    (hu : H.neighborSet u = ∅) :
    ¬ simple_graph_vertex_dominated H u
Source
scout/2611-14430-linear-size-graphs-at-every-strict-dismantling-level.md:237 (arXiv:2611.14430 Lemma 2.1)
Verified
13 Nov 2026
Axioms
propext
Built on 1
  • simple_graph_vertex_dominatedA vertex $v$ of a simple graph $H$ is dominated if there exists a vertex $t \neq v$ in $H$ such that the closed neighbourhood of $v$ is…

Read back from the Lean

For any type V, any simple graph H on V, and any vertex u : V, if the neighbor set of u in H is empty, then u is not vertex-dominated in H (there is no vertex t ≠ u whose closed neighborhood contains the closed neighborhood of 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

The proof is by contradiction. If an isolated vertex u were dominated by some vertex t ≠ u, the closed neighbourhood of u would be contained in that of t. Since u is in its own closed neighbourhood, it must be in the closed neighbourhood of t, meaning either u = t or u is adjacent to t. The first case contradicts t ≠ u, and the second implies by symmetry of adjacency that t is a neighbour of u, contradicting that u has no neighbours.

  1. It suffices to derive a contradiction assuming u is dominated by some vertex t.

    We proceed by contradiction: suppose u is dominated by a vertex t. By the definition of vertex domination, t ≠ u and the closed neighbourhood of u is a subset of the closed neighbourhood of t, that is, {u} ∪ N(u) ⊆ {t} ∪ N(t).

    line 5

      rintro ⟨t, htv, hsub⟩
  2. Either u = t or u is a neighbour of t.

    The vertex u is trivially in its own closed neighbourhood {u} ∪ N(u). By the neighbourhood inclusion, u must therefore belong to {t} ∪ N(t). Rewriting with `Set.mem_insert_iff` expresses this membership as the disjunction u = t ∨ u ∈ N(t).

    lines 6–7

    uses Set.mem_insert_iff

      have hmem : u ∈ insert t (H.neighborSet t) := hsub (by simp)
      rw [Set.mem_insert_iff] at hmem
  3. The case u = t is impossible.

    We split into cases on the disjunction. In the first case, u = t, which directly contradicts the assumption that t ≠ u.

    lines 8–9

      rcases hmem with h | h
      · exact htv h.symm
  4. The case u ∈ N(t) is impossible.

    In the second case, u is a neighbour of t, which by `SimpleGraph.mem_neighborSet` means t is adjacent to u. Simple graph adjacency is symmetric (`SimpleGraph.Adj.symm`), so u is adjacent to t, meaning t ∈ N(u). But u is isolated, so its neighbourhood N(u) is empty (hu), which leaves t ∈ ∅, an immediate contradiction.

    lines 10–14

    uses SimpleGraph.mem_neighborSet, SimpleGraph.Adj.symm

      · rw [SimpleGraph.mem_neighborSet] at h
        have h' : t ∈ H.neighborSet u := by
          rw [SimpleGraph.mem_neighborSet]; exact SimpleGraph.Adj.symm h
        rw [hu] at h'
        exact h'
Set.mem_insert_iff
An element x is in insert a s if and only if x = a or x ∈ s.
SimpleGraph.Adj.symm
The adjacency relation in a simple graph is symmetric: if u is adjacent to v, then v is adjacent to u.
SimpleGraph.mem_neighborSet
A vertex w belongs to the neighbourhood of v if and only if v and w are adjacent.

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

/-- An isolated vertex in a simple graph is not dominated by any vertex. -/theorem not_simple_graph_vertex_dominated_of_isolated {V : Type*} (H : SimpleGraph V) (u : V)    (hu : H.neighborSet u = ∅) :    ¬ simple_graph_vertex_dominated H u := by  rintro ⟨t, htv, hsub⟩  have hmem : u ∈ insert t (H.neighborSet t) := hsub (by simp)  rw [Set.mem_insert_iff] at hmem  rcases hmem with h | h  · exact htv h.symm  · rw [SimpleGraph.mem_neighborSet] at h    have h' : t ∈ H.neighborSet u := by      rw [SimpleGraph.mem_neighborSet]; exact SimpleGraph.Adj.symm h    rw [hu] at h'    exact h'
See it in the graphDiscuss this resultChallenge it