simple_graph_vertex_dominated_complete_two
In the complete graph on two vertices, vertex 0 is dominated.
Statement
theorem simple_graph_vertex_dominated_complete_two :
simple_graph_vertex_dominated (⊤ : SimpleGraph (Fin 2)) (0 : Fin 2)- Source
- arXiv:2611.14430 Section 2
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- 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
In the complete simple graph on the vertex set Fin 2, the vertex 0 is dominated; that is, there exists a vertex t : Fin 2 such that t ≠ 0 and the closed neighborhood of 0 (the set formed by inserting 0 into the neighbor set of 0) is a subset of the closed neighborhood of t (the set formed by inserting t into the neighbor set of t).
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 vertex 0 is dominated in the complete graph on two vertices, we exhibit vertex 1 as the dominating vertex. Vertex 1 is distinct from vertex 0, and in a complete graph on two vertices, the closed neighborhood of vertex 1 contains all vertices of the graph, so it trivially contains the closed neighborhood of vertex 0. The proof verifies this by checking each of the two vertices 0 and 1.
Vertex 1 is chosen as the dominating vertex, reducing the goal to showing that the closed neighborhood of vertex 0 is contained in the closed neighborhood of vertex 1.
We provide vertex 1 as the witness for the existential quantifier in the definition of domination (`use 1`). We must then show that 1 ≠ 0 and that the closed neighborhood of 0 is a subset of the closed neighborhood of 1. The inequality 1 ≠ 0 is proved by finite evaluation (`decide`), leaving only the subset inclusion.
use 1 refine ⟨by decide, ?_⟩
To prove the inclusion, it suffices to check the two possible vertices, 0 and 1.
We take an arbitrary vertex x assumed to lie in the closed neighborhood of 0 (`intro x _`). Because the vertex type is Fin 2, we exhaustively split into two cases: x = 0 and x = 1 (`fin_cases x`).
intro x _ fin_cases xVertex 0 belongs to the closed neighborhood of vertex 1.
In the case x = 0, we must show 0 ∈ {1} ∪ N(1). Choosing the right alternative (`right`) leaves the goal of showing that 0 is adjacent to 1 in the complete graph (0 ∈ N(1)). In the complete graph ⊤, distinct vertices are connected by an edge; simplifying this condition reduces to 0 ≠ 1 and closes the goal (`simp`).
· right simp
Vertex 1 belongs to the closed neighborhood of vertex 1.
In the case x = 1, we must show 1 ∈ {1} ∪ N(1). Choosing the left alternative (`left`) leaves the equality 1 = 1, which holds by reflexivity (`rfl`).
· left rfl
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.
/-- In the complete graph on two vertices, vertex 0 is dominated by vertex 1. -/theorem simple_graph_vertex_dominated_complete_two : simple_graph_vertex_dominated (⊤ : SimpleGraph (Fin 2)) (0 : Fin 2) := by use 1 refine ⟨by decide, ?_⟩ intro x _ fin_cases x · right simp · left rfl