AFTD Auto-Formalizing Theoretical Domains

simple_graph_j

def

The number of connected spanning subgraphs j(G) of a finite simple graph G.

Statement

noncomputable def simple_graph_j {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
Defined in
arXiv:2610.36749, Section 1
Verified
30 Oct 2026
Axioms
none listed

Read back from the Lean

Given a finite type V and a simple graph G on V, simple_graph_j G is defined as the number (cardinality) of edge subsets C : Finset (Sym2 V) such that C ⊆ G.edgeSet and the simple graph on vertex type V with edge set C is connected (that is, V is nonempty and every pair of vertices in V is reachable from one another via edges in C). In other words, it counts the number of connected spanning subgraphs of G.

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 connected spanning subgraphs of a finite simple graph. -/
noncomputable def simple_graph_j {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := by
  classical
  exact (Finset.univ.filter (fun C : Finset (Sym2 V) =>
    (C : Set (Sym2 V)) ⊆ G.edgeSet ∧
      (SimpleGraph.fromEdgeSet (C : Set (Sym2 V))).Connected)).card
See it in the graphDiscuss this resultChallenge it