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