AFTD Auto-Formalizing Theoretical Domains

exists_adj_of_complete_bipartite_one_isContained

theoremverified

A copy of the star K_{1,p} in R gives a vertex with p distinct R-neighbours.

Statement

theorem exists_adj_of_complete_bipartite_one_isContained {V : Type*} (R : SimpleGraph V) (p : ℕ)
    (h : (completeBipartiteGraph (Fin 1) (Fin p)).IsContained R) :
    ∃ v : V, ∃ g : Fin p → V, Function.Injective g ∧ ∀ j, R.Adj v (g j)
Source
helper for arXiv:2610.25958 (Size Ramsey numbers of star forests with two components on one side), Lemma 2.3 (PR-280)
Verified
23 Oct 2026
Axioms
Quot.soundpropext
Used by 1

The proof, explained

An embedding of the star graph K_{1,p} into R provides an injective homomorphism from the complete bipartite graph on Fin 1 ⊕ Fin p into R. The center vertex is the image of the unique element in Fin 1, and the p neighbours are the images of the elements of Fin p. Because the embedding is injective, these p neighbours are all distinct, and because it preserves edges, each is adjacent to the center vertex in R.

  1. There is an embedding of the complete bipartite graph K_{1,p} into R.

    The hypothesis that R contains K_{1,p} as a subgraph means there exists a graph embedding f from K_{1,p} (with vertex set Fin 1 ⊕ Fin p) into R, which is an injective map preserving edges.

    line 4

      obtain ⟨f⟩ := h
  2. The images of the two parts of K_{1,p} define a vertex v and an injective family of p vertices g : Fin p → V.

    We pick the center vertex v to be f(Sum.inl 0) and define g(j) = f(Sum.inr j). To see that g is injective, suppose g(a) = g(b). By injectivity of f, Sum.inr a = Sum.inr b, and by Sum.inr_injective, a = b. This leaves only the requirement that v is adjacent to each g(j).

    lines 5–6

    uses Sum.inr_injective

      refine ⟨f (Sum.inl 0), fun j => f (Sum.inr j), fun a b hab => Sum.inr_injective (f.injective hab),
        fun j => ?_⟩
  3. The vertex v is adjacent in R to each g(j).

    Because f is a graph homomorphism, it preserves adjacency. In K_{1,p}, the single left vertex Sum.inl 0 is connected to every right vertex Sum.inr j by definition of a complete bipartite graph, which simp verifies. Applying f.toHom.map_adj then shows that v and g(j) are adjacent in R.

    line 7

      exact f.toHom.map_adj (by simp)
Sum.inr_injective
The right injection `Sum.inr` into a sum type is injective, so `Sum.inr a = Sum.inr b` implies `a = b`.

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

theorem exists_adj_of_complete_bipartite_one_isContained {V : Type*} (R : SimpleGraph V) (p : ℕ)    (h : (completeBipartiteGraph (Fin 1) (Fin p)).IsContained R) :    ∃ v : V, ∃ g : Fin p → V, Function.Injective g ∧ ∀ j, R.Adj v (g j) := by  obtain ⟨f⟩ := h  refine ⟨f (Sum.inl 0), fun j => f (Sum.inr j), fun a b hab => Sum.inr_injective (f.injective hab),    fun j => ?_⟩  exact f.toHom.map_adj (by simp)
See it in the graphDiscuss this resultChallenge it