AFTD Auto-Formalizing Theoretical Domains

simple_graph_star_forest_adj_centre_leaf

theoremverified

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

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.

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

    line 3

    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

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