simple_graph_j_e
The number of connected spanning subgraphs j_e(G) of a finite simple graph G containing a given edge e.
Statement
noncomputable def simple_graph_j_e {V : Type*} [Fintype V] (G : SimpleGraph V) (e : Sym2 V) : ℕ
- Defined in
- arXiv:2610.36749, Section 1
- Verified
- 30 Oct 2026
- Axioms
- none listed
Read back from the Lean
A definition of simple_graph_j_e, which takes a finite type V, a simple graph G on V, and an edge e : Sym2 V, and returns the natural number of edge sets C : Finset (Sym2 V) such that:
1. C (as a set) is a subset of G.edgeSet,
2. e ∈ C, and
3. the graph on vertex set V with edge set C, given by SimpleGraph.fromEdgeSet (C : Set (Sym2 V)), is connected (meaning V is nonempty and every pair of vertices in V is connected by a path of edges in C).
In other words, it returns the number of connected spanning subgraphs of G containing the edge e.
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 containing an edge e. -/ noncomputable def simple_graph_j_e {V : Type*} [Fintype V] (G : SimpleGraph V) (e : Sym2 V) : ℕ := by classical exact (Finset.univ.filter (fun C : Finset (Sym2 V) => (C : Set (Sym2 V)) ⊆ G.edgeSet ∧ e ∈ C ∧ (SimpleGraph.fromEdgeSet (C : Set (Sym2 V))).Connected)).card