AFTD Auto-Formalizing Theoretical Domains

simple_graph_compl_regular_triangle_distinct

theoremverifiedformalization

If G is an r-regular triangle-distinct graph on N vertices, its complement is an (N − r − 1)-regular triangle-distinct graph.

Statement

theorem simple_graph_compl_regular_triangle_distinct {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (r N : ℕ) (hN : Fintype.card V = N)
    (hreg : G.IsRegularOfDegree r) (htd : simple_graph_is_triangle_distinct G) :
    Gᶜ.IsRegularOfDegree (N - r - 1) ∧ simple_graph_is_triangle_distinct Gᶜ
Formalizes
arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine), Lemma 2.1 (consequence); follows from the complement formula simple_graph_triangle_degree_compl.
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_triangle_degree_complLet G be an r-regular simple graph on N vertices. For every vertex v, td_{Ḡ}(v) = C(N − r − 1, 2) − N r / 2 + r² − td_G(v), where Ḡ is the…
  • simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
  • simple_graph_triangle_degreeThe triangle-degree td_G(v): the number of triangles of G containing v, i.e. the number of 2-element subsets {u, w} of the neighbourhood…
Used by 3

The proof, explained

The proof splits into two parts: regularity and triangle-distinctness of the complement graph Gᶜ. Regularity of Gᶜ follows from the general theorem for regular graph complements, which gives degree |V| - 1 - r = N - r - 1. For triangle-distinctness, the triangle degree of any vertex in Gᶜ is shown to be an affine function of its triangle degree in G with slope -1; hence any two vertices with equal triangle degree in Gᶜ must have equal triangle degree in G, which implies they are the same vertex since G is triangle-distinct.

  1. Gᶜ is regular of degree N - r - 1.

    The theorem requires proving two conjuncts: regularity and triangle-distinctness of Gᶜ. For regularity, `hreg.compl` states that the complement of an r-regular graph on vertex set V is regular of degree |V| - 1 - r. Rewriting |V| as N using the hypothesis hN and simplifying the arithmetic identity N - 1 - r = N - r - 1 establishes that Gᶜ is regular of degree N - r - 1.

    lines 5–9

    uses hreg.compl

      refine ⟨?_, ?_⟩
      · have h := hreg.compl
        rw [hN] at h
        have e : N - 1 - r = N - r - 1 := by omega
        rwa [e] at h
  2. To show Gᶜ is triangle-distinct, it suffices to show that any two vertices x and y with equal triangle degree in Gᶜ also have equal triangle degree in G.

    By definition, a graph is triangle-distinct if its triangle-degree function is injective. Assuming x and y have the same triangle degree in Gᶜ, injectivity of the triangle degree in G (the hypothesis htd) reduces proving x = y to proving that x and y have the same triangle degree in G.

    lines 10–11

      · intro x y hxy
        apply htd
  3. The triangle degrees of x and y in G are equal, which proves x = y and completes the proof.

    By `simple_graph_triangle_degree_compl`, the triangle degree of any vertex v in Gᶜ is given in ℚ by a constant depending only on N and r minus its triangle degree in G. Since x and y have equal triangle degrees in Gᶜ, linear arithmetic over ℚ implies that their triangle degrees in G are equal. Casting this equality back from ℚ to ℕ closes the goal.

    lines 12–16

    uses simple_graph_triangle_degree_compl

        have h1 := simple_graph_triangle_degree_compl G r N hN hreg x
        have h2 := simple_graph_triangle_degree_compl G r N hN hreg y
        have : (simple_graph_triangle_degree G x : ℚ) = simple_graph_triangle_degree G y := by
          rw [hxy] at h1; linarith
        exact_mod_cast this
hreg.compl
If a graph G on a finite vertex set V is r-regular, then its complement Gᶜ is regular of degree |V| - 1 - r.
simple_graph_triangle_degree_compl
For an r-regular graph G on N vertices, the triangle degree of any vertex v in Gᶜ equals ((N - r - 1).choose 2) - N * r / 2 + r^2 - (triangle degree of v in G), evaluated in ℚ.

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

theorem simple_graph_compl_regular_triangle_distinct {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (r N : ℕ) (hN : Fintype.card V = N)    (hreg : G.IsRegularOfDegree r) (htd : simple_graph_is_triangle_distinct G) :    Gᶜ.IsRegularOfDegree (N - r - 1) ∧ simple_graph_is_triangle_distinct Gᶜ := by  refine ⟨?_, ?_⟩  · have h := hreg.compl    rw [hN] at h    have e : N - 1 - r = N - r - 1 := by omega    rwa [e] at h  · intro x y hxy    apply htd    have h1 := simple_graph_triangle_degree_compl G r N hN hreg x    have h2 := simple_graph_triangle_degree_compl G r N hN hreg y    have : (simple_graph_triangle_degree G x : ℚ) = simple_graph_triangle_degree G y := by      rw [hxy] at h1; linarith    exact_mod_cast this
See it in the graphDiscuss this resultChallenge it