ediam_le_two_of_card_sub_one_le_two_mul_minDegree
A graph on n vertices with minimum degree δ(G) ≥ (n − 1)/2 has diameter at most 2 (in particular it is connected).
Statement
theorem ediam_le_two_of_card_sub_one_le_two_mul_minDegree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h : ((Fintype.card V : ℝ) - 1) / 2 ≤ (G.minDegree : ℝ)) : G.ediam ≤ 2
- Formalizes
- arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Lemma 4.1; diameter as Mathlib's extended diameter `ediam`, so the conclusion includes connectedness.
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- ediam_le_two_of_minDegree_ge_two_thirdsIf a finite connected graph G on at least two vertices has minimum degree δ(G) ≥ 2n/3 − 1, then its diameter is at most 2.
- five_vertex_min_degree_two_ediam_le_twoEvery graph on 5 vertices with minimum degree at least 2 has diameter at most 2, hence is connected.
The proof, explained
The theorem is proved by contradiction. If the diameter of G were strictly greater than 2, there would exist two vertices u and v at distance greater than 2, meaning they are non-adjacent and share no common neighbors. Consequently, the sets N(u), N(v), and {u, v} are mutually disjoint, so their union has size deg(u) + deg(v) + 2 ≤ |V|. Since each degree is at least the minimum degree δ(G), this implies 2δ(G) + 2 ≤ |V|, which contradicts the hypothesis δ(G) ≥ (|V| - 1)/2.
Assume for contradiction that the graph diameter is greater than 2, giving two vertices u and v that are distinct, non-adjacent, and have no common neighbors.
By definition, the diameter is at most 2 if and only if the distance between any two vertices is at most 2. Assuming for contradiction that this fails, we obtain two vertices u and v with distance strictly greater than 2. By the characterization of distance greater than 2 in a simple graph, u and v must be distinct, non-adjacent, and have an empty set of common neighbors.
uses
SimpleGraph.ediam_le_iff,not_le,SimpleGraph.two_lt_edist_iffrw [SimpleGraph.ediam_le_iff] intro u v by_contra hlt rw [not_le, SimpleGraph.two_lt_edist_iff] at hlt rcases hlt with ⟨huv, hnotadj, hcn⟩
The neighbor sets of u and v are disjoint.
If an element x were in both the neighbor set of u and the neighbor set of v, it would be adjacent to both u and v, making it a common neighbor of u and v. But u and v have no common neighbors, which is a contradiction.
uses
Finset.disjoint_iff_ne,SimpleGraph.mem_neighborFinset,SimpleGraph.mem_commonNeighborshave hd1 : Disjoint (G.neighborFinset u) (G.neighborFinset v) := by rw [Finset.disjoint_iff_ne] intro x hx y hy hxy subst hxy rw [SimpleGraph.mem_neighborFinset] at hx hy have : x ∈ G.commonNeighbors u v := by rw [SimpleGraph.mem_commonNeighbors] exact ⟨hx, hy⟩ rw [hcn] at this exact this
The neighbor set of u is disjoint from {u, v}.
The neighborhood of u is disjoint from {u, v} because u ∉ N(u) (simple graphs have no loops) and v ∉ N(u) (u and v are not adjacent).
uses
Finset.disjoint_insert_right,Finset.disjoint_singleton_right,SimpleGraph.mem_neighborFinset,G.irreflhave hd2 : Disjoint (G.neighborFinset u) ({u, v} : Finset V) := by rw [Finset.disjoint_insert_right, Finset.disjoint_singleton_right] refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset]; exact G.irrefl · rw [SimpleGraph.mem_neighborFinset]; exact hnotadj
The neighbor set of v is disjoint from {u, v}.
Similarly, the neighborhood of v is disjoint from {u, v} because u ∉ N(v) (by symmetry of non-adjacency between u and v) and v ∉ N(v) (irreflexivity).
uses
Finset.disjoint_insert_right,Finset.disjoint_singleton_right,SimpleGraph.mem_neighborFinset,G.irreflhave hd3 : Disjoint (G.neighborFinset v) ({u, v} : Finset V) := by rw [Finset.disjoint_insert_right, Finset.disjoint_singleton_right] refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset]; intro hadj; exact hnotadj hadj.symm · rw [SimpleGraph.mem_neighborFinset]; exact G.irrefl
The union of the neighbor sets N(u) ∪ N(v) is disjoint from {u, v}.
Since both N(u) and N(v) are disjoint from {u, v}, their union is also disjoint from {u, v}.
uses
Finset.disjoint_union_left.mprhave hd4 : Disjoint (G.neighborFinset u ∪ G.neighborFinset v) ({u, v} : Finset V) := Finset.disjoint_union_left.mpr ⟨hd2, hd3⟩deg(u) + deg(v) + 2 ≤ |V|.
The union (N(u) ∪ N(v)) ∪ {u, v} is a subset of the full vertex set V, so its cardinality is bounded by |V|. Because the subsets are mutually disjoint, the cardinality of this union equals |N(u)| + |N(v)| + |{u, v}|. Since u ≠ v, |{u, v}| = 2, and the size of each neighborhood is the vertex degree, yielding deg(u) + deg(v) + 2 ≤ |V|.
uses
Finset.card_le_univ,Finset.card_union_of_disjoint,Finset.card_pair,SimpleGraph.card_neighborFinset_eq_degreehave h_card := Finset.card_le_univ ((G.neighborFinset u ∪ G.neighborFinset v) ∪ {u, v}) rw [Finset.card_union_of_disjoint hd4, Finset.card_union_of_disjoint hd1] at h_card have h_uv : Finset.card ({u, v} : Finset V) = 2 := Finset.card_pair huv rw [SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.card_neighborFinset_eq_degree, h_uv] at h_card
Over the real numbers, deg(u) + deg(v) + 2 ≤ |V|, with δ(G) ≤ deg(u) and δ(G) ≤ deg(v).
The minimum degree δ(G) is at most the degree of any vertex, so δ(G) ≤ deg(u) and δ(G) ≤ deg(v). These inequalities and the cardinality bound are cast from ℕ to ℝ so that they can be combined with the real hypothesis.
uses
G.minDegree_le_degreehave hu : G.minDegree ≤ G.degree u := G.minDegree_le_degree u have hv : G.minDegree ≤ G.degree v := G.minDegree_le_degree v have h_card_real : (G.degree u : ℝ) + (G.degree v : ℝ) + 2 ≤ (Fintype.card V : ℝ) := by exact_mod_cast h_card have hu_real : (G.minDegree : ℝ) ≤ (G.degree u : ℝ) := by exact_mod_cast hu have hv_real : (G.minDegree : ℝ) ≤ (G.degree v : ℝ) := by exact_mod_cast hv
A contradiction is reached: False. automation
From δ(G) ≤ deg(u), δ(G) ≤ deg(v), and deg(u) + deg(v) + 2 ≤ |V|, linear arithmetic over ℝ gives 2δ(G) + 2 ≤ |V|, or δ(G) ≤ (|V| - 2) / 2. This directly contradicts the hypothesis δ(G) ≥ (|V| - 1) / 2.
linarith
SimpleGraph.ediam_le_iff- The diameter of a graph is at most k if and only if every pair of vertices has distance at most k.
not_le- For linearly ordered types, ¬(a ≤ b) is equivalent to b < a.
SimpleGraph.two_lt_edist_iff- The extended distance between two vertices u and v is strictly greater than 2 if and only if u ≠ v, u and v are not adjacent, and they have no common neighbors.
Finset.disjoint_iff_ne- Two finite sets are disjoint if and only if no element of the first equals an element of the second.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent in G.
SimpleGraph.mem_commonNeighbors- A vertex belongs to the set of common neighbors of u and v if and only if it is adjacent to both u and v.
Finset.disjoint_insert_right- A set s is disjoint from {a} ∪ t if and only if a ∉ s and s is disjoint from t.
Finset.disjoint_singleton_right- A set s is disjoint from the singleton {a} if and only if a ∉ s.
G.irrefl- A simple graph has no self-loops: no vertex is adjacent to itself.
Finset.disjoint_union_left.mpr- If s is disjoint from u and t is disjoint from u, then s ∪ t is disjoint from u.
Finset.card_le_univ- The cardinality of any finite subset of a type is at most the total number of elements in the type.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_pair- A set of two distinct elements {a, b} has cardinality 2.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex equals its degree in the graph.
G.minDegree_le_degree- The minimum degree of a graph is less than or equal to the degree of any of its vertices.
- Casting the inequalities between natural numbers to the real numbers (lines 37–40) is a formal detail needed to apply real linear arithmetic (linarith) alongside the hypothesis ((|V| - 1) / 2 ≤ δ(G)).
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.
theorem ediam_le_two_of_card_sub_one_le_two_mul_minDegree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h : ((Fintype.card V : ℝ) - 1) / 2 ≤ (G.minDegree : ℝ)) : G.ediam ≤ 2 := by rw [SimpleGraph.ediam_le_iff] intro u v by_contra hlt rw [not_le, SimpleGraph.two_lt_edist_iff] at hlt rcases hlt with ⟨huv, hnotadj, hcn⟩ have hd1 : Disjoint (G.neighborFinset u) (G.neighborFinset v) := by rw [Finset.disjoint_iff_ne] intro x hx y hy hxy subst hxy rw [SimpleGraph.mem_neighborFinset] at hx hy have : x ∈ G.commonNeighbors u v := by rw [SimpleGraph.mem_commonNeighbors] exact ⟨hx, hy⟩ rw [hcn] at this exact this have hd2 : Disjoint (G.neighborFinset u) ({u, v} : Finset V) := by rw [Finset.disjoint_insert_right, Finset.disjoint_singleton_right] refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset]; exact G.irrefl · rw [SimpleGraph.mem_neighborFinset]; exact hnotadj have hd3 : Disjoint (G.neighborFinset v) ({u, v} : Finset V) := by rw [Finset.disjoint_insert_right, Finset.disjoint_singleton_right] refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset]; intro hadj; exact hnotadj hadj.symm · rw [SimpleGraph.mem_neighborFinset]; exact G.irrefl have hd4 : Disjoint (G.neighborFinset u ∪ G.neighborFinset v) ({u, v} : Finset V) := Finset.disjoint_union_left.mpr ⟨hd2, hd3⟩ have h_card := Finset.card_le_univ ((G.neighborFinset u ∪ G.neighborFinset v) ∪ {u, v}) rw [Finset.card_union_of_disjoint hd4, Finset.card_union_of_disjoint hd1] at h_card have h_uv : Finset.card ({u, v} : Finset V) = 2 := Finset.card_pair huv rw [SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.card_neighborFinset_eq_degree, h_uv] at h_card have hu : G.minDegree ≤ G.degree u := G.minDegree_le_degree u have hv : G.minDegree ≤ G.degree v := G.minDegree_le_degree v have h_card_real : (G.degree u : ℝ) + (G.degree v : ℝ) + 2 ≤ (Fintype.card V : ℝ) := by exact_mod_cast h_card have hu_real : (G.minDegree : ℝ) ≤ (G.degree u : ℝ) := by exact_mod_cast hu have hv_real : (G.minDegree : ℝ) ≤ (G.degree v : ℝ) := by exact_mod_cast hv linarith