not_simple_graph_vertex_dominated_of_isolated
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.
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).
rintro ⟨t, htv, hsub⟩
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).
uses
Set.mem_insert_iffhave hmem : u ∈ insert t (H.neighborSet t) := hsub (by simp) rw [Set.mem_insert_iff] at hmem
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.
rcases hmem with h | h · exact htv h.symm
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.
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
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.
/-- 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'