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