simple_graph_regular_of_degree_iff_neighbor_card
A finite simple graph is regular of degree d if and only if every vertex has exactly d neighbours, counted as the cardinality of its neighbour finset.
Statement
theorem simple_graph_regular_of_degree_iff_neighbor_card {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (d : ℕ) : G.IsRegularOfDegree d ↔ ∀ v : V, (G.neighborFinset v).card = d
- Source
- step towards exists_nonempty_regular_eight_triangle_distinct
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- eight_regular_triangle_distinct_of_certificateIf the computable certificate checker accepts the edge list L on the n vertices {0,…,n−1}, then the graph of L is 8-regular and has…
The proof, explained
The theorem establishes that a finite simple graph is regular of degree d if and only if every vertex has neighbour finset of cardinality d. By definition, d-regularity means that every vertex has degree d. Rewriting this definition using the identity that the degree of a vertex equals the cardinality of its neighbour finset immediately proves the equivalence.
The graph G is d-regular if and only if every vertex has exactly d neighbours in its neighbour finset.
By definition (SimpleGraph.IsRegularOfDegree), G is regular of degree d precisely when G.degree v = d for all vertices v. By SimpleGraph.card_neighborFinset_eq_degree, the degree of v equals the cardinality of its neighbour finset (G.neighborFinset v).card. Rewriting with these two facts simplifies the equivalence to an identity.
uses
SimpleGraph.IsRegularOfDegree,SimpleGraph.card_neighborFinset_eq_degreesimp_rw [SimpleGraph.IsRegularOfDegree, SimpleGraph.card_neighborFinset_eq_degree]
SimpleGraph.IsRegularOfDegree- A graph is regular of degree d if and only if every vertex v has degree(v) = d.
SimpleGraph.card_neighborFinset_eq_degree- For any vertex v in a locally finite graph, the cardinality of its neighbour finset equals its degree.
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.
/-- Regularity of a finite graph is decided by the cardinalities of its neighbour finsets. -/theorem simple_graph_regular_of_degree_iff_neighbor_card {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (d : ℕ) : G.IsRegularOfDegree d ↔ ∀ v : V, (G.neighborFinset v).card = d := by simp_rw [SimpleGraph.IsRegularOfDegree, SimpleGraph.card_neighborFinset_eq_degree]