five_vertex_min_degree_two_ediam_le_two
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
- 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_positive_edge_connectivity_threshold_fivec(5) = 2: every connected graph on 5 vertices with edge-connectivity at least 2 has positive Lin–Lu–Yau curvature on every edge, while the…
- five_vertex_min_degree_two_wasserstein_lt_oneEvery connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.
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.
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$.
uses
ediam_le_two_of_card_sub_one_le_two_mul_minDegreeapply ediam_le_two_of_card_sub_one_le_two_mul_minDegreeThe 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δ`.
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.
- The diameter bound `ediam_le_two_of_card_sub_one_le_two_mul_minDegree` is formulated with quantities coerced to the real numbers, so `exact_mod_cast` handles the conversion between the integer/natural-number hypothesis and the real inequality.
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 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δ