exists_adj_of_complete_bipartite_one_isContained
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
- simple_graph_size_ramsey_star_star_forest_edges_geLower bound of Lemma 2.3 of arXiv:2610.25958. Every finite graph G with G → (K_{1,p}, ⊔_i K_{1,n_i}) has at least ∑_i (p + n_i - 1) edges.
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.
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.
obtain ⟨f⟩ := hThe 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).
uses
Sum.inr_injectiverefine ⟨f (Sum.inl 0), fun j => f (Sum.inr j), fun a b hab => Sum.inr_injective (f.injective hab), fun j => ?_⟩
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.
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
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.
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)