card_generalized_kneser_graph_verts
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.
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.
uses
exists_five_finsets_cardFintype.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)$.
- The tactic on line 3 is a `first | ...` trial sequence generated by automated proof search. The earlier branches fail, and the closing branch `simpa using exists_five_finsets_card` succeeds purely through simplification (`simp`), which evaluates the cardinality of the subtype of $n$-element subsets directly without actually using `exists_five_finsets_card`.
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.
/-- 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