AFTD Auto-Formalizing Theoretical Domains

five_vertex_t_star_connected_edge_connectivity

theoremverified

The T-graph (edges 0–1, 0–3, 0–4, 1–2) is connected and has edge-connectivity κ' = 1 (it is a tree).

Statement

theorem five_vertex_t_star_connected_edge_connectivity :
    five_vertex_t_star.Connected ∧ graph_edge_connectivity five_vertex_t_star = 1
Source
step towards lly_positive_edge_connectivity_threshold_five
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

The theorem proves that the five-vertex tree five_vertex_t_star is connected and has edge-connectivity equal to 1. Connectedness is verified by finite computation. The edge-connectivity is then pinched between 1 and 1: it is at least 1 because the graph is connected, and at most 1 because edge-connectivity cannot exceed the minimum degree, which is computed to be 1.

  1. The graph five_vertex_t_star is connected, leaving only the edge-connectivity to be established.

    Because the graph is finite and explicitly specified, its connectedness is verified by finite computation (`decide`). Providing this fact (`hconn`) discharges the first conjunct of the goal, leaving the equality graph_edge_connectivity five_vertex_t_star = 1.

    lines 4–5

      have hconn : five_vertex_t_star.Connected := by decide
      refine ⟨hconn, ?_⟩
  2. 1 ≤ graph_edge_connectivity five_vertex_t_star

    By one_le_graph_edge_connectivity_of_connected, any connected graph on a nontrivial finite vertex type has edge-connectivity at least 1. Applying this to the connectedness hypothesis hconn establishes the lower bound.

    lines 6–7

    uses one_le_graph_edge_connectivity_of_connected

      have h1 : 1 ≤ graph_edge_connectivity five_vertex_t_star :=
        one_le_graph_edge_connectivity_of_connected five_vertex_t_star hconn
  3. graph_edge_connectivity five_vertex_t_star ≤ 1

    The edge-connectivity of any graph is bounded above by its minimum vertex degree (graph_edge_connectivity_le_minDegree). Since the graph is finite and has leaves (such as vertex 2), its minimum degree is computed to be 1 by `decide`. Linear integer arithmetic (`omega`) combines these two inequalities to yield the upper bound.

    lines 8–11

    uses graph_edge_connectivity_le_minDegree

      have h2 : graph_edge_connectivity five_vertex_t_star ≤ 1 := by
        have hle := graph_edge_connectivity_le_minDegree five_vertex_t_star
        have hdeg : five_vertex_t_star.minDegree = 1 := by decide
        omega
  4. graph_edge_connectivity five_vertex_t_star = 1

    Linear integer arithmetic (`omega`) combines the lower bound 1 ≤ κ' and the upper bound κ' ≤ 1 to conclude that the edge-connectivity equals 1.

    line 12

      omega
one_le_graph_edge_connectivity_of_connected
A connected simple graph on a finite, nontrivial vertex set has edge-connectivity at least 1.
graph_edge_connectivity_le_minDegree
The edge-connectivity of a simple graph on a finite, nontrivial vertex set is at most its minimum vertex degree.

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

/-- The T-graph is connected and its edge-connectivity is 1, so it is a legitimate test graph for both the hypotheses `0 ≤ κ'` and `1 ≤ κ'`. -/theorem five_vertex_t_star_connected_edge_connectivity :    five_vertex_t_star.Connected ∧ graph_edge_connectivity five_vertex_t_star = 1 := by  have hconn : five_vertex_t_star.Connected := by decide  refine ⟨hconn, ?_⟩  have h1 : 1 ≤ graph_edge_connectivity five_vertex_t_star :=    one_le_graph_edge_connectivity_of_connected five_vertex_t_star hconn  have h2 : graph_edge_connectivity five_vertex_t_star ≤ 1 := by    have hle := graph_edge_connectivity_le_minDegree five_vertex_t_star    have hdeg : five_vertex_t_star.minDegree = 1 := by decide    omega  omega
See it in the graphDiscuss this resultChallenge it