AFTD Auto-Formalizing Theoretical Domains

tree_markable_edges

def

The number of markable edges of a graph is the number of edges not incident to any leaf.

Statement

noncomputable def tree_markable_edges {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ
Defined in
arXiv:2610.15145, Section 1 and 2
Verified
25 Oct 2026
Axioms
none listed
Used by 2
  • arrows_markable_unmarked_emptyIn the empty position the number of unmarked markable edges equals the number of markable (non-pendant) edges, tree_markable_edges.
  • arrows_parity_of_strategy_classLet T be a finite tree and S a class of positions of the Game of Arrows on T that contains the empty position, such that from every…

Read back from the Lean

Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, tree_markable_edges G is defined as the number of edges e of G such that every vertex v incident to e has degree in G not equal to 1 (i.e., neither endpoint of e is a degree-1 vertex).

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 number of markable edges of a graph: edges where neither endpoint is a leaf. -/
noncomputable def tree_markable_edges {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ := (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.degree v ≠ 1)).card
See it in the graphDiscuss this resultChallenge it