simple_graph_star_forest_adj_centre_leaf
Sanity: in the star forest, the centre of component i is adjacent to each of its leaves.
Statement
theorem simple_graph_star_forest_adj_centre_leaf (q : ℕ) (n : Fin q → ℕ) (i : Fin q) (j : Fin (n i)) :
(simple_graph_star_forest q n).Adj ⟨i, none⟩ ⟨i, some j⟩- Source
- sanity lemma for simple_graph_star_forest
- Verified
- 23 Oct 2026
- Axioms
propext- Built on 1
- simple_graph_star_forestThe star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q}: component i has a centre (i, none) adjacent to its n_i leaves (i, some j), and there are no…
- 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
The proof verifies adjacency directly from the definition of the star forest graph. Two vertices in the graph are adjacent when they belong to the same component and one is the component's centre while the other is a leaf. Here, both vertices have component index $i$, the first has coordinate $\mathrm{none}$, and the second has coordinate $\mathrm{some}\ j \ne \mathrm{none}$, satisfying the adjacency condition immediately.
The vertex $\langle i, \mathrm{none}\rangle$ is adjacent to $\langle i, \mathrm{some}\ j\rangle$ in the star forest.
By definition of `simple_graph_star_forest`, two vertices are adjacent if they share the same component index and either the first is the centre ($\mathrm{none}$) while the second is a leaf ($\ne \mathrm{none}$), or vice versa. Both vertices have component index $i$, which matches by reflexivity. For the second condition, we take the left disjunct via `Or.inl`: the first vertex has coordinate $\mathrm{none}$ (by reflexivity), and the second has coordinate $\mathrm{some}\ j \ne \mathrm{none}$, which holds because the `Option` constructors `some` and `none` are distinct (closed by `simp`).
uses
Or.inl⟨rfl, Or.inl ⟨rfl, by simp⟩⟩
Or.inl- From a proof of a proposition $A$, infers the disjunction $A \lor 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 simple_graph_star_forest_adj_centre_leaf (q : ℕ) (n : Fin q → ℕ) (i : Fin q) (j : Fin (n i)) : (simple_graph_star_forest q n).Adj ⟨i, none⟩ ⟨i, some j⟩ := ⟨rfl, Or.inl ⟨rfl, by simp⟩⟩