simple_graph_compl_regular_triangle_distinct
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
- regular_eight_triangle_distinct_card_ge_fifteenEvery 8-regular triangle-distinct graph with at least one vertex has at least 15 vertices: its complement is (n − 9)-regular and…
- simple_graph_eight_regular_not_card_fifteenNo 8-regular triangle-distinct simple graph exists on 15 vertices.
- simple_graph_regular_eight_triangle_distinct_fin_fifteen_degreesIf G is an 8-regular triangle-distinct graph on the 15 vertices {0,…,14}, then the set of its vertex triangle-degrees is exactly…
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.
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.
uses
hreg.complrefine ⟨?_, ?_⟩ · have h := hreg.compl rw [hN] at h have e : N - 1 - r = N - r - 1 := by omega rwa [e] at h
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.
· intro x y hxy apply htd
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.
uses
simple_graph_triangle_degree_complhave 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 ℚ.
- The formula relating triangle degrees in the complement graph and the original graph (`simple_graph_triangle_degree_compl`) is stated over the rational numbers ℚ to handle division by 2, requiring the equality of triangle degrees in G to be derived in ℚ before being cast back to ℕ via `exact_mod_cast`.
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.
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