AFTD Auto-Formalizing Theoretical Domains

ediam_le_two_of_card_sub_one_le_two_mul_minDegree

theoremverifiedformalization

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

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.

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

    lines 4–8

    uses SimpleGraph.ediam_le_iff, not_le, SimpleGraph.two_lt_edist_iff

      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⟩
  2. 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.

    lines 9–18

    uses Finset.disjoint_iff_ne, SimpleGraph.mem_neighborFinset, SimpleGraph.mem_commonNeighbors

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

    lines 19–23

    uses Finset.disjoint_insert_right, Finset.disjoint_singleton_right, SimpleGraph.mem_neighborFinset, G.irrefl

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

    lines 24–28

    uses Finset.disjoint_insert_right, Finset.disjoint_singleton_right, SimpleGraph.mem_neighborFinset, G.irrefl

      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
  5. 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}.

    lines 29–30

    uses Finset.disjoint_union_left.mpr

      have hd4 : Disjoint (G.neighborFinset u ∪ G.neighborFinset v) ({u, v} : Finset V) :=
        Finset.disjoint_union_left.mpr ⟨hd2, hd3⟩
  6. 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|.

    lines 31–34

    uses Finset.card_le_univ, Finset.card_union_of_disjoint, Finset.card_pair, SimpleGraph.card_neighborFinset_eq_degree

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

    lines 35–40

    uses G.minDegree_le_degree

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

    line 41

      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.

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

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