AFTD Auto-Formalizing Theoretical Domains

op_193_kneser_hom_sum_inl

theoremverified

For 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 (G ⊔ H)-stable Kneser graph KG(G ⊔ H, k).

Statement

theorem op_193_kneser_hom_sum_inl {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (k : ℕ) :
    Nonempty (GStableKneser G k →g GStableKneser (G.sum H) k)
Source
Mathlib.Combinatorics.SimpleGraph.Sum
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • g_stable_kneser_adjTwo 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…
Used by 1

Read back from the Lean

For any types $V$ and $W$, any simple graphs $G$ on $V$ and $H$ on $W$, and any natural number $k$, there exists a graph homomorphism from the stable Kneser graph GStableKneser G k to GStableKneser (G.sum H) k (where G.sum H is the disjoint union graph of $G$ and $H$ on $V \oplus W$).

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 proof constructs a graph homomorphism from KG(G, k) to KG(G ⊕ H, k) by mapping each independent k-set s of G to its image under the canonical inclusion inl : V ↪ V ⊕ W. Because inl is an embedding and there are no edges between summands in the graph sum G ⊕ H, the image inl(s) is an independent set of size k. Furthermore, inl preserves disjointness and injectivity on finite sets, ensuring that adjacent vertices in KG(G, k) map to adjacent vertices in KG(G ⊕ H, k).

  1. Define the candidate vertex map f sending each independent k-set s of G to its image under the canonical inclusion into V ⊕ W, reducing well-definedness to verifying independence and cardinality.

    We define the vertex map f by applying the canonical embedding inl : V ↪ V ⊕ W to the underlying finite set of each independent k-set s of G. To show that inl(s) is a valid vertex of KG(G ⊕ H, k), we split the IsNIndepSet condition into two subgoals: proving that inl(s) is an independent set in G ⊕ H, and proving that its cardinality is k.

    lines 4–6

      let f : { s : Finset V // G.IsNIndepSet k s } → { t : Finset (V ⊕ W) // (G.sum H).IsNIndepSet k t } :=
        fun s => ⟨s.1.map Function.Embedding.inl, by
          refine ⟨?_, ?_⟩
  2. The image inl(s) is an independent set in the graph sum G ⊕ H.

    Rewriting the finset image as a set image using Finset.coe_map, consider two distinct elements in inl(s), which must be of the form inl(u) and inl(v) for some u, v ∈ s. Unfolding the definition of adjacency in the graph sum (SimpleGraph.sum), inl(u) and inl(v) are adjacent in G ⊕ H if and only if u and v are adjacent in G. Since u and v are distinct vertices in the independent set s, they cannot be adjacent in G, giving a contradiction.

    lines 7–14

    uses Finset.coe_map, SimpleGraph.sum

          · rw [Finset.coe_map]
            rintro _ ⟨u, hu, rfl⟩ _ ⟨v, hv, rfl⟩ hne
            dsimp [SimpleGraph.sum]
            intro h
            have : u ≠ v := by
              rintro rfl
              exact hne rfl
            exact s.2.isIndepSet hu hv this h
  3. The image inl(s) has cardinality k, completing the definition of the vertex map f.

    Because mapping along an injective embedding preserves the cardinality of a finite set (Finset.card_map), the cardinality of inl(s) equals the cardinality of s, which is k by the assumption that s is a k-independent set.

    lines 15–16

    uses Finset.card_map

          · rw [Finset.card_map]
            exact s.2.card_eq⟩
  4. To show that f defines a graph homomorphism, it suffices to show that f(s) ≠ f(t) for adjacent vertices s and t, as their disjointness is preserved.

    We package f into a graph homomorphism. By g_stable_kneser_adj, adjacency in a stable Kneser graph means that two independent sets are disjoint and distinct. Given adjacent vertices s and t, their images f(s) and f(t) are disjoint because mapping along an embedding preserves disjointness (Finset.disjoint_map), leaving only the requirement to show that f(s) ≠ f(t).

    lines 17–21

    uses g_stable_kneser_adj, Finset.disjoint_map

      refine ⟨⟨f, ?_⟩⟩
      intro s t h
      rw [g_stable_kneser_adj] at h ⊢
      rcases h with ⟨hdisj, hne⟩
      refine ⟨(Finset.disjoint_map Function.Embedding.inl).mpr hdisj, ?_⟩
  5. The images f(s) and f(t) are distinct, completing the proof that f is a graph homomorphism.

    Suppose for contradiction that f(s) = f(t). Then their underlying finite sets inl(s) and inl(t) are equal. Since inl is injective, Finset.map_injective implies s = t, which contradicts the hypothesis that s and t are distinct. Thus f(s) ≠ f(t).

    lines 22–26

    uses Finset.map_injective

      intro h_eq
      apply hne
      ext1
      have h1 : (f s).1 = (f t).1 := by rw [h_eq]
      exact Finset.map_injective Function.Embedding.inl h1
Finset.coe_map
The coercion to a set of the image of a finite set under an embedding equals the set-theoretic image under that embedding.
SimpleGraph.sum
The disjoint union of two graphs, where vertices within each summand retain their original adjacency and vertices in different summands are never adjacent.
Finset.card_map
Mapping a finite set along an injective embedding preserves its cardinality.
g_stable_kneser_adj
Two vertices in a stable Kneser graph are adjacent if and only if their underlying independent sets are disjoint and distinct.
Finset.disjoint_map
Two finite sets are disjoint if and only if their images under an injective embedding are disjoint.
Finset.map_injective
Mapping finite sets along an injective embedding is an injective operation on finite sets.

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

/-- Canonical embedding homomorphism from KG(G, k) into KG(G ⊔ H, k). -/theorem op_193_kneser_hom_sum_inl {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (k : ℕ) :    Nonempty (GStableKneser G k →g GStableKneser (G.sum H) k) := by  let f : { s : Finset V // G.IsNIndepSet k s } → { t : Finset (V ⊕ W) // (G.sum H).IsNIndepSet k t } :=    fun s => ⟨s.1.map Function.Embedding.inl, by      refine ⟨?_, ?_⟩      · rw [Finset.coe_map]        rintro _ ⟨u, hu, rfl⟩ _ ⟨v, hv, rfl⟩ hne        dsimp [SimpleGraph.sum]        intro h        have : u ≠ v := by          rintro rfl          exact hne rfl        exact s.2.isIndepSet hu hv this h      · rw [Finset.card_map]        exact s.2.card_eq⟩  refine ⟨⟨f, ?_⟩⟩  intro s t h  rw [g_stable_kneser_adj] at h ⊢  rcases h with ⟨hdisj, hne⟩  refine ⟨(Finset.disjoint_map Function.Embedding.inl).mpr hdisj, ?_⟩  intro h_eq  apply hne  ext1  have h1 : (f s).1 = (f t).1 := by rw [h_eq]  exact Finset.map_injective Function.Embedding.inl h1
See it in the graphDiscuss this resultChallenge it