AFTD Auto-Formalizing Theoretical Domains

graph_edge_connectivity

def

The edge-connectivity κ'(G): the largest k such that removing fewer than k edges never disconnects G (0 for a disconnected graph; 0 also for a single vertex, as in the paper's convention).

Statement

noncomputable def graph_edge_connectivity {V : Type*} (G : SimpleGraph V) : ℕ
Defined in
arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 1 (edge-connectivity: the minimum number of edges whose removal disconnects the graph; 0 for a single vertex); expressed through Mathlib's `SimpleGraph.IsEdgeConnected`.
Verified
10 Oct 2026
Axioms
none listed
Used by 12

Lean source view module on GitHub

/-- Edge-connectivity `κ'(G)`: the largest `k` with `G.IsEdgeConnected k` (Mathlib: deleting fewer than `k` edges keeps every pair reachable). -/
noncomputable def graph_edge_connectivity {V : Type*} (G : SimpleGraph V) : ℕ :=
  sSup {k | G.IsEdgeConnected k}
See it in the graphDiscuss this resultChallenge it