AFTD Auto-Formalizing Theoretical Domains

simple_graph_j_ef

def

The number of connected spanning subgraphs j_{ef}(G) of a finite simple graph G containing two given edges e and f.

Statement

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

Read back from the Lean

For a finite type V, a simple graph G on V, and two unordered pairs of vertices e, f : Sym2 V, simple_graph_j_ef G e f is the number (cardinality as a ℕ) of edge subsets C : Finset (Sym2 V) such that: 1. C (as a set) is a subset of the edge set of G (G.edgeSet), 2. e ∈ C, 3. f ∈ C, and 4. The simple graph on V with edge set given by C (excluding self-loops), SimpleGraph.fromEdgeSet C, is connected.

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 two edges e and f. -/
noncomputable def simple_graph_j_ef {V : Type*} [Fintype V] (G : SimpleGraph V) (e f : Sym2 V) : ℕ := by
  classical
  exact (Finset.univ.filter (fun C : Finset (Sym2 V) =>
    (C : Set (Sym2 V)) ⊆ G.edgeSet ∧ e ∈ C ∧ f ∈ C ∧
      (SimpleGraph.fromEdgeSet (C : Set (Sym2 V))).Connected)).card
See it in the graphDiscuss this resultChallenge it