simple_graph_V3_bot
In the empty simple graph on a finite type V with decidable equality, the finset of vertices of degree 3 is the empty finset.
Statement
theorem simple_graph_V3_bot {V : Type*} [Fintype V] [DecidableEq V] : simple_graph_V3 (⊥ : SimpleGraph V) = ∅
- Source
- folklore
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_V3For a finite type V with decidable equality and a simple graph G on V with decidable adjacency, simple_graph_V3 G is the finset of all…
Read back from the Lean
For any finite type V with decidable equality, the set of vertices having degree 3 in the empty simple graph on V (the graph with no edges, ⊥) is empty (equal to ∅ : Finset V).
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 theorem states that in an empty graph, the set of vertices of degree 3 is empty. By set extensionality, this reduces to showing that no vertex belongs to this set, which holds because every vertex in the empty graph has degree 0 rather than 3.
To show equality of the two finsets, it suffices to show that any vertex v is an element of simple_graph_V3 ⊥ if and only if v ∈ ∅.
By set extensionality (`ext v`), two finsets are equal if and only if they contain the exact same elements.
ext vNo vertex has degree 3 in the empty graph, so both sides of the membership condition are false.
Unfolding the definition of `simple_graph_V3`, a vertex v is in the set if and only if its degree in the empty graph ⊥ is 3. In the empty graph, there are no edges, so every vertex has degree 0. Since 0 ≠ 3, the membership condition is false, matching v ∈ ∅, and the simplifier closes the equivalence.
uses
simple_graph_V3simp [simple_graph_V3]
simple_graph_V3- The finset of vertices in a graph G having degree 3, defined by filtering the universe of vertices on the condition G.degree v = 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
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.
/-- The set of degree-3 vertices of an empty graph is empty. -/theorem simple_graph_V3_bot {V : Type*} [Fintype V] [DecidableEq V] : simple_graph_V3 (⊥ : SimpleGraph V) = ∅ := by ext v simp [simple_graph_V3]