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
- lly_positive_edge_connectivity_threshold_fivec(5) = 2: every connected graph on 5 vertices with edge-connectivity at least 2 has positive Lin–Lu–Yau curvature on every edge, while the…
- not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- edge_connectivity_ge_min_degree_mul_lly_lower_bound_twoEvery finite connected graph of diameter 2 has κ'(G) ≥ δ(G) · κ_LLY^(2)(G).
- lly_positive_edge_connectivity_thresholdc(n): the smallest natural number k such that every connected simple graph on n vertices with edge-connectivity at least k has positive…
- lly_curvature_pos_of_edge_connectivity_geIf a finite connected graph on n vertices has edge-connectivity κ'(G) ≥ 2n/3 − 1, then every edge xy has κ_LLY(x, y) > 0.
- graph_edge_connectivity_eq_minDegree_of_diam_twoPlesník's theorem: every finite connected graph of diameter 2 has edge-connectivity equal to its minimum degree, κ'(G) = δ(G).
- one_le_graph_edge_connectivity_of_connectedA connected graph on at least two vertices has edge-connectivity at least 1.
- edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_bound_of_eq_minDegreeOP-164 holds for every finite connected graph whose edge-connectivity equals its minimum degree: then κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) for…
- graph_edge_connectivity_le_minDegreeEdge-connectivity is at most the minimum degree, κ'(G) ≤ δ(G) (for at least two vertices).
- lly_positive_edge_connectivity_threshold_threec(3) = 0: every connected graph on 3 vertices has positive Lin–Lu–Yau curvature on every edge, whatever its edge-connectivity.
- exists_min_cut_partitionFor every finite connected graph G on at least two vertices, there exists a non-trivial cut partition (X, X^c) with crossing edges at most…
- five_vertex_t_star_connected_edge_connectivityThe T-graph (edges 0–1, 0–3, 0–4, 1–2) is connected and has edge-connectivity κ' = 1 (it is a tree).
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}