simple_graph_triangle_degree_compl
Let 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 complement of G.
Statement
theorem simple_graph_triangle_degree_compl {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (r N : ℕ) (hN : Fintype.card V = N) (hreg : G.IsRegularOfDegree r) (v : V) : (simple_graph_triangle_degree Gᶜ v : ℚ) = ((N - r - 1).choose 2 : ℚ) - (N * r : ℚ) / 2 + (r : ℚ) ^ 2 - simple_graph_triangle_degree G v
- Formalizes
- arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine), Lemma 2.1 (first part); stated over ℚ so that N r / 2 and the subtraction are exact.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 3
- simple_graph_compl_regular_triangle_distinctIf G is an r-regular triangle-distinct graph on N vertices, its complement is an (N − r − 1)-regular triangle-distinct graph.
- 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
To compute the triangle degree of a vertex v in the complement graph Ḡ, the vertex set V is partitioned into {v}, its neighborhood A = N_G(v) of size r, and its non-neighborhood B = N_{Ḡ}(v) of size N - r - 1. The triangle degrees td_G(v) and td_{Ḡ}(v) correspond to the number of induced edges e_A in A and e_B in B respectively, with td_{Ḡ}(v) + e_B = C(N - r - 1, 2). Double counting the edges out of A and out of the whole graph produces two linear relations involving the cross-edge count e(A, B), e_A, and e_B. Eliminating e(A, B) and e_B from this linear system over ℚ directly yields the formula for td_{Ḡ}(v).
Twice the number of 2-element cliques for a relation R on a finite set S equals the number of distinct ordered pairs in S mutually related by R.
We count ordered pairs fiberwise via `Finset.card_eq_sum_card_fiberwise`, mapping each off-diagonal symmetric pair (x, y) to the unordered pair {x, y}. For every 2-clique {a, b}, the fiber consists of exactly two ordered pairs, (a, b) and (b, a) (lines 12–29), each of cardinality 2 by `Finset.card_pair`. We also check that every such ordered pair maps to a valid 2-element clique (lines 30–39), giving the factor of 2.
uses
Finset.card_eq_sum_card_fiberwise,Finset.card_pairtheorem triangle_compl_two_mul_card_clique_pairs {V : Type*} [DecidableEq V] (S : Finset V) (R : V → V → Prop) [DecidableRel R] : 2 * ((S.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → R x y)).card = (S.offDiag.filter (fun p => R p.1 p.2 ∧ R p.2 p.1)).card := by rw [Finset.card_eq_sum_card_fiberwise (f := fun p : V × V => ({p.1, p.2} : Finset V)) (t := (S.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → R x y))] · rw [mul_comm, ← smul_eq_mul, ← Finset.sum_const] refine Finset.sum_congr rfl fun t ht => ?_ obtain ⟨hts, hcl⟩ := Finset.mem_filter.1 ht obtain ⟨hsub, hcard⟩ := Finset.mem_powersetCard.1 hts obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.1 hcard have hfib : ((S.offDiag.filter fun p => R p.1 p.2 ∧ R p.2 p.1).filter fun p => ({p.1, p.2} : Finset V) = {a, b}) = {(a, b), (b, a)} := by ext ⟨x, y⟩ simp only [Finset.mem_filter, Finset.mem_offDiag, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq] constructor · rintro ⟨⟨⟨hx, hy, hxy⟩, hr⟩, heq⟩ have hx' : x ∈ ({a, b} : Finset V) := heq ▸ (by simp) have hy' : y ∈ ({a, b} : Finset V) := heq ▸ (by simp) simp only [Finset.mem_insert, Finset.mem_singleton] at hx' hy' rcases hx' with rfl | rfl <;> rcases hy' with rfl | rfl <;> simp_all · rintro (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) · exact ⟨⟨⟨hsub (by simp), hsub (by simp), hab⟩, hcl _ (by simp) _ (by simp) hab, hcl _ (by simp) _ (by simp) hab.symm⟩, rfl⟩ · exact ⟨⟨⟨hsub (by simp), hsub (by simp), hab.symm⟩, hcl _ (by simp) _ (by simp) hab.symm, hcl _ (by simp) _ (by simp) hab⟩, Finset.pair_comm _ _⟩ rw [hfib, Finset.card_pair (by simp [hab])] · rintro ⟨x, y⟩ hp simp only [Finset.mem_coe, Finset.mem_filter, Finset.mem_offDiag] at hp obtain ⟨⟨hx, hy, hxy⟩, hr1, hr2⟩ := hp simp only [Finset.mem_coe, Finset.mem_filter, Finset.mem_powersetCard] refine ⟨⟨?_, Finset.card_pair hxy⟩, ?_⟩ · intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl <;> assumption · intro z hz w hw hzw simp only [Finset.mem_insert, Finset.mem_singleton] at hz hw rcases hz with rfl | rfl <;> rcases hw with rfl | rfl <;> simp_all
The cross-set adjacency count e(S, T) is additive in both arguments over disjoint unions, symmetric, and sums to the vertex degrees when T is the full vertex set.
Left additivity `triangle_compl_adj_count_union_left` follows from splitting the outer sum with `Finset.sum_union` (lines 43–46). Right additivity `triangle_compl_adj_count_union_right` follows after distributing the inner sum (lines 47–51). Symmetry `triangle_compl_adj_count_comm` holds by interchanging the sums using `Finset.sum_comm` and applying the symmetry of graph adjacency (lines 52–56). Finally, summing over all y ∈ V evaluates each inner sum to the degree of x via `Finset.sum_boole`, so e(S, V) is the sum of degrees in S (lines 57–62).
uses
Finset.sum_union,Finset.sum_comm,Finset.sum_booletheorem triangle_compl_adj_count_union_left {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S S' T : Finset V) (h : Disjoint S S') : triangle_compl_adj_count G (S ∪ S') T = triangle_compl_adj_count G S T + triangle_compl_adj_count G S' T := by unfold triangle_compl_adj_count; rw [Finset.sum_union h] theorem triangle_compl_adj_count_union_right {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S T T' : Finset V) (h : Disjoint T T') : triangle_compl_adj_count G S (T ∪ T') = triangle_compl_adj_count G S T + triangle_compl_adj_count G S T' := by unfold triangle_compl_adj_count; rw [← Finset.sum_add_distrib] exact Finset.sum_congr rfl fun x _ => Finset.sum_union h theorem triangle_compl_adj_count_comm {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S T : Finset V) : triangle_compl_adj_count G S T = triangle_compl_adj_count G T S := by unfold triangle_compl_adj_count; rw [Finset.sum_comm] refine Finset.sum_congr rfl fun x _ => Finset.sum_congr rfl fun y _ => ?_ simp [G.adj_comm] theorem triangle_compl_adj_count_univ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : triangle_compl_adj_count G S Finset.univ = ∑ x ∈ S, G.degree x := by unfold triangle_compl_adj_count refine Finset.sum_congr rfl fun x _ => ?_ rw [Finset.sum_boole, ← G.card_neighborFinset_eq_degree, G.neighborFinset_eq_filter] simp
The self-adjacency count e(S, S) equals twice the number of induced edges on S.
Because simple graphs are loopless, the pairs in S × S that are adjacent in G coincide with the off-diagonal mutually adjacent pairs (lines 67–73). Rewriting the sum with `Finset.card_filter` and `Finset.sum_product` (line 76), the previous lemma `triangle_compl_two_mul_card_clique_pairs` shows this count is exactly twice the number of 2-cliques on S, which are the induced edges.
uses
triangle_compl_two_mul_card_clique_pairs,Finset.card_filter,Finset.sum_producttheorem triangle_compl_adj_count_self {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : triangle_compl_adj_count G S S = 2 * ((S.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y)).card := by have h2 := triangle_compl_two_mul_card_clique_pairs S G.Adj have h : S.offDiag.filter (fun p => G.Adj p.1 p.2 ∧ G.Adj p.2 p.1) = (S ×ˢ S).filter (fun p => G.Adj p.1 p.2) := by ext ⟨x, y⟩ simp only [Finset.mem_filter, Finset.mem_offDiag, Finset.mem_product] constructor · rintro ⟨⟨hx, hy, -⟩, h, -⟩; exact ⟨⟨hx, hy⟩, h⟩ · rintro ⟨⟨hx, hy⟩, h⟩; exact ⟨⟨hx, hy, h.ne⟩, h, h.symm⟩ have h3 : triangle_compl_adj_count G S S = (S.offDiag.filter (fun p => G.Adj p.1 p.2 ∧ G.Adj p.2 p.1)).card := by rw [h, Finset.card_filter, Finset.sum_product] rfl rw [h3] convert h2.symm
Singleton adjacency counts satisfy e(N(v), {v}) = deg(v), e({v}, {v}) = 0, and e(B, {v}) = 0 for any set B of non-neighbors of v.
Specialising the second set to {v} collapses the inner sum with `Finset.sum_singleton`. For the neighborhood N(v), each term is 1 because all members are adjacent to v, so the sum equals deg(v) (lines 81–90). For {v}, irreflexivity gives 0 (lines 91–93). For a set B of non-neighbors, every term is 0, so the sum vanishes by `Finset.sum_eq_zero` (lines 94–99).
uses
Finset.sum_singleton,SimpleGraph.mem_neighborFinset,Finset.sum_eq_zerotheorem triangle_compl_adj_count_singleton_nbr {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : triangle_compl_adj_count G (G.neighborFinset v) {v} = G.degree v := by unfold triangle_compl_adj_count simp only [Finset.sum_singleton] rw [Finset.sum_congr rfl (g := fun _ => 1), Finset.sum_const, smul_eq_mul, mul_one, G.card_neighborFinset_eq_degree] intro x hx rw [SimpleGraph.mem_neighborFinset] at hx simp [hx.symm] theorem triangle_compl_adj_count_singleton_self {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : triangle_compl_adj_count G {v} {v} = 0 := by simp [triangle_compl_adj_count] theorem triangle_compl_adj_count_nonnbr_singleton {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (B : Finset V) (hB : ∀ x ∈ B, ¬ G.Adj x v) : triangle_compl_adj_count G B {v} = 0 := by unfold triangle_compl_adj_count simp only [Finset.sum_singleton] exact Finset.sum_eq_zero fun x hx => by simp [hB x hx]
Two distinct vertices a ≠ b form a 2-clique for relation R if and only if R a b and R b a both hold.
A 2-element set {a, b} is an R-clique when every pair of distinct elements is related. Since a ≠ b, the only ordered pairs of distinct elements are (a, b) and (b, a), so the condition reduces to R a b ∧ R b a by unpacking set membership and case splitting.
theorem triangle_compl_pair_clique_iff {V : Type*} [DecidableEq V] (R : V → V → Prop) {a b : V} (hab : a ≠ b) : (∀ x ∈ ({a, b} : Finset V), ∀ y ∈ ({a, b} : Finset V), x ≠ y → R x y) ↔ R a b ∧ R b a := by simp only [Finset.mem_insert, Finset.mem_singleton] constructor · intro h exact ⟨h a (Or.inl rfl) b (Or.inr rfl) hab, h b (Or.inr rfl) a (Or.inl rfl) hab.symm⟩ · rintro ⟨h1, h2⟩ x hx y hy hxy rcases hx with rfl | rfl <;> rcases hy with rfl | rfl · exact absurd rfl hxy · exact h1 · exact h2 · exact absurd rfl hxy
The vertex set V partitions into the disjoint union of {v}, the neighbors A = N_G(v) of size r, and the non-neighbors B = N_{Ḡ}(v) of size N - r - 1.
We set A = N_G(v) and B = N_{Ḡ}(v) = V \ ({v} ∪ A) (lines 120–130). By r-regularity, |A| = r and v ∉ A (lines 131–132). Using `Finset.card_sdiff_of_subset` and `Finset.card_univ`, |B| = N - (r + 1) = N - r - 1 (lines 133–136). The sets {v}, A, and B are pairwise disjoint with union V (lines 137–148), and no vertex in B is adjacent to v in G (lines 149–151).
uses
Finset.card_sdiff_of_subset,Finset.card_univ,Finset.card_insert_of_notMem,Finset.disjoint_singleton_lefttheorem simple_graph_triangle_degree_compl {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (r N : ℕ) (hN : Fintype.card V = N) (hreg : G.IsRegularOfDegree r) (v : V) : (simple_graph_triangle_degree Gᶜ v : ℚ) = ((N - r - 1).choose 2 : ℚ) - (N * r : ℚ) / 2 + (r : ℚ) ^ 2 - simple_graph_triangle_degree G v := by set A := G.neighborFinset v with hA set B := Gᶜ.neighborFinset v with hB have hBeq : B = Finset.univ \ insert v A := by ext x simp only [hB, hA, SimpleGraph.mem_neighborFinset, SimpleGraph.compl_adj, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, true_and] constructor · rintro ⟨hne, hna⟩; rintro (rfl | h) · exact hne rfl · exact hna h · intro h; exact ⟨fun e => h (Or.inl e.symm), fun e => h (Or.inr e)⟩ have hvA : v ∉ A := by simp [hA] have hcardA : A.card = r := by rw [hA, G.card_neighborFinset_eq_degree, hreg v] have hcardB : B.card = N - r - 1 := by rw [hBeq, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ, hN, Finset.card_insert_of_notMem hvA, hcardA] omega have hdisjAB : Disjoint A B := by rw [hBeq]; exact Finset.disjoint_sdiff.mono_left (Finset.subset_insert _ _) have hdisjv : Disjoint {v} (A ∪ B) := by rw [Finset.disjoint_singleton_left, Finset.mem_union, not_or] exact ⟨hvA, by rw [hBeq]; simp⟩ have huniv : (Finset.univ : Finset V) = {v} ∪ (A ∪ B) := by ext x; simp only [Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, true_iff] by_cases h1 : x = v · exact Or.inl h1 · by_cases h2 : x ∈ A · exact Or.inr (Or.inl h2) · right; right; rw [hBeq]; simp [h1, h2] have hBnv : ∀ x ∈ B, ¬ G.Adj x v := by intro x hx h; rw [hBeq] at hx; simp at hx exact hx.2 (by rw [hA, SimpleGraph.mem_neighborFinset]; exact h.symm) -- the counts
The triangle degree td_G(v) equals e_A (the induced edges on A), while td_{Ḡ}(v) + e_B = C(N - r - 1, 2), where e_B is the number of edges of G induced on B.
The triangle degree td_G(v) is defined as the number of edges induced by G on N_G(v) = A, which is e_A (line 155). In the complement graph Ḡ, two distinct vertices in B are adjacent if and only if they are not adjacent in G (lines 156–171). Hence the 2-subsets of B partition into edges of Ḡ (counted by td_{Ḡ}(v)) and edges of G (counted by e_B). By `Finset.card_filter_add_card_filter_not` and `Finset.card_powersetCard`, their sum is |B choose 2| = C(N - r - 1, 2) (lines 172–179).
uses
triangle_compl_pair_clique_iff,SimpleGraph.compl_adj,Finset.card_filter_add_card_filter_not,Finset.card_powersetCardset eA := ((A.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y)).card set eB := ((B.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y)).card have htdG : simple_graph_triangle_degree G v = eA := rfl have hfilt : (B.powersetCard 2).filter (fun s => ¬ ∀ x ∈ s, ∀ y ∈ s, x ≠ y → Gᶜ.Adj x y) = (B.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y) := by apply Finset.filter_congr intro s hs obtain ⟨-, hc⟩ := Finset.mem_powersetCard.1 hs obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.1 hc rw [triangle_compl_pair_clique_iff _ hab, triangle_compl_pair_clique_iff _ hab] simp only [SimpleGraph.compl_adj] constructor · intro h by_contra hn apply h refine ⟨⟨hab, fun h1 => hn ⟨h1, h1.symm⟩⟩, ⟨hab.symm, fun h2 => hn ⟨h2.symm, h2⟩⟩⟩ · rintro ⟨h1, -⟩ ⟨⟨-, h2⟩, -⟩ exact h2 h1 have htdC : simple_graph_triangle_degree Gᶜ v + eB = (N - r - 1).choose 2 := by calc simple_graph_triangle_degree Gᶜ v + eB = ((B.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → Gᶜ.Adj x y)).card + ((B.powersetCard 2).filter (fun s => ¬ ∀ x ∈ s, ∀ y ∈ s, x ≠ y → Gᶜ.Adj x y)).card := by rw [hfilt]; rfl _ = (B.powersetCard 2).card := Finset.card_filter_add_card_filter_not _ _ = _ := by rw [Finset.card_powersetCard, hcardB]
Double counting cross-set edges yields two linear equations: N r = r + r² + e(A, B) + 2 e_B and r² = r + 2 e_A + e(A, B).
By r-regularity, e(V, V) = N r (`e1`) and e(A, V) = r² (`e2`) using `triangle_compl_adj_count_univ`. Decomposing V = {v} ∪ A ∪ B with the union lemmas expresses e(A, V) as e(A, {v}) + e(A, A) + e(A, B) = r + 2 e_A + e(A, B), yielding `key2` (lines 186, 206–207). Decomposing e(V, V) = e({v}, V) + e(A, V) + e(B, V) and expanding e(B, V) = 0 + e(A, B) + 2 e_B yields `key1`: N r = r + r² + e(A, B) + 2 e_B (lines 189–205).
uses
triangle_compl_adj_count_univ,triangle_compl_adj_count_union_left,triangle_compl_adj_count_union_right,triangle_compl_adj_count_singleton_nbr,triangle_compl_adj_count_nonnbr_singleton,triangle_compl_adj_count_comm,triangle_compl_adj_count_selfhave e1 : triangle_compl_adj_count G Finset.univ Finset.univ = N * r := by rw [triangle_compl_adj_count_univ, Finset.sum_congr rfl (fun x _ => hreg x), Finset.sum_const, Finset.card_univ, hN, smul_eq_mul] have e2 : triangle_compl_adj_count G A Finset.univ = r * r := by rw [triangle_compl_adj_count_univ, Finset.sum_congr rfl (fun x _ => hreg x), Finset.sum_const, hcardA, smul_eq_mul] have e3 : triangle_compl_adj_count G A Finset.univ = triangle_compl_adj_count G A {v} + (triangle_compl_adj_count G A A + triangle_compl_adj_count G A B) := by calc triangle_compl_adj_count G A Finset.univ = triangle_compl_adj_count G A ({v} ∪ (A ∪ B)) := by rw [← huniv] _ = _ := by rw [triangle_compl_adj_count_union_right _ _ _ _ hdisjv, triangle_compl_adj_count_union_right _ _ _ _ hdisjAB] have e4 : triangle_compl_adj_count G Finset.univ Finset.univ = triangle_compl_adj_count G {v} Finset.univ + (triangle_compl_adj_count G A Finset.univ + triangle_compl_adj_count G B Finset.univ) := by calc triangle_compl_adj_count G Finset.univ Finset.univ = triangle_compl_adj_count G ({v} ∪ (A ∪ B)) Finset.univ := by rw [← huniv] _ = _ := by rw [triangle_compl_adj_count_union_left _ _ _ _ hdisjv, triangle_compl_adj_count_union_left _ _ _ _ hdisjAB] have e5 : triangle_compl_adj_count G B Finset.univ = triangle_compl_adj_count G B {v} + (triangle_compl_adj_count G B A + triangle_compl_adj_count G B B) := by calc triangle_compl_adj_count G B Finset.univ = triangle_compl_adj_count G B ({v} ∪ (A ∪ B)) := by rw [← huniv] _ = _ := by rw [triangle_compl_adj_count_union_right _ _ _ _ hdisjv, triangle_compl_adj_count_union_right _ _ _ _ hdisjAB] have e6 : triangle_compl_adj_count G {v} Finset.univ = r := by rw [triangle_compl_adj_count_univ, Finset.sum_singleton, hreg v] have e7 : triangle_compl_adj_count G A {v} = r := by rw [hA, triangle_compl_adj_count_singleton_nbr, hreg v] have e8 : triangle_compl_adj_count G B {v} = 0 := triangle_compl_adj_count_nonnbr_singleton G v B hBnv have e9 : triangle_compl_adj_count G B A = triangle_compl_adj_count G A B := triangle_compl_adj_count_comm G B A have eAA : triangle_compl_adj_count G A A = 2 * eA := triangle_compl_adj_count_self G A have eBB : triangle_compl_adj_count G B B = 2 * eB := triangle_compl_adj_count_self G B have key1 : N * r = r + r * r + triangle_compl_adj_count G A B + 2 * eB := by rw [← e1, e4, e6, e2, e5, e8, e9, eBB]; ring have key2 : r * r = r + 2 * eA + triangle_compl_adj_count G A B := by rw [← e2, e3, e7, eAA]; ring
Eliminating e(A, B) and e_B from the linear system establishes td_{Ḡ}(v) = C(N - r - 1, 2) - N r / 2 + r² - td_G(v) over ℚ. automation
The equations `key1`, `key2`, and `htdC` are cast from ℕ to ℚ as `q1`, `q2`, `q3` (lines 208–211). Rewriting td_G(v) to e_A via `htdG` (line 212), `linarith` solves the linear system over ℚ by eliminating e(A, B) and e_B, completing the proof (line 213).
have q1 : (N : ℚ) * r = r + r * r + (triangle_compl_adj_count G A B : ℚ) + 2 * eB := by exact_mod_cast key1 have q2 : (r : ℚ) * r = r + 2 * eA + (triangle_compl_adj_count G A B : ℚ) := by exact_mod_cast key2 have q3 : (simple_graph_triangle_degree Gᶜ v : ℚ) + eB = ((N - r - 1).choose 2 : ℕ) := by exact_mod_cast htdC rw [htdG] linarith
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum of the cardinalities of the fibers of any map into a target set.
Finset.card_pair- The cardinality of an unordered pair {a, b} of distinct elements is 2.
Finset.sum_union- The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
Finset.sum_comm- Fubini's theorem for finite sets: swapping the order of summation over two finite sets leaves the sum unchanged.
Finset.sum_boole- The sum of a Boolean indicator over a finite set equals the cardinality of the subset satisfying the predicate.
triangle_compl_two_mul_card_clique_pairs- Twice the number of 2-element cliques for a relation R on S equals the number of distinct ordered pairs in S mutually related by R.
Finset.card_filter- The cardinality of a filtered subset equals the sum over the parent set of the indicator of the condition.
Finset.sum_product- The sum over a Cartesian product of two finite sets equals the iterated double sum over each set.
Finset.sum_singleton- The sum of a function over a singleton set {a} equals the function value at a.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Finset.sum_eq_zero- If a function is identically zero on a finite set, its sum over that set is zero.
Finset.card_sdiff_of_subset- If S ⊆ T, then |T \ S| = |T| - |S|.
Finset.card_univ- The cardinality of the universal finset is the cardinality of the underlying finite type.
Finset.card_insert_of_notMem- Inserting an element not belonging to S increases the cardinality of S by 1.
Finset.disjoint_singleton_left- A singleton {a} is disjoint from a set S if and only if a ∉ S.
triangle_compl_pair_clique_iff- Two distinct vertices a ≠ b form a 2-clique for relation R if and only if R a b and R b a both hold.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph if and only if they are distinct and not adjacent in the original graph.
Finset.card_filter_add_card_filter_not- The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the cardinality of the set.
Finset.card_powersetCard- The number of k-element subsets of a set of cardinality n is C(n, k).
triangle_compl_adj_count_univ- The sum of vertex degrees over a subset S equals the cross-set adjacency count from S to the entire graph.
triangle_compl_adj_count_union_left- The cross-set adjacency count is additive in the first argument over disjoint unions: e(S ∪ S', T) = e(S, T) + e(S', T).
triangle_compl_adj_count_union_right- The cross-set adjacency count is additive in the second argument over disjoint unions: e(S, T ∪ T') = e(S, T) + e(S, T').
triangle_compl_adj_count_singleton_nbr- The adjacency count between the neighborhood of v and the singleton {v} equals the degree of v.
triangle_compl_adj_count_nonnbr_singleton- The adjacency count between a set of non-neighbors of v and the singleton {v} is 0.
triangle_compl_adj_count_comm- The cross-set adjacency count is symmetric: e(S, T) = e(T, S).
triangle_compl_adj_count_self- The self-adjacency count e(S, S) equals twice the number of edges induced on S.
- The final step relies on `linarith` to eliminate the auxiliary counts and solve the 3-variable linear system over ℚ without manual algebraic rearrangement.
- In Step 6, the subtraction arithmetic showing |B| = N - r - 1 is closed by the `omega` decision procedure.
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 triangle_compl_two_mul_card_clique_pairs {V : Type*} [DecidableEq V] (S : Finset V) (R : V → V → Prop) [DecidableRel R] : 2 * ((S.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → R x y)).card = (S.offDiag.filter (fun p => R p.1 p.2 ∧ R p.2 p.1)).card := by rw [Finset.card_eq_sum_card_fiberwise (f := fun p : V × V => ({p.1, p.2} : Finset V)) (t := (S.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → R x y))] · rw [mul_comm, ← smul_eq_mul, ← Finset.sum_const] refine Finset.sum_congr rfl fun t ht => ?_ obtain ⟨hts, hcl⟩ := Finset.mem_filter.1 ht obtain ⟨hsub, hcard⟩ := Finset.mem_powersetCard.1 hts obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.1 hcard have hfib : ((S.offDiag.filter fun p => R p.1 p.2 ∧ R p.2 p.1).filter fun p => ({p.1, p.2} : Finset V) = {a, b}) = {(a, b), (b, a)} := by ext ⟨x, y⟩ simp only [Finset.mem_filter, Finset.mem_offDiag, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq] constructor · rintro ⟨⟨⟨hx, hy, hxy⟩, hr⟩, heq⟩ have hx' : x ∈ ({a, b} : Finset V) := heq ▸ (by simp) have hy' : y ∈ ({a, b} : Finset V) := heq ▸ (by simp) simp only [Finset.mem_insert, Finset.mem_singleton] at hx' hy' rcases hx' with rfl | rfl <;> rcases hy' with rfl | rfl <;> simp_all · rintro (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) · exact ⟨⟨⟨hsub (by simp), hsub (by simp), hab⟩, hcl _ (by simp) _ (by simp) hab, hcl _ (by simp) _ (by simp) hab.symm⟩, rfl⟩ · exact ⟨⟨⟨hsub (by simp), hsub (by simp), hab.symm⟩, hcl _ (by simp) _ (by simp) hab.symm, hcl _ (by simp) _ (by simp) hab⟩, Finset.pair_comm _ _⟩ rw [hfib, Finset.card_pair (by simp [hab])] · rintro ⟨x, y⟩ hp simp only [Finset.mem_coe, Finset.mem_filter, Finset.mem_offDiag] at hp obtain ⟨⟨hx, hy, hxy⟩, hr1, hr2⟩ := hp simp only [Finset.mem_coe, Finset.mem_filter, Finset.mem_powersetCard] refine ⟨⟨?_, Finset.card_pair hxy⟩, ?_⟩ · intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl <;> assumption · intro z hz w hw hzw simp only [Finset.mem_insert, Finset.mem_singleton] at hz hw rcases hz with rfl | rfl <;> rcases hw with rfl | rfl <;> simp_alldef triangle_compl_adj_count {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S T : Finset V) : ℕ := ∑ x ∈ S, ∑ y ∈ T, if G.Adj x y then 1 else 0theorem triangle_compl_adj_count_union_left {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S S' T : Finset V) (h : Disjoint S S') : triangle_compl_adj_count G (S ∪ S') T = triangle_compl_adj_count G S T + triangle_compl_adj_count G S' T := by unfold triangle_compl_adj_count; rw [Finset.sum_union h]theorem triangle_compl_adj_count_union_right {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S T T' : Finset V) (h : Disjoint T T') : triangle_compl_adj_count G S (T ∪ T') = triangle_compl_adj_count G S T + triangle_compl_adj_count G S T' := by unfold triangle_compl_adj_count; rw [← Finset.sum_add_distrib] exact Finset.sum_congr rfl fun x _ => Finset.sum_union htheorem triangle_compl_adj_count_comm {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S T : Finset V) : triangle_compl_adj_count G S T = triangle_compl_adj_count G T S := by unfold triangle_compl_adj_count; rw [Finset.sum_comm] refine Finset.sum_congr rfl fun x _ => Finset.sum_congr rfl fun y _ => ?_ simp [G.adj_comm]theorem triangle_compl_adj_count_univ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : triangle_compl_adj_count G S Finset.univ = ∑ x ∈ S, G.degree x := by unfold triangle_compl_adj_count refine Finset.sum_congr rfl fun x _ => ?_ rw [Finset.sum_boole, ← G.card_neighborFinset_eq_degree, G.neighborFinset_eq_filter] simptheorem triangle_compl_adj_count_self {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : triangle_compl_adj_count G S S = 2 * ((S.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y)).card := by have h2 := triangle_compl_two_mul_card_clique_pairs S G.Adj have h : S.offDiag.filter (fun p => G.Adj p.1 p.2 ∧ G.Adj p.2 p.1) = (S ×ˢ S).filter (fun p => G.Adj p.1 p.2) := by ext ⟨x, y⟩ simp only [Finset.mem_filter, Finset.mem_offDiag, Finset.mem_product] constructor · rintro ⟨⟨hx, hy, -⟩, h, -⟩; exact ⟨⟨hx, hy⟩, h⟩ · rintro ⟨⟨hx, hy⟩, h⟩; exact ⟨⟨hx, hy, h.ne⟩, h, h.symm⟩ have h3 : triangle_compl_adj_count G S S = (S.offDiag.filter (fun p => G.Adj p.1 p.2 ∧ G.Adj p.2 p.1)).card := by rw [h, Finset.card_filter, Finset.sum_product] rfl rw [h3] convert h2.symmtheorem triangle_compl_adj_count_singleton_nbr {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : triangle_compl_adj_count G (G.neighborFinset v) {v} = G.degree v := by unfold triangle_compl_adj_count simp only [Finset.sum_singleton] rw [Finset.sum_congr rfl (g := fun _ => 1), Finset.sum_const, smul_eq_mul, mul_one, G.card_neighborFinset_eq_degree] intro x hx rw [SimpleGraph.mem_neighborFinset] at hx simp [hx.symm]theorem triangle_compl_adj_count_singleton_self {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : triangle_compl_adj_count G {v} {v} = 0 := by simp [triangle_compl_adj_count]theorem triangle_compl_adj_count_nonnbr_singleton {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (B : Finset V) (hB : ∀ x ∈ B, ¬ G.Adj x v) : triangle_compl_adj_count G B {v} = 0 := by unfold triangle_compl_adj_count simp only [Finset.sum_singleton] exact Finset.sum_eq_zero fun x hx => by simp [hB x hx]theorem triangle_compl_pair_clique_iff {V : Type*} [DecidableEq V] (R : V → V → Prop) {a b : V} (hab : a ≠ b) : (∀ x ∈ ({a, b} : Finset V), ∀ y ∈ ({a, b} : Finset V), x ≠ y → R x y) ↔ R a b ∧ R b a := by simp only [Finset.mem_insert, Finset.mem_singleton] constructor · intro h exact ⟨h a (Or.inl rfl) b (Or.inr rfl) hab, h b (Or.inr rfl) a (Or.inl rfl) hab.symm⟩ · rintro ⟨h1, h2⟩ x hx y hy hxy rcases hx with rfl | rfl <;> rcases hy with rfl | rfl · exact absurd rfl hxy · exact h1 · exact h2 · exact absurd rfl hxytheorem simple_graph_triangle_degree_compl {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (r N : ℕ) (hN : Fintype.card V = N) (hreg : G.IsRegularOfDegree r) (v : V) : (simple_graph_triangle_degree Gᶜ v : ℚ) = ((N - r - 1).choose 2 : ℚ) - (N * r : ℚ) / 2 + (r : ℚ) ^ 2 - simple_graph_triangle_degree G v := by set A := G.neighborFinset v with hA set B := Gᶜ.neighborFinset v with hB have hBeq : B = Finset.univ \ insert v A := by ext x simp only [hB, hA, SimpleGraph.mem_neighborFinset, SimpleGraph.compl_adj, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, true_and] constructor · rintro ⟨hne, hna⟩; rintro (rfl | h) · exact hne rfl · exact hna h · intro h; exact ⟨fun e => h (Or.inl e.symm), fun e => h (Or.inr e)⟩ have hvA : v ∉ A := by simp [hA] have hcardA : A.card = r := by rw [hA, G.card_neighborFinset_eq_degree, hreg v] have hcardB : B.card = N - r - 1 := by rw [hBeq, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ, hN, Finset.card_insert_of_notMem hvA, hcardA] omega have hdisjAB : Disjoint A B := by rw [hBeq]; exact Finset.disjoint_sdiff.mono_left (Finset.subset_insert _ _) have hdisjv : Disjoint {v} (A ∪ B) := by rw [Finset.disjoint_singleton_left, Finset.mem_union, not_or] exact ⟨hvA, by rw [hBeq]; simp⟩ have huniv : (Finset.univ : Finset V) = {v} ∪ (A ∪ B) := by ext x; simp only [Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, true_iff] by_cases h1 : x = v · exact Or.inl h1 · by_cases h2 : x ∈ A · exact Or.inr (Or.inl h2) · right; right; rw [hBeq]; simp [h1, h2] have hBnv : ∀ x ∈ B, ¬ G.Adj x v := by intro x hx h; rw [hBeq] at hx; simp at hx exact hx.2 (by rw [hA, SimpleGraph.mem_neighborFinset]; exact h.symm) -- the counts set eA := ((A.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y)).card set eB := ((B.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y)).card have htdG : simple_graph_triangle_degree G v = eA := rfl have hfilt : (B.powersetCard 2).filter (fun s => ¬ ∀ x ∈ s, ∀ y ∈ s, x ≠ y → Gᶜ.Adj x y) = (B.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → G.Adj x y) := by apply Finset.filter_congr intro s hs obtain ⟨-, hc⟩ := Finset.mem_powersetCard.1 hs obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.1 hc rw [triangle_compl_pair_clique_iff _ hab, triangle_compl_pair_clique_iff _ hab] simp only [SimpleGraph.compl_adj] constructor · intro h by_contra hn apply h refine ⟨⟨hab, fun h1 => hn ⟨h1, h1.symm⟩⟩, ⟨hab.symm, fun h2 => hn ⟨h2.symm, h2⟩⟩⟩ · rintro ⟨h1, -⟩ ⟨⟨-, h2⟩, -⟩ exact h2 h1 have htdC : simple_graph_triangle_degree Gᶜ v + eB = (N - r - 1).choose 2 := by calc simple_graph_triangle_degree Gᶜ v + eB = ((B.powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → Gᶜ.Adj x y)).card + ((B.powersetCard 2).filter (fun s => ¬ ∀ x ∈ s, ∀ y ∈ s, x ≠ y → Gᶜ.Adj x y)).card := by rw [hfilt]; rfl _ = (B.powersetCard 2).card := Finset.card_filter_add_card_filter_not _ _ = _ := by rw [Finset.card_powersetCard, hcardB] have e1 : triangle_compl_adj_count G Finset.univ Finset.univ = N * r := by rw [triangle_compl_adj_count_univ, Finset.sum_congr rfl (fun x _ => hreg x), Finset.sum_const, Finset.card_univ, hN, smul_eq_mul] have e2 : triangle_compl_adj_count G A Finset.univ = r * r := by rw [triangle_compl_adj_count_univ, Finset.sum_congr rfl (fun x _ => hreg x), Finset.sum_const, hcardA, smul_eq_mul] have e3 : triangle_compl_adj_count G A Finset.univ = triangle_compl_adj_count G A {v} + (triangle_compl_adj_count G A A + triangle_compl_adj_count G A B) := by calc triangle_compl_adj_count G A Finset.univ = triangle_compl_adj_count G A ({v} ∪ (A ∪ B)) := by rw [← huniv] _ = _ := by rw [triangle_compl_adj_count_union_right _ _ _ _ hdisjv, triangle_compl_adj_count_union_right _ _ _ _ hdisjAB] have e4 : triangle_compl_adj_count G Finset.univ Finset.univ = triangle_compl_adj_count G {v} Finset.univ + (triangle_compl_adj_count G A Finset.univ + triangle_compl_adj_count G B Finset.univ) := by calc triangle_compl_adj_count G Finset.univ Finset.univ = triangle_compl_adj_count G ({v} ∪ (A ∪ B)) Finset.univ := by rw [← huniv] _ = _ := by rw [triangle_compl_adj_count_union_left _ _ _ _ hdisjv, triangle_compl_adj_count_union_left _ _ _ _ hdisjAB] have e5 : triangle_compl_adj_count G B Finset.univ = triangle_compl_adj_count G B {v} + (triangle_compl_adj_count G B A + triangle_compl_adj_count G B B) := by calc triangle_compl_adj_count G B Finset.univ = triangle_compl_adj_count G B ({v} ∪ (A ∪ B)) := by rw [← huniv] _ = _ := by rw [triangle_compl_adj_count_union_right _ _ _ _ hdisjv, triangle_compl_adj_count_union_right _ _ _ _ hdisjAB] have e6 : triangle_compl_adj_count G {v} Finset.univ = r := by rw [triangle_compl_adj_count_univ, Finset.sum_singleton, hreg v] have e7 : triangle_compl_adj_count G A {v} = r := by rw [hA, triangle_compl_adj_count_singleton_nbr, hreg v] have e8 : triangle_compl_adj_count G B {v} = 0 := triangle_compl_adj_count_nonnbr_singleton G v B hBnv have e9 : triangle_compl_adj_count G B A = triangle_compl_adj_count G A B := triangle_compl_adj_count_comm G B A have eAA : triangle_compl_adj_count G A A = 2 * eA := triangle_compl_adj_count_self G A have eBB : triangle_compl_adj_count G B B = 2 * eB := triangle_compl_adj_count_self G B have key1 : N * r = r + r * r + triangle_compl_adj_count G A B + 2 * eB := by rw [← e1, e4, e6, e2, e5, e8, e9, eBB]; ring have key2 : r * r = r + 2 * eA + triangle_compl_adj_count G A B := by rw [← e2, e3, e7, eAA]; ring have q1 : (N : ℚ) * r = r + r * r + (triangle_compl_adj_count G A B : ℚ) + 2 * eB := by exact_mod_cast key1 have q2 : (r : ℚ) * r = r + 2 * eA + (triangle_compl_adj_count G A B : ℚ) := by exact_mod_cast key2 have q3 : (simple_graph_triangle_degree Gᶜ v : ℚ) + eB = ((N - r - 1).choose 2 : ℕ) := by exact_mod_cast htdC rw [htdG] linarith