simple_graph_star_forest_adj_iff
Adjacency in the star forest: same component, one vertex the centre and the other a leaf.
Statement
theorem simple_graph_star_forest_adj_iff (q : ℕ) (n : Fin q → ℕ) (u v : Σ i : Fin q, Option (Fin (n i))) :
(simple_graph_star_forest q n).Adj u v ↔
u.1 = v.1 ∧ ((u.2 = none ∧ v.2 ≠ none) ∨ (u.2 ≠ none ∧ v.2 = none))- 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
- none — Lean reports it depends on no axioms
- 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_star_forest_edgeSet_ncardThe star forest K_{1,n_1} ⊔ ... ⊔ K_{1,n_q} has ∑ n_i edges.
The proof, explained
The theorem states the adjacency condition for the star forest graph: two vertices are adjacent if and only if they belong to the same star component and one is the centre while the other is a leaf. Because this condition is the literal definition of the graph's adjacency relation, the two sides of the iff are definitionally identical, and the proof finishes in one step by reflexivity (Iff.rfl).
The adjacency relation (simple_graph_star_forest q n).Adj u v is equivalent to u and v sharing the same component index with exactly one vertex being the centre (none) and the other a leaf (≠ none).
In the definition of simple_graph_star_forest, the adjacency relation Adj u v is defined directly as u.1 = v.1 ∧ ((u.2 = none ∧ v.2 ≠ none) ∨ (u.2 ≠ none ∧ v.2 = none)). Because the left-hand and right-hand sides are definitionally equal, the equivalence holds reflexively by Iff.rfl.
uses
Iff.rflIff.rfl
Iff.rfl- every proposition is logically equivalent to itself
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem simple_graph_star_forest_adj_iff (q : ℕ) (n : Fin q → ℕ) (u v : Σ i : Fin q, Option (Fin (n i))) : (simple_graph_star_forest q n).Adj u v ↔ u.1 = v.1 ∧ ((u.2 = none ∧ v.2 ≠ none) ∨ (u.2 ≠ none ∧ v.2 = none)) := Iff.rfl