AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_degree_le_choose

theoremverified

td_G(v) ≤ C(deg v, 2).

Statement

theorem simple_graph_triangle_degree_le_choose {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) :
    simple_graph_triangle_degree G v ≤ (G.degree v).choose 2
Source
Sanity lemma for simple_graph_triangle_degree (arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine)); used for the order bound on regular triangle-distinct graphs.
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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 4

The proof, explained

The triangle degree of a vertex v counts the edges spanned by its neighborhood, formally defined as the number of adjacent 2-element subsets of neighbors. Because these adjacent pairs form a subset of all pairs of neighbors, their count is bounded by the total number of 2-element subsets of the neighborhood, which evaluates to (deg(v) choose 2).

  1. The triangle degree of v is at most the total number of 2-element subsets of the neighbor set of v.

    By definition, the triangle degree of a vertex v counts the 2-element subsets of its neighbors that are joined by an edge, represented as a filter on the collection of all 2-element subsets of N(v). Filtering any finite set can only decrease or preserve its size (Finset.card_filter_le), so this count is bounded above by the total number of 2-element subsets of N(v).

    lines 4–5

    uses Finset.card_filter_le

      unfold simple_graph_triangle_degree
      calc _ ≤ ((G.neighborFinset v).powersetCard 2).card := Finset.card_filter_le _ _
  2. The total number of 2-element subsets of the neighbor set equals (deg(v) choose 2).

    The number of size-2 subsets of a finite set of cardinality k is (k choose 2) (Finset.card_powersetCard). Rewriting with this and the fact that the neighbor set of v has size deg(v) (SimpleGraph.card_neighborFinset_eq_degree) yields the upper bound (deg(v) choose 2).

    line 6

    uses Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree

        _ = (G.degree v).choose 2 := by rw [Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree]
Finset.card_filter_le
Filtering a finite set by a predicate produces a subset whose cardinality is at most that of the original set: |{x ∈ s | p(x)}| ≤ |s|.
Finset.card_powersetCard
The number of k-element subsets of a finite set s is (|s| choose k).
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighbor set of a vertex v equals the degree deg(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

theorem simple_graph_triangle_degree_le_choose {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) :    simple_graph_triangle_degree G v ≤ (G.degree v).choose 2 := by  unfold simple_graph_triangle_degree  calc _ ≤ ((G.neighborFinset v).powersetCard 2).card := Finset.card_filter_le _ _    _ = (G.degree v).choose 2 := by rw [Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree]
See it in the graphDiscuss this resultChallenge it