simple_graph_star_forest_not_adj_of_ne
Sanity: vertices in different components of the star forest are not adjacent.
Statement
theorem simple_graph_star_forest_not_adj_of_ne (q : ℕ) (n : Fin q → ℕ) (u v : Σ i : Fin q, Option (Fin (n i)))
(h : u.1 ≠ v.1) : ¬ (simple_graph_star_forest q n).Adj u v- Source
- sanity lemma for simple_graph_star_forest
- 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…
The proof, explained
We argue by contradiction: assuming vertices u and v are adjacent, the definition of adjacency requires that they share the same component index (u.1 = v.1). This directly contradicts the hypothesis u.1 ≠ v.1.
Vertices with different component indices are not adjacent.
Assume for contradiction that u and v are adjacent (hadj). By the definition of adjacency in simple_graph_star_forest, adjacent vertices must belong to the same component, so hadj.1 gives u.1 = v.1. This contradicts the hypothesis h that u.1 ≠ v.1.
fun hadj => h hadj.1
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_not_adj_of_ne (q : ℕ) (n : Fin q → ℕ) (u v : Σ i : Fin q, Option (Fin (n i))) (h : u.1 ≠ v.1) : ¬ (simple_graph_star_forest q n).Adj u v := fun hadj => h hadj.1