AFTD Auto-Formalizing Theoretical Domains

is_subcubic_tree

def

A finite simple graph is a subcubic tree if it is connected, acyclic, and every vertex has degree at most 3.

Statement

def is_subcubic_tree {α : Type*} [Fintype α] (G : SimpleGraph α) : Prop
Defined in
arXiv:2610.39863, Section 3
Verified
02 Nov 2026
Axioms
none listed
Used by 3
  • tbt_optFor a finite type V and a simple graph T on V, tbt_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H id over all…
  • tbt_opt_eq_sn_opt_of_is_subcubicFor every finite type V with at least two elements and every subcubic tree T on V, tbt_opt T equals tbt_sn_opt T.
  • tbt_sn_optFor a finite type V and a simple graph T on V, tbt_sn_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H f over all…

Read back from the Lean

Given a finite type α and a simple graph G on α, is_subcubic_tree G asserts that G is a tree (i.e., G.IsTree) and that for every vertex v : α, the degree of v in G is less than or equal to 3.

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 finite simple graph is a subcubic tree (an unrooted binary tree) if it is a tree and every vertex has degree at most 3. -/
def is_subcubic_tree {α : Type*} [Fintype α] (G : SimpleGraph α) : Prop := G.IsTree ∧ open Classical in ∀ v : α, G.degree v ≤ 3
See it in the graphDiscuss this resultChallenge it