AFTD Auto-Formalizing Theoretical Domains

graph_edge_connectivity_le_minDegree

theoremverified

Edge-connectivity is at most the minimum degree, κ'(G) ≤ δ(G) (for at least two vertices).

Statement

theorem graph_edge_connectivity_le_minDegree {V : Type*} [Fintype V] [DecidableEq V]
    [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] :
    graph_edge_connectivity G ≤ G.minDegree
Source
Sanity check of the definitions of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 1 (the classical bound κ(G) ≤ κ'(G) ≤ δ(G) quoted there).
Verified
10 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_edge_connectivityThe edge-connectivity κ'(G): the largest k such that removing fewer than k edges never disconnects G (0 for a disconnected graph; 0 also…
Used by 4

The proof, explained

The edge-connectivity κ'(G) is defined as the supremum of all k ∈ ℕ such that G is k-edge-connected. To prove κ'(G) ≤ δ(G), the argument applies the upper-bound property of suprema, which reduces the claim to showing that 0 is in the set and that every such k satisfies k ≤ δ(G). The upper bound holds because G has a vertex v of degree δ(G), and k-edge-connectivity forces k to be bounded by the degree of every vertex.

  1. To show that the edge-connectivity of G is at most its minimum degree, it suffices to show that the set of connectivity values is nonempty and bounded above by the minimum degree.

    Unfolding the definition of edge-connectivity as the supremum of {k | G.IsEdgeConnected k}, applying csSup_le reduces the inequality sSup {k | G.IsEdgeConnected k} ≤ G.minDegree to two subgoals: verifying that the set is nonempty, and showing that every k in the set satisfies k ≤ G.minDegree.

    lines 4–5

    uses csSup_le

      dsimp [graph_edge_connectivity]
      apply csSup_le
  2. The set of integers k for which G is k-edge-connected is nonempty.

    The integer 0 is a witness: every graph is 0-edge-connected by SimpleGraph.IsEdgeConnected.zero.

    line 6

    uses SimpleGraph.IsEdgeConnected.zero

      · exact ⟨0, SimpleGraph.IsEdgeConnected.zero⟩
  3. Every integer k for which G is k-edge-connected is at most the minimum degree of G.

    Fix an arbitrary k such that G is k-edge-connected. Since G is finite and nontrivial, G.exists_minimal_degree_vertex provides a vertex v such that G.minDegree = G.degree v. Rewriting with this equality reduces the goal to k ≤ G.degree v, which follows immediately from hk.le_degree since G is k-edge-connected.

    lines 7–10

    uses G.exists_minimal_degree_vertex, hk.le_degree

      · intro k hk
        obtain ⟨v, hv⟩ := G.exists_minimal_degree_vertex
        rw [hv]
        exact hk.le_degree
csSup_le
In a conditionally complete lattice, the supremum of a set is at most an upper bound a whenever the set is nonempty and every element is at most a.
SimpleGraph.IsEdgeConnected.zero
Every simple graph is 0-edge-connected.
G.exists_minimal_degree_vertex
In any finite, nonempty simple graph, there exists a vertex whose degree equals the minimum degree of the graph.
hk.le_degree
If a nontrivial simple graph is k-edge-connected, then k is at most the degree of any vertex u.

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 graph_edge_connectivity_le_minDegree {V : Type*} [Fintype V] [DecidableEq V]    [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] :    graph_edge_connectivity G ≤ G.minDegree := by  dsimp [graph_edge_connectivity]  apply csSup_le  · exact ⟨0, SimpleGraph.IsEdgeConnected.zero⟩  · intro k hk    obtain ⟨v, hv⟩ := G.exists_minimal_degree_vertex    rw [hv]    exact hk.le_degree
See it in the graphDiscuss this resultChallenge it