AFTD Auto-Formalizing Theoretical Domains

complete_bipartite_one_isContained_of_adj

theoremverified

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

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.

  1. 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.

    line 4

    uses Sum.elim

      refine ⟨⟨⟨Sum.elim (fun _ => v) g, ?_⟩, ?_⟩⟩
  2. 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`).

    lines 5–8

      · intro a b hab
        rcases a with a | a <;> rcases b with b | b <;> simp at hab ⊢
        · exact hadj b
        · exact (hadj a).symm
  3. 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`).

    lines 9–14

    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.

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 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
See it in the graphDiscuss this resultChallenge it