AFTD Auto-Formalizing Theoretical Domains

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
  • tauFor a vertex u in a finite simple graph G on vertex type V, tau G u is the integer (max_induced_linear_forest G : ℤ) * ((Fintype.card V :…
  • deltaFor a finite simple graph G on vertex type V, delta G is the integer (max_induced_linear_forest G : ℤ) * (Fintype.card V : ℤ) *…

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