AFTD Auto-Formalizing Theoretical Domains

regular_graph_compl_regular_iff

theoremverified

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

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.

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

    lines 6–8

      constructor
      · intro h
        exact h.compl
  2. 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.

    lines 9–11

    uses SimpleGraph.degree_compl

      · intro h v
        have hv := h v
        rw [SimpleGraph.degree_compl] at hv
  3. 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.

    lines 12–13

    uses SimpleGraph.degree_lt_card_verts

        have 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

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