AFTD Auto-Formalizing Theoretical Domains

simple_graph_V3_bot

theoremverified

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.

  1. 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.

    line 4

      ext v
  2. No 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.

    line 5

    uses simple_graph_V3

      simp [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

/-- 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]
See it in the graphDiscuss this resultChallenge it