AFTD Auto-Formalizing Theoretical Domains

tau

def

For 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 : ℤ) - 1) - 2 * (graph_vertex_dist_sum G u : ℤ).

Statement

noncomputable def tau {V : Type*} [Fintype V] (G : SimpleGraph V) (u : V) : ℤ
Defined in
arXiv:2611.12781, Section 2, equation (169)
Verified
13 Nov 2026
Axioms
none listed
Built on 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…
  • graph_vertex_dist_sumFor a vertex u in a finite simple graph G on vertex type V, graph_vertex_dist_sum G u is the sum ∑ v : V, G.dist u v of shortest-path…

Read back from the Lean

For a finite type V, a simple graph G on V, and a vertex u : V, tau G u is the integer defined by: L * (|V| - 1) - 2 * (∑ v : V, G.dist u v) where: - L is max_induced_linear_forest G, defined as the supremum (in ℕ) of the cardinalities of finite subsets s ⊆ V such that the induced subgraph G.induce s is a linear forest (acyclic with maximum degree at most 2); - |V| is Fintype.card V, the total number of vertices in V; - ∑ v : V, G.dist u v is the sum of graph distances from u to all vertices v ∈ V (where G.dist u v is 0 if v is unreachable from u).

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 vertex tau invariant: L(G)(n-1) - 2 * w_G(u). -/
noncomputable def tau {V : Type*} [Fintype V] (G : SimpleGraph V) (u : V) : ℤ := (max_induced_linear_forest G : ℤ) * ((Fintype.card V : ℤ) - 1) - 2 * (graph_vertex_dist_sum G u : ℤ)
See it in the graphDiscuss this resultChallenge it