AFTD Auto-Formalizing Theoretical Domains

simple_graph_j_e

def

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
See it in the graphDiscuss this resultChallenge it