AFTD Auto-Formalizing Theoretical Domains

simple_graph_star_forest_not_adj_of_ne

theoremverified

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.

  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.

    line 3

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