AFTD Auto-Formalizing Theoretical Domains

g_stable_kneser_adj

theoremverified

Two independent k-sets s and t in the G-stable Kneser graph KG(G, k) are adjacent if and only if their underlying vertex sets are disjoint and distinct.

Statement

theorem g_stable_kneser_adj {V : Type*} (G : SimpleGraph V) (k : ℕ)
    (s t : { s : Finset V // G.IsNIndepSet k s }) :
    (GStableKneser G k).Adj s t ↔ Disjoint s.1 t.1 ∧ s ≠ t
Source
scout/2610-17884-the-chromatic-number-of-g-stable-kneser-graphs.md:108
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • GStableKneserFor a simple graph G and a natural number k, the G-stable Kneser graph KG(G, k) is the simple graph whose vertices are the independent…
Used by 2
  • op_193_hom_cycle_stepFor all integers k ≥ 2 and r ≥ 2 * k - 2, there exists a graph homomorphism from the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) to the…
  • op_193_kneser_hom_sum_inlFor any simple graphs G and H and any natural number k, there exists a graph homomorphism from the G-stable Kneser graph KG(G, k) to the…

Read back from the Lean

For any type V, any simple graph G on V, any natural number k, and any two vertices s and t of the subtype of size-k independent sets of G ({ s : Finset V // G.IsNIndepSet k s }), s and t are adjacent in GStableKneser G k if and only if their underlying finite sets s.1 and t.1 are disjoint and s ≠ t.

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

The theorem states that two vertices in the $G$-stable Kneser graph $\mathrm{KG}(G, k)$ are adjacent if and only if their underlying independent sets are disjoint and distinct. This equivalence holds by definition, as the adjacency relation in `GStableKneser` is defined by precisely this condition.

  1. Two vertices $s$ and $t$ are adjacent in the $G$-stable Kneser graph if and only if their underlying vertex sets are disjoint and distinct.

    The adjacency relation on `GStableKneser G k` is defined directly as `Disjoint s.1 t.1 ∧ s ≠ t`. Consequently, both sides of the `↔` are definitionally identical, and reflexivity closes the goal.

    line 5

      rfl

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

/-- Adjacency in the G-stable Kneser graph is given by disjointness and inequality of the independent sets. -/theorem g_stable_kneser_adj {V : Type*} (G : SimpleGraph V) (k : ℕ)    (s t : { s : Finset V // G.IsNIndepSet k s }) :    (GStableKneser G k).Adj s t ↔ Disjoint s.1 t.1 ∧ s ≠ t := by  rfl
See it in the graphDiscuss this resultChallenge it