ediam_le_two_of_minDegree_ge_two_thirds
If a finite connected graph G on at least two vertices has minimum degree δ(G) ≥ 2n/3 − 1, then its diameter is at most 2.
Statement
theorem ediam_le_two_of_minDegree_ge_two_thirds {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ)) : G.ediam ≤ 2
- Source
- step towards lly_curvature_pos_of_edge_connectivity_ge
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- ediam_le_two_of_card_sub_one_le_two_mul_minDegreeA graph on n vertices with minimum degree δ(G) ≥ (n − 1)/2 has diameter at most 2 (in particular it is connected).
- Used by 2
- 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.
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
The proof, explained
The proof reduces the diameter bound to the general criterion that (|V| - 1)/2 ≤ δ(G) implies diam(G) ≤ 2, splitting into cases based on the vertex count |V|. When |V| ≥ 3, the minimum degree hypothesis δ(G) ≥ 2|V|/3 - 1 directly implies (|V| - 1)/2 ≤ δ(G) because 2|V|/3 - 1 ≥ (|V| - 1)/2 for all |V| ≥ 3. In the remaining case |V| < 3, nontriviality forces |V| = 2, and connectedness guarantees δ(G) ≥ 1, which also satisfies (|V| - 1)/2 = 1/2 ≤ δ(G).
The number of vertices |V| is strictly greater than 1, and either |V| < 3 or |V| ≥ 3.
Because the vertex type V is nontrivial, its cardinality is strictly greater than 1 by Fintype.one_lt_card. Using lt_or_ge, we split into two cases: |V| < 3 and |V| ≥ 3.
uses
Fintype.one_lt_card,lt_or_gehave hn : 1 < Fintype.card V := Fintype.one_lt_card rcases lt_or_ge (Fintype.card V) 3 with hlt | hge
In the case |V| < 3, the graph has exactly 2 vertices and minimum degree δ(G) ≥ 1.
Since 1 < |V| < 3 for natural numbers, integer arithmetic (omega) determines that |V| = 2. Furthermore, because G is connected and nontrivial, every vertex has degree at least 1, so the minimum degree δ(G) is strictly positive by minDegree_pos_of_nontrivial, which means δ(G) ≥ 1 when cast to the real numbers.
uses
minDegree_pos_of_nontrivial· have hcard : Fintype.card V = 2 := by omega have hmin : (1 : ℝ) ≤ (G.minDegree : ℝ) := by exact_mod_cast (hG.preconnected.minDegree_pos_of_nontrivial : 0 < G.minDegree)
In the case |V| < 3, the diameter of G is at most 2.
Applying ediam_le_two_of_card_sub_one_le_two_mul_minDegree, it suffices to show that (|V| - 1)/2 ≤ δ(G). Substituting |V| = 2 reduces this to 1/2 ≤ δ(G), which follows by linear arithmetic (linarith) from the fact that δ(G) ≥ 1.
uses
ediam_le_two_of_card_sub_one_le_two_mul_minDegreeapply ediam_le_two_of_card_sub_one_le_two_mul_minDegree rw [hcard] norm_num linarith
In the case |V| ≥ 3, the diameter of G is at most 2.
Applying ediam_le_two_of_card_sub_one_le_two_mul_minDegree again reduces the goal to proving (|V| - 1)/2 ≤ δ(G). Since |V| ≥ 3, the algebraic inequality (|V| - 1)/2 ≤ 2|V|/3 - 1 holds (as 3(|V| - 1) ≤ 4|V| - 6 is equivalent to 3 ≤ |V|). Combined with the hypothesis 2|V|/3 - 1 ≤ δ(G), this implies (|V| - 1)/2 ≤ δ(G), which nlinarith verifies.
uses
ediam_le_two_of_card_sub_one_le_two_mul_minDegree· apply ediam_le_two_of_card_sub_one_le_two_mul_minDegree have hnR : (3 : ℝ) ≤ (Fintype.card V : ℝ) := by exact_mod_cast hge nlinarith
Fintype.one_lt_card- A nontrivial finite type has cardinality strictly greater than 1.
lt_or_ge- In any linearly ordered type, any two elements satisfy a < b or b ≤ a.
minDegree_pos_of_nontrivial- In a connected (or preconnected) graph on a nontrivial vertex type, the minimum degree is strictly positive.
ediam_le_two_of_card_sub_one_le_two_mul_minDegree- If a finite graph satisfies (|V| - 1) / 2 ≤ δ(G), then its extended diameter is at most 2.
- The arithmetic inequalities (n - 1)/2 ≤ δ(G) are discharged automatically by the linear arithmetic tactics linarith and nlinarith.
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.
/-- A connected graph on at least two vertices with minimum degree δ(G) ≥ 2n/3 - 1 has diameter at most 2. -/theorem ediam_le_two_of_minDegree_ge_two_thirds {V : Type*} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ)) : G.ediam ≤ 2 := by have hn : 1 < Fintype.card V := Fintype.one_lt_card rcases lt_or_ge (Fintype.card V) 3 with hlt | hge · have hcard : Fintype.card V = 2 := by omega have hmin : (1 : ℝ) ≤ (G.minDegree : ℝ) := by exact_mod_cast (hG.preconnected.minDegree_pos_of_nontrivial : 0 < G.minDegree) apply ediam_le_two_of_card_sub_one_le_two_mul_minDegree rw [hcard] norm_num linarith · apply ediam_le_two_of_card_sub_one_le_two_mul_minDegree have hnR : (3 : ℝ) ≤ (Fintype.card V : ℝ) := by exact_mod_cast hge nlinarith