regular_graph_compl_regular_iff
Let G be a simple graph on a finite vertex set V with cardinality n. If d + 1 ≤ n, then G is d-regular if and only if its complement Gᶜ is (n - 1 - d)-regular.
Statement
open scoped Classical in theorem regular_graph_compl_regular_iff {V : Type*} [Fintype V] (d : ℕ) (hn : d + 1 ≤ Fintype.card V) (G : SimpleGraph V) : G.IsRegularOfDegree d ↔ Gᶜ.IsRegularOfDegree (Fintype.card V - 1 - d)
- Source
- step towards regular_graph_lap_trace_minimal_iff_compl_adj_trace_minimal
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_endpoint_sum_edges_subsetFor any finite simple graph G, vertex labeling φ : V → ℕ, and natural number r, the finset simple_graph_endpoint_sum_edges G φ r is a…
The proof, explained
To show that a simple graph G on n vertices is d-regular if and only if its complement Gᶜ is (n - 1 - d)-regular, the proof splits the equivalence into two implications. The forward direction applies the library theorem that the complement of a d-regular graph is (n - 1 - d)-regular. For the reverse direction, assuming Gᶜ is (n - 1 - d)-regular, the complement degree identity expresses each vertex degree as n - 1 - deg_G(v) = n - 1 - d; since vertex degrees and d are strictly bounded by n, linear integer arithmetic cancels n - 1 to conclude deg_G(v) = d.
The forward direction holds: if G is d-regular, then its complement Gᶜ is (|V| - 1 - d)-regular.
To prove the "if and only if" statement, we split into two directions. In the forward direction, assuming G is d-regular, the regularity of the complement graph Gᶜ with degree |V| - 1 - d follows directly from the library result for complement graphs (applied as h.compl).
constructor · intro h exact h.compl
Assuming Gᶜ is (|V| - 1 - d)-regular, every vertex v satisfies |V| - 1 - deg_G(v) = |V| - 1 - d.
For the reverse direction, assume Gᶜ is (|V| - 1 - d)-regular and consider any vertex v. By definition of regularity, the degree of v in Gᶜ is |V| - 1 - d. Rewriting this degree using SimpleGraph.degree_compl yields |V| - 1 - deg_G(v) = |V| - 1 - d.
uses
SimpleGraph.degree_compl· intro h v have hv := h v rw [SimpleGraph.degree_compl] at hv
The degree of every vertex v in G equals d, so G is d-regular.
By SimpleGraph.degree_lt_card_verts, the degree of v in G is strictly less than |V|. Combining this upper bound with the hypothesis d + 1 ≤ |V| and the equality |V| - 1 - deg_G(v) = |V| - 1 - d, linear arithmetic on natural numbers (handled by omega) cancels the subtracted terms to conclude deg_G(v) = d.
uses
SimpleGraph.degree_lt_card_vertshave hdeg := SimpleGraph.degree_lt_card_verts (G := G) v omega
SimpleGraph.degree_compl- In a finite simple graph G, the degree of any vertex v in the complement graph Gᶜ equals |V| - 1 - deg_G(v).
SimpleGraph.degree_lt_card_verts- In a finite simple graph G, the degree of any vertex v is strictly less than the number of vertices |V|.
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.
open scoped Classical in/-- A simple graph G on n vertices is d-regular if and only if its complement Gᶜ is (n - 1 - d)-regular. -/theorem regular_graph_compl_regular_iff {V : Type*} [Fintype V] (d : ℕ) (hn : d + 1 ≤ Fintype.card V) (G : SimpleGraph V) : G.IsRegularOfDegree d ↔ Gᶜ.IsRegularOfDegree (Fintype.card V - 1 - d) := by constructor · intro h exact h.compl · intro h v have hv := h v rw [SimpleGraph.degree_compl] at hv have hdeg := SimpleGraph.degree_lt_card_verts (G := G) v omega