AFTD Auto-Formalizing Theoretical Domains

simple_graph_star_forest_adj_iff

theoremverified

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

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

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

    line 4

    uses Iff.rfl

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