complete_bipartite_one_isContained_of_adj
A vertex v with p distinct neighbours g(0), ..., g(p-1) in R gives a copy of the star K_{1,p} in R.
Statement
theorem complete_bipartite_one_isContained_of_adj {V : Type*} (R : SimpleGraph V) (p : ℕ) (v : V) (g : Fin p → V) (hg : Function.Injective g) (hadj : ∀ j, R.Adj v (g j)) : (completeBipartiteGraph (Fin 1) (Fin p)).IsContained R
- 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 2
- 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.
- simple_graph_size_ramsey_star_star_forest_arrowsUpper bound of Lemma 2.3 of arXiv:2610.25958. Some finite graph with ∑_i (p + n_i - 1) edges arrows (K_{1,p}, ⊔_i K_{1,n_i}): the disjoint…
The proof, explained
To show that the star graph $K_{1,p}$ is contained in $R$, we construct a graph embedding from $K_{1,p}$ into $R$ by mapping the central vertex of $\text{Fin } 1$ to $v$ and the $p$ leaf vertices of $\text{Fin } p$ to the distinct neighbours $g(j)$. Adjacency is preserved because all edges in $K_{1,p}$ connect the center to a leaf, matching the hypothesis that $v$ is adjacent to each $g(j)$. Injectivity follows from the injectivity of $g$ and the fact that a vertex cannot equal any of its neighbours in a simple graph.
There exists a graph homomorphism from $K_{1,p}$ to $R$ whose vertex map sends the unique left vertex to $v$ and the $j$-th right vertex to $g(j)$.
To show containment of the complete bipartite graph $K_{1,p}$, we define an embedding candidate whose underlying vertex function on $\text{Fin } 1 \oplus \text{Fin } p$ maps the left vertex to $v$ and each right vertex $j$ to $g(j)$ using `Sum.elim`. This leaves two obligations: that this map preserves adjacency and that it is injective.
uses
Sum.elimrefine ⟨⟨⟨Sum.elim (fun _ => v) g, ?_⟩, ?_⟩⟩
The candidate map preserves adjacency.
Let $a, b \in \text{Fin } 1 \oplus \text{Fin } p$ be adjacent in $K_{1,p}$. Case analysis on whether each vertex is in the left or right part leaves only two possible edge configurations: $a \in \text{Fin } 1$ with $b \in \text{Fin } p$, or vice versa (edges within the same part are impossible and discarded by simplification). In the first case, the vertices map to $v$ and $g(b)$, which are adjacent in $R$ by `hadj b`. In the second case, they map to $g(a)$ and $v$, which are adjacent by symmetry of adjacency in $R$ (`(hadj a).symm`).
· intro a b hab rcases a with a | a <;> rcases b with b | b <;> simp at hab ⊢ · exact hadj b · exact (hadj a).symm
The candidate map is injective on vertices.
Suppose two vertices $a, b \in \text{Fin } 1 \oplus \text{Fin } p$ have the same image. We inspect all four cases: when both are in $\text{Fin } 1$, they are equal because $\text{Fin } 1$ has only one element (`Subsingleton.elim`); when one is in $\text{Fin } 1$ and the other is in $\text{Fin } p$, their images would satisfy $v = g(j)$, contradicting the fact that adjacent vertices in a simple graph cannot be equal (`(hadj j).ne`); and when both are in $\text{Fin } p$, their images satisfy $g(a) = g(b)$, which implies $a = b$ by the injectivity of $g$ (`hg`).
uses
Subsingleton.elim· intro a b hab rcases a with a | a <;> rcases b with b | b <;> simp at hab ⊢ · exact Subsingleton.elim a b · exact (hadj b).ne hab · exact (hadj a).ne hab.symm · exact hg hab
Sum.elim- Given functions from α and β into γ, defines the function on α ⊕ β by case analysis on the sum.
Subsingleton.elim- Any two terms of a subsingleton type (such as `Fin 1`) are equal.
- The tactic `rcases ... <;> simp at hab ⊢` handles all four partition cases simultaneously and automatically discards impossible edges within the same partition, where the adjacency hypothesis reduces to `False`.
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 complete_bipartite_one_isContained_of_adj {V : Type*} (R : SimpleGraph V) (p : ℕ) (v : V) (g : Fin p → V) (hg : Function.Injective g) (hadj : ∀ j, R.Adj v (g j)) : (completeBipartiteGraph (Fin 1) (Fin p)).IsContained R := by refine ⟨⟨⟨Sum.elim (fun _ => v) g, ?_⟩, ?_⟩⟩ · intro a b hab rcases a with a | a <;> rcases b with b | b <;> simp at hab ⊢ · exact hadj b · exact (hadj a).symm · intro a b hab rcases a with a | a <;> rcases b with b | b <;> simp at hab ⊢ · exact Subsingleton.elim a b · exact (hadj b).ne hab · exact (hadj a).ne hab.symm · exact hg hab