graph_edge_connectivity_le_minDegree
Edge-connectivity is at most the minimum degree, κ'(G) ≤ δ(G) (for at least two vertices).
Statement
theorem graph_edge_connectivity_le_minDegree {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] : graph_edge_connectivity G ≤ G.minDegree
- Source
- Sanity check of the definitions of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 1 (the classical bound κ(G) ≤ κ'(G) ≤ δ(G) quoted there).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_edge_connectivityThe edge-connectivity κ'(G): the largest k such that removing fewer than k edges never disconnects G (0 for a disconnected graph; 0 also…
- Used by 4
- 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…
- 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).
- 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).
The proof, explained
The edge-connectivity κ'(G) is defined as the supremum of all k ∈ ℕ such that G is k-edge-connected. To prove κ'(G) ≤ δ(G), the argument applies the upper-bound property of suprema, which reduces the claim to showing that 0 is in the set and that every such k satisfies k ≤ δ(G). The upper bound holds because G has a vertex v of degree δ(G), and k-edge-connectivity forces k to be bounded by the degree of every vertex.
To show that the edge-connectivity of G is at most its minimum degree, it suffices to show that the set of connectivity values is nonempty and bounded above by the minimum degree.
Unfolding the definition of edge-connectivity as the supremum of {k | G.IsEdgeConnected k}, applying csSup_le reduces the inequality sSup {k | G.IsEdgeConnected k} ≤ G.minDegree to two subgoals: verifying that the set is nonempty, and showing that every k in the set satisfies k ≤ G.minDegree.
uses
csSup_ledsimp [graph_edge_connectivity] apply csSup_le
The set of integers k for which G is k-edge-connected is nonempty.
The integer 0 is a witness: every graph is 0-edge-connected by SimpleGraph.IsEdgeConnected.zero.
uses
SimpleGraph.IsEdgeConnected.zero· exact ⟨0, SimpleGraph.IsEdgeConnected.zero⟩Every integer k for which G is k-edge-connected is at most the minimum degree of G.
Fix an arbitrary k such that G is k-edge-connected. Since G is finite and nontrivial, G.exists_minimal_degree_vertex provides a vertex v such that G.minDegree = G.degree v. Rewriting with this equality reduces the goal to k ≤ G.degree v, which follows immediately from hk.le_degree since G is k-edge-connected.
uses
G.exists_minimal_degree_vertex,hk.le_degree· intro k hk obtain ⟨v, hv⟩ := G.exists_minimal_degree_vertex rw [hv] exact hk.le_degree
csSup_le- In a conditionally complete lattice, the supremum of a set is at most an upper bound a whenever the set is nonempty and every element is at most a.
SimpleGraph.IsEdgeConnected.zero- Every simple graph is 0-edge-connected.
G.exists_minimal_degree_vertex- In any finite, nonempty simple graph, there exists a vertex whose degree equals the minimum degree of the graph.
hk.le_degree- If a nontrivial simple graph is k-edge-connected, then k is at most the degree of any vertex u.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem graph_edge_connectivity_le_minDegree {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] : graph_edge_connectivity G ≤ G.minDegree := by dsimp [graph_edge_connectivity] apply csSup_le · exact ⟨0, SimpleGraph.IsEdgeConnected.zero⟩ · intro k hk obtain ⟨v, hv⟩ := G.exists_minimal_degree_vertex rw [hv] exact hk.le_degree