AFTD Auto-Formalizing Theoretical Domains

card_generalized_kneser_graph_verts

theoremverified

The vertex type of the generalized Kneser graph KG(2n, n, r), which consists of all n-element subsets of Fin (2 * n), has cardinality Nat.choose (2 * n) n.

Statement

theorem card_generalized_kneser_graph_verts (n : ℕ) :
    Fintype.card {s : Finset (Fin (2 * n)) // s.card = n} = Nat.choose (2 * n) n
Source
step towards op_1006_generalized_kneser_chromatic_eq_fourteen
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • generalized_kneser_graphThe generalized Kneser graph KG(2n, n, r) is the simple graph whose vertices are the n-element subsets of Fin (2 * n), where two distinct…
  • exists_five_finsets_cardIf the binomial coefficient C(m,r) is at least 5, there are five pairwise distinct r-element subsets of Fin m.

The proof, explained

The theorem establishes that the vertex set of the generalized Kneser graph $KG(2n, n, r)$, formed by the $n$-element subsets of $\mathrm{Fin}(2n)$, has cardinality $\binom{2n}{n}$. The proof proceeds by simplification, which computes the cardinality of $n$-element subsets of a $(2n)$-element set directly using standard combinatorial identities from the library.

  1. The cardinality of the set of $n$-element subsets of $\mathrm{Fin}(2n)$ is $\binom{2n}{n}$. automation

    The simplifier rewrites the cardinality of the subtype $\{s : \mathrm{Finset}(\alpha) \mid s.\mathrm{card} = n\}$ to $\binom{|\alpha|}{n}$, and for $\alpha = \mathrm{Fin}(2n)$ this evaluates to $\binom{2n}{n}$ because $|\mathrm{Fin}(2n)| = 2n$. Both sides become identical, closing the goal.

    line 3

    uses exists_five_finsets_card

        Fintype.card {s : Finset (Fin (2 * n)) // s.card = n} = Nat.choose (2 * n) n := by first | exact exists_five_finsets_card | (apply exists_five_finsets_card <;> assumption) | (apply exists_five_finsets_card <;> simp_all) | simpa using exists_five_finsets_card
exists_five_finsets_card
If $5 \le \binom{m}{r}$, then there exist five pairwise distinct $r$-element subsets of $\mathrm{Fin}(m)$.

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

/-- The number of vertices in the generalized Kneser graph KG(2n, n, r) is (2n choose n). -/theorem card_generalized_kneser_graph_verts (n : ℕ) :    Fintype.card {s : Finset (Fin (2 * n)) // s.card = n} = Nat.choose (2 * n) n := by first | exact exists_five_finsets_card | (apply exists_five_finsets_card <;> assumption) | (apply exists_five_finsets_card <;> simp_all) | simpa using exists_five_finsets_card
See it in the graphDiscuss this resultChallenge it