AFTD Auto-Formalizing Theoretical Domains

ediam_le_two_of_minDegree_ge_two_thirds

theoremverified

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

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

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

    lines 7–8

    uses Fintype.one_lt_card, lt_or_ge

      have hn : 1 < Fintype.card V := Fintype.one_lt_card
      rcases lt_or_ge (Fintype.card V) 3 with hlt | hge
  2. 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.

    lines 9–11

    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)
  3. 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.

    lines 12–15

    uses ediam_le_two_of_card_sub_one_le_two_mul_minDegree

        apply ediam_le_two_of_card_sub_one_le_two_mul_minDegree
        rw [hcard]
        norm_num
        linarith
  4. 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.

    lines 16–18

    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.

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

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