AFTD Auto-Formalizing Theoretical Domains

generalized_kneser_graph_adj

theoremverified

In the generalized Kneser graph KG(2n, n, r), two vertices s and t are adjacent if and only if s ≠ t and the cardinality of their intersection s.1 ∩ t.1 is strictly less than r.

Statement

theorem generalized_kneser_graph_adj (n r : ℕ)
    (s t : {s : Finset (Fin (2 * n)) // s.card = n}) :
    (generalized_kneser_graph n r).Adj s t ↔ s ≠ t ∧ (s.1 ∩ t.1).card < r
Source
arXiv:2611.04486 Sec. 1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…
Used by 1

Read back from the Lean

For all natural numbers n and r, and all vertices s and t (which are n-element subsets of Fin (2 * n)), s and t are adjacent in generalized_kneser_graph n r if and only if s ≠ t and the cardinality of the intersection s ∩ t is strictly less than r.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

In the definition of the generalized Kneser graph KG(2n, n, r), two vertices s and t are defined to be adjacent if and only if s ≠ t and |s ∩ t| < r. Since the left-hand and right-hand sides of the equivalence are definitionally equal, the statement holds immediately by reflexivity of equivalence.

  1. The adjacency condition in the generalized Kneser graph is definitionally equal to s ≠ t ∧ |s ∩ t| < r.

    By definition of `generalized_kneser_graph`, the adjacency relation `(generalized_kneser_graph n r).Adj s t` is defined directly as `s ≠ t ∧ (s.1 ∩ t.1).card < r`. Because both sides of the `↔` are definitionally identical, the equivalence holds by reflexivity (`Iff.rfl`).

    line 4

    uses Iff.rfl

        (generalized_kneser_graph n r).Adj s t ↔ s ≠ t ∧ (s.1 ∩ t.1).card < r := Iff.rfl
Iff.rfl
Every proposition is equivalent to itself (P ↔ P).

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Adjacency criterion for the generalized Kneser graph KG(2n, n, r). -/theorem generalized_kneser_graph_adj (n r : ℕ)    (s t : {s : Finset (Fin (2 * n)) // s.card = n}) :    (generalized_kneser_graph n r).Adj s t ↔ s ≠ t ∧ (s.1 ∩ t.1).card < r := Iff.rfl
See it in the graphDiscuss this resultChallenge it