max_induced_linear_forest
def
The 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 cardinalities of all vertex subsets s : Finset V such that the induced subgraph on s is a linear forest.
Statement
noncomputable def max_induced_linear_forest {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2611.12781 Section 1
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 1
- is_linear_forestA simple graph is a linear forest if it is acyclic and every vertex has at most two neighbors.
- Used by 2
Read back from the Lean
For a finite type V and a simple graph G on V, max_induced_linear_forest G is defined as the supremum (sSup in ℕ) of the set of all natural numbers n such that there exists a finset s of vertices of V with s.card = n whose induced subgraph G.induce (s : Set V) is a linear forest (meaning it is acyclic and every vertex in the induced subgraph 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
/-- The maximum order of an induced linear forest in a finite graph G. -/ noncomputable def max_induced_linear_forest {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := sSup {n : ℕ | ∃ s : Finset V, is_linear_forest (G.induce (s : Set V)) ∧ s.card = n}