graph_edge_connectivity_eq_minDegree_of_diam_two
Plesník's theorem: every finite connected graph of diameter 2 has edge-connectivity equal to its minimum degree, κ'(G) = δ(G).
Statement
theorem graph_edge_connectivity_eq_minDegree_of_diam_two {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : G.diam = 2) : graph_edge_connectivity G = G.minDegree
- Source
- step towards edge_connectivity_ge_min_degree_mul_lly_lower_bound_two
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- cross_cut_card_ge_minDegree_of_diam_twoPlesník's cut lemma: in a finite connected graph G with diam(G) = 2, every nontrivial vertex cut (A, Aᶜ) has at least δ(G) crossing edges.
- 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…
- graph_edge_connectivity_le_minDegreeEdge-connectivity is at most the minimum degree, κ'(G) ≤ δ(G) (for at least two vertices).
- one_le_graph_edge_connectivity_of_connectedA connected graph on at least two vertices has edge-connectivity at least 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 1
- edge_connectivity_ge_min_degree_mul_lly_lower_bound_twoEvery finite connected graph of diameter 2 has κ'(G) ≥ δ(G) · κ_LLY^(2)(G).
The proof, explained
The equality κ'(G) = δ(G) is established by proving both inequalities. The upper bound κ'(G) ≤ δ(G) holds for all nontrivial graphs by isolating a vertex of minimum degree. For the reverse inequality δ(G) ≤ κ'(G), the diameter-2 condition ensures that every cut partition has at least δ(G) crossing edges, so applying this property to a minimum cut gives the result.
The vertex set V is nontrivial (contains at least two vertices).
Because G has diameter 2, its diameter is nonzero (2 ≠ 0). By SimpleGraph.nontrivial_of_diam_ne_zero, any graph with nonzero diameter has a nontrivial vertex set.
uses
SimpleGraph.nontrivial_of_diam_ne_zerohave : Nontrivial V := SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd]; decide)
It suffices to show both κ'(G) ≤ δ(G) and δ(G) ≤ κ'(G).
By antisymmetry of the partial order on natural numbers (le_antisymm), establishing both inequalities suffices to prove equality.
uses
le_antisymmapply le_antisymmκ'(G) ≤ δ(G)
In any finite nontrivial graph, edge-connectivity is bounded above by the minimum degree (graph_edge_connectivity_le_minDegree), since cutting the edges incident to a minimum-degree vertex isolates it.
uses
graph_edge_connectivity_le_minDegree· exact graph_edge_connectivity_le_minDegree Gδ(G) ≤ κ'(G)
Choose a cut partition X, Xᶜ with nonempty sides whose number of crossing edges is at most κ'(G) (via exists_min_cut_partition). In any connected diameter-2 graph, every cut has at least δ(G) crossing edges (cross_cut_card_ge_minDegree_of_diam_two). Combining δ(G) ≤ |E(X, Xᶜ)| and |E(X, Xᶜ)| ≤ κ'(G) by transitivity of ≤ (le_trans) establishes δ(G) ≤ κ'(G).
uses
exists_min_cut_partition,cross_cut_card_ge_minDegree_of_diam_two,le_trans· obtain ⟨X, hX, hXc, hle⟩ := exists_min_cut_partition G hG have hge := cross_cut_card_ge_minDegree_of_diam_two G hG hd X hX hXc exact le_trans hge hle
SimpleGraph.nontrivial_of_diam_ne_zero- a graph with nonzero diameter has a nontrivial vertex type (at least two vertices)
le_antisymm- if a ≤ b and b ≤ a, then a = b
graph_edge_connectivity_le_minDegree- for any finite nontrivial graph G, its edge-connectivity is at most its minimum degree, κ'(G) ≤ δ(G)
exists_min_cut_partition- in a finite connected nontrivial graph, there exists a cut partition (X, Xᶜ) whose number of crossing edges is at most the edge-connectivity κ'(G)
cross_cut_card_ge_minDegree_of_diam_two- in a connected graph of diameter 2, any cut partition into two nonempty subsets has at least δ(G) crossing edges
le_trans- if a ≤ b and b ≤ c, then a ≤ c
- The proof begins by formally establishing the typeclass instance `Nontrivial V` from the diameter being 2 (and hence nonzero), a formal prerequisite required by downstream lemmas about cuts and minimum degree.
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.
/-- Plesník's theorem: a finite connected diameter-2 graph has κ'(G) = δ(G). -/theorem graph_edge_connectivity_eq_minDegree_of_diam_two {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : G.diam = 2) : graph_edge_connectivity G = G.minDegree := by have : Nontrivial V := SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd]; decide) apply le_antisymm · exact graph_edge_connectivity_le_minDegree G · obtain ⟨X, hX, hXc, hle⟩ := exists_min_cut_partition G hG have hge := cross_cut_card_ge_minDegree_of_diam_two G hG hd X hX hXc exact le_trans hge hle