AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_degree_compl

theoremverifiedformalization

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

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

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

    lines 1–40

    uses Finset.card_eq_sum_card_fiberwise, Finset.card_pair

    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_all
    
  2. 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).

    lines 43–62

    uses Finset.sum_union, Finset.sum_comm, Finset.sum_boole

    theorem 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
    
  3. 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.

    lines 63–80

    uses triangle_compl_two_mul_card_clique_pairs, Finset.card_filter, Finset.sum_product

    theorem 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
    
  4. 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).

    lines 81–99

    uses Finset.sum_singleton, SimpleGraph.mem_neighborFinset, Finset.sum_eq_zero

    theorem 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]
    
  5. 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.

    lines 100–113

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

    lines 114–152

    uses Finset.card_sdiff_of_subset, Finset.card_univ, Finset.card_insert_of_notMem, Finset.disjoint_singleton_left

    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 := 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
  7. 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).

    lines 153–179

    uses triangle_compl_pair_clique_iff, SimpleGraph.compl_adj, Finset.card_filter_add_card_filter_not, Finset.card_powersetCard

      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]
  8. 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).

    lines 180–207

    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_self

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

    lines 208–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.

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