one_le_graph_edge_connectivity_of_connected
A connected graph on at least two vertices has edge-connectivity at least 1.
Statement
theorem one_le_graph_edge_connectivity_of_connected {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) : 1 ≤ graph_edge_connectivity G
- Source
- Sanity check of the definitions of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 1.
- 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 2
- 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 of G is defined as the supremum of all k such that G is k-edge-connected. The proof reduces the inequality 1 ≤ graph_edge_connectivity G to showing that the set of such k is bounded above and contains 1. An upper bound is given by the degree of any chosen vertex, and 1 belongs to the set because a connected graph is preconnected, which is equivalent to 1-edge-connectivity.
To show 1 ≤ graph_edge_connectivity G, it suffices to show that the set of edge-connectivities {k | G.IsEdgeConnected k} is bounded above and contains 1.
Unfolding graph_edge_connectivity expresses it as sSup {k | G.IsEdgeConnected k}. By le_csSup, an element a is at most sSup s whenever s is bounded above and a ∈ s. Applying this with a = 1 splits the goal into two subgoals: showing that the set of k for which G is k-edge-connected is bounded above, and showing that 1 belongs to this set.
uses
le_csSupdsimp [graph_edge_connectivity] apply le_csSup
The set {k | G.IsEdgeConnected k} is bounded above by the degree of any vertex.
Since the vertex set V is nontrivial, it is nonempty, so we can choose a vertex v ∈ V. For any k such that G is k-edge-connected, k is at most the degree of v (by le_degree). Therefore, the degree G.degree v provides an explicit upper bound for {k | G.IsEdgeConnected k}.
uses
le_degree· obtain ⟨v⟩ : Nonempty V := inferInstance exact ⟨G.degree v, fun k hk ↦ hk.le_degree⟩
1 ∈ {k | G.IsEdgeConnected k}, that is, G is 1-edge-connected.
By isEdgeConnected_one, a graph is 1-edge-connected if and only if it is preconnected. Since G is assumed to be connected (hG), it is preconnected, which concludes the proof.
uses
isEdgeConnected_one· exact G.isEdgeConnected_one.mpr hG.preconnected
le_csSup- In a conditionally complete lattice, an element a is at most the supremum of a set s if s is bounded above and a ∈ s.
le_degree- If a graph on a nontrivial vertex set is k-edge-connected, then k is bounded above by the degree of any vertex.
isEdgeConnected_one- A simple graph is 1-edge-connected if and only if it is preconnected.
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 one_le_graph_edge_connectivity_of_connected {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) : 1 ≤ graph_edge_connectivity G := by dsimp [graph_edge_connectivity] apply le_csSup · obtain ⟨v⟩ : Nonempty V := inferInstance exact ⟨G.degree v, fun k hk ↦ hk.le_degree⟩ · exact G.isEdgeConnected_one.mpr hG.preconnected