AFTD Auto-Formalizing Theoretical Domains

is_linear_forest

def

A simple graph is a linear forest if it is acyclic and every vertex has at most two neighbors.

Statement

def is_linear_forest {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.12781 Section 1
Verified
12 Nov 2026
Axioms
none listed
Used by 2
  • max_induced_linear_forestThe maximum order of an induced linear forest in a finite simple graph G on a finite vertex type V is the supremum in ℕ of the…
  • is_linear_forest_botThe empty simple graph on any vertex type is a linear forest.

Read back from the Lean

Given a type V and a simple graph G on V, is_linear_forest G asserts that G is acyclic and for every vertex v : V, the extended cardinality (encard) of the set of neighbors of v in G is at most 2 (i.e., every vertex has degree at most 2).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A simple graph is a linear forest if it is acyclic and every vertex has degree at most 2. -/
def is_linear_forest {V : Type*} (G : SimpleGraph V) : Prop := G.IsAcyclic ∧ ∀ v : V, (G.neighborSet v).encard ≤ 2
See it in the graphDiscuss this resultChallenge it