five_vertex_t_star_connected_edge_connectivity
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
- five_vertex_t_starThe tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2: the path 3–0–1–2 with an extra leaf 4 attached at 0.
- five_vertex_t_star_adj_decidableAdjacency in the T-graph is decidable.
- 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…
- one_le_graph_edge_connectivity_of_connectedA connected graph on at least two vertices has edge-connectivity at least 1.
- graph_edge_connectivity_le_minDegreeEdge-connectivity is at most the minimum degree, κ'(G) ≤ δ(G) (for at least two vertices).
- Used by 1
- lly_positive_edge_connectivity_threshold_fivec(5) = 2: every connected graph on 5 vertices with edge-connectivity at least 2 has positive Lin–Lu–Yau curvature on every edge, while the…
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.
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.
have hconn : five_vertex_t_star.Connected := by decide refine ⟨hconn, ?_⟩
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.
uses
one_le_graph_edge_connectivity_of_connectedhave h1 : 1 ≤ graph_edge_connectivity five_vertex_t_star := one_le_graph_edge_connectivity_of_connected five_vertex_t_star hconngraph_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.
uses
graph_edge_connectivity_le_minDegreehave 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
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.
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.
- The graph's connectedness and its minimum degree are proved by computational reflection (`decide`), evaluating the decidable predicates directly over the finite 5-vertex graph.
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.
/-- 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