AFTD Auto-Formalizing Theoretical Domains

graph_edge_connectivity_eq_minDegree_of_diam_two

theoremverified

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
Used by 1

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.

  1. 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.

    line 5

    uses SimpleGraph.nontrivial_of_diam_ne_zero

      have : Nontrivial V := SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd]; decide)
  2. 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.

    line 6

    uses le_antisymm

      apply le_antisymm
  3. κ'(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.

    line 7

    uses graph_edge_connectivity_le_minDegree

      · exact graph_edge_connectivity_le_minDegree G
  4. δ(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).

    lines 8–10

    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

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

/-- 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
See it in the graphDiscuss this resultChallenge it