AFTD Auto-Formalizing Theoretical Domains

five_vertex_min_degree_two_ediam_le_two

theoremverified

Every graph on 5 vertices with minimum degree at least 2 has diameter at most 2, hence is connected.

Statement

theorem five_vertex_min_degree_two_ediam_le_two {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5)
    (hδ : 2 ≤ G.minDegree) : G.ediam ≤ 2
Source
step towards lly_positive_edge_connectivity_threshold_five
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The proof applies a general theorem stating that any finite graph with minimum degree $δ(G) ≥ (|V| - 1)/2$ has diameter at most 2. For a 5-vertex graph, this threshold simplifies via arithmetic to $(5 - 1)/2 = 2$. Since the graph is assumed to have minimum degree at least 2, the bound holds immediately.

  1. It suffices to show that $(|V| - 1) / 2 ≤ δ(G)$.

    We apply `ediam_le_two_of_card_sub_one_le_two_mul_minDegree`, which reduces proving that the diameter is at most 2 to checking that the minimum degree $δ(G)$ is at least $(|V| - 1) / 2$.

    line 5

    uses ediam_le_two_of_card_sub_one_le_two_mul_minDegree

      apply ediam_le_two_of_card_sub_one_le_two_mul_minDegree
  2. The inequality $(|V| - 1) / 2 ≤ δ(G)$ holds for $G$.

    We substitute $|V| = 5$ from the vertex-count assumption `hcard`. Numerical evaluation (`norm_num`) simplifies $(5 - 1) / 2$ to 2, reducing the goal to $2 ≤ δ(G)$, which is precisely the given minimum-degree assumption `hδ`.

    lines 6–8

      rw [hcard]
      norm_num
      exact_mod_cast hδ
ediam_le_two_of_card_sub_one_le_two_mul_minDegree
A finite graph has eccentricity-diameter at most 2 if its minimum degree satisfies $(|V| - 1)/2 ≤ δ(G)$ as real numbers.

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 5-vertex graph of minimum degree 2 has ((card V) − 1)/2 = 2 ≤ δ(G), hence eccentricity-diameter at most 2 (and in particular is connected). -/theorem five_vertex_min_degree_two_ediam_le_two {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5)    (hδ : 2 ≤ G.minDegree) : G.ediam ≤ 2 := by  apply ediam_le_two_of_card_sub_one_le_two_mul_minDegree  rw [hcard]  norm_num  exact_mod_cast hδ
See it in the graphDiscuss this resultChallenge it