AFTD Auto-Formalizing Theoretical Domains

one_le_graph_edge_connectivity_of_connected

theoremverified

A connected graph on at least two vertices has edge-connectivity at least 1.

Statement

theorem one_le_graph_edge_connectivity_of_connected {V : Type*} [Fintype V] [DecidableEq V]
    [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) :
    1 ≤ graph_edge_connectivity G
Source
Sanity check of the definitions of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 1.
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 2

The proof, explained

The edge-connectivity of G is defined as the supremum of all k such that G is k-edge-connected. The proof reduces the inequality 1 ≤ graph_edge_connectivity G to showing that the set of such k is bounded above and contains 1. An upper bound is given by the degree of any chosen vertex, and 1 belongs to the set because a connected graph is preconnected, which is equivalent to 1-edge-connectivity.

  1. To show 1 ≤ graph_edge_connectivity G, it suffices to show that the set of edge-connectivities {k | G.IsEdgeConnected k} is bounded above and contains 1.

    Unfolding graph_edge_connectivity expresses it as sSup {k | G.IsEdgeConnected k}. By le_csSup, an element a is at most sSup s whenever s is bounded above and a ∈ s. Applying this with a = 1 splits the goal into two subgoals: showing that the set of k for which G is k-edge-connected is bounded above, and showing that 1 belongs to this set.

    lines 4–5

    uses le_csSup

      dsimp [graph_edge_connectivity]
      apply le_csSup
  2. The set {k | G.IsEdgeConnected k} is bounded above by the degree of any vertex.

    Since the vertex set V is nontrivial, it is nonempty, so we can choose a vertex v ∈ V. For any k such that G is k-edge-connected, k is at most the degree of v (by le_degree). Therefore, the degree G.degree v provides an explicit upper bound for {k | G.IsEdgeConnected k}.

    lines 6–7

    uses le_degree

      · obtain ⟨v⟩ : Nonempty V := inferInstance
        exact ⟨G.degree v, fun k hk ↦ hk.le_degree⟩
  3. 1 ∈ {k | G.IsEdgeConnected k}, that is, G is 1-edge-connected.

    By isEdgeConnected_one, a graph is 1-edge-connected if and only if it is preconnected. Since G is assumed to be connected (hG), it is preconnected, which concludes the proof.

    line 8

    uses isEdgeConnected_one

      · exact G.isEdgeConnected_one.mpr hG.preconnected
le_csSup
In a conditionally complete lattice, an element a is at most the supremum of a set s if s is bounded above and a ∈ s.
le_degree
If a graph on a nontrivial vertex set is k-edge-connected, then k is bounded above by the degree of any vertex.
isEdgeConnected_one
A simple graph is 1-edge-connected if and only if it is preconnected.

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 one_le_graph_edge_connectivity_of_connected {V : Type*} [Fintype V] [DecidableEq V]    [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) :    1 ≤ graph_edge_connectivity G := by  dsimp [graph_edge_connectivity]  apply le_csSup  · obtain ⟨v⟩ : Nonempty V := inferInstance    exact ⟨G.degree v, fun k hk ↦ hk.le_degree⟩  · exact G.isEdgeConnected_one.mpr hG.preconnected
See it in the graphDiscuss this resultChallenge it