exists_min_cut_partition
For every finite connected graph G on at least two vertices, there exists a non-trivial cut partition (X, X^c) with crossing edges at most the edge-connectivity κ'(G).
Statement
theorem exists_min_cut_partition {V : Type} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) : ∃ (X : Finset V), X.Nonempty ∧ (Xᶜ : Finset V).Nonempty ∧ (G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card ≤ graph_edge_connectivity G
- Source
- step towards edge_connectivity_ge_three_halves_min_degree_mul_lly_lower_bound_three
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- Arena.Reachable.transReachability is transitive.
- Used by 1
- graph_edge_connectivity_eq_minDegree_of_diam_twoPlesník's theorem: every finite connected graph of diameter 2 has edge-connectivity equal to its minimum degree, κ'(G) = δ(G).
The proof, explained
By definition of edge-connectivity κ'(G) as a supremum, the graph G is not (κ'(G) + 1)-edge-connected. Therefore, there exist vertices u and v and an edge set s with |s| ≤ κ'(G) whose deletion disconnects u from v. Taking X to be the connected component of u in G \ s yields a non-trivial cut partition (X, Xᶜ) containing u and v in opposite sides. Any edge of G crossing between X and Xᶜ must belong to s, bounding the number of crossing edges by |s| ≤ κ'(G).
The graph G is not (κ'(G) + 1)-edge-connected.
The edge-connectivity κ'(G) is defined as the supremum of the integers k for which G is k-edge-connected. Assuming for contradiction that G is (κ'(G) + 1)-edge-connected, κ'(G) + 1 belongs to this set. Since G has at least two vertices, choosing any vertex v gives an upper bound on k by the degree of v, so by `le_csSup` we obtain κ'(G) + 1 ≤ κ'(G), an arithmetic contradiction closed by `omega`.
uses
le_csSupclassical -- `κ'(G)+1` exceeds the sSup, so `G` is not `(κ'(G)+1)`-edge-connected. have hnot : ¬ G.IsEdgeConnected (graph_edge_connectivity G + 1) := by intro h have hbound : graph_edge_connectivity G + 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 h omega
There exist two vertices u, v and an edge set s with |s| < κ'(G) + 1 such that u cannot reach v in G \ s.
Unfolding the definition of edge-connectivity (`SimpleGraph.IsEdgeConnected`) and negating reveals a pair of vertices u and v that are not (κ'(G) + 1)-edge-reachable. In turn, unfolding `SimpleGraph.IsEdgeReachable` and negating yields an edge set s with cardinality strictly less than κ'(G) + 1 (as an extended natural) whose removal from G leaves u unable to reach v.
uses
SimpleGraph.IsEdgeConnected,SimpleGraph.IsEdgeReachablerw [SimpleGraph.IsEdgeConnected] at hnot push_neg at hnot obtain ⟨u, v, huv⟩ := hnot rw [SimpleGraph.IsEdgeReachable] at huv push_neg at huv obtain ⟨s, hs, hreach⟩ := huv
The connected component X of u in G \ s defines a non-trivial cut partition (X, Xᶜ).
Let H = G \ s, and define X to be the set of vertices reachable from u in H. Since reachability is reflexive (`SimpleGraph.Reachable.rfl`), u ∈ X, so X is non-empty. On the other hand, u cannot reach v in H by construction of s, so v ∉ X (`Finset.mem_filter`, `Finset.mem_univ`, `true_and`), meaning v ∈ Xᶜ and Xᶜ is also non-empty. This supplies the witness X and its non-emptiness conditions for the existential goal.
uses
SimpleGraph.Reachable.rfl,Finset.mem_filter,Finset.mem_univ,true_and-- Work in `H = G` with the edge set `s` deleted, and take the component of `u`. let H := G.deleteEdges s let X : Finset V := Finset.univ.filter (fun x => H.Reachable u x) have huX : u ∈ X := by simp [X, SimpleGraph.Reachable.rfl] have hvX : v ∉ X := by simp only [X, Finset.mem_filter, Finset.mem_univ, true_and] exact hreach have hXne : X.Nonempty := ⟨u, huX⟩ have hXcne : (Xᶜ : Finset V).Nonempty := ⟨v, by simp [hvX]⟩ refine ⟨X, hXne, hXcne, ?_⟩
Every edge of G crossing between X and Xᶜ must belong to the deleted set s.
Consider any edge e = s(a, b) of G with a ∈ X and b ∈ Xᶜ (`Finset.coe_filter`, `Set.mem_setOf_eq`). By definition of X, u can reach a in H, while u cannot reach b (`Finset.mem_filter`, `Finset.mem_univ`, `Finset.mem_compl`, `true_and`). If e were not in s, then e would still be present in H (`SimpleGraph.mem_edgeFinset`, `SimpleGraph.mem_edgeSet`), making a and b adjacent in H (`SimpleGraph.deleteEdges_adj.mpr`). Then u would reach b by following the path to a and traversing e, contradicting b ∈ Xᶜ. Hence e ∈ s.
uses
Finset.coe_filter,Set.mem_setOf_eq,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_compl,SimpleGraph.mem_edgeSet,SimpleGraph.mem_edgeFinset,SimpleGraph.deleteEdges_adj.mpr-- Every edge crossing the cut `(X, Xᶜ)` must belong to `s`. have hsub : ((G.edgeFinset.filter (fun e => ∃ a ∈ X, ∃ b ∈ (Xᶜ : Finset V), e = s(a, b))) : Set (Sym2 V)) ⊆ s := by intro e he simp only [Finset.coe_filter, Set.mem_setOf_eq] at he obtain ⟨heedge, a, haX, b, hbXc, rfl⟩ := he simp only [X, Finset.mem_filter, Finset.mem_univ, true_and] at haX simp only [Finset.mem_compl, X, Finset.mem_filter, Finset.mem_univ, true_and] at hbXc by_contra hmem have hadj : G.Adj a b := (SimpleGraph.mem_edgeSet G).mp ((SimpleGraph.mem_edgeFinset).mp heedge) have hHadj : H.Adj a b := SimpleGraph.deleteEdges_adj.mpr ⟨hadj, hmem⟩ exact hbXc (haX.trans hHadj.reachable)
The number of edges crossing the cut (X, Xᶜ) is at most κ'(G).
Because |s| < κ'(G) + 1 and κ'(G) is finite, we have |s| ≤ κ'(G) in `ℕ∞` (`ENat.lt_add_one_iff`). Since the set of crossing edges is a subset of s, its extended cardinality is at most |s| by monotonicity (`Set.encard_le_encard`), and hence at most κ'(G) by transitivity (`le_trans`). Rewriting the extended cardinality of the crossing edges as the coerced finset cardinality (`Set.encard_coe_eq_coe_finsetCard`) and transferring the inequality back to `ℕ` (`ENat.natCast_le_natCast.mp`) finishes the proof.
uses
ENat.lt_add_one_iff,le_trans,Set.encard_le_encard,Set.encard_coe_eq_coe_finsetCard,ENat.natCast_le_natCast.mp-- Since `s.encard < κ'(G)+1`, we have `s.encard ≤ κ'(G)`, bounding the cut size. have hleκ : s.encard ≤ (graph_edge_connectivity G : ℕ∞) := by have hs' : s.encard < (graph_edge_connectivity G : ℕ∞) + 1 := by simpa using hs exact (ENat.lt_add_one_iff (by simp)).mp hs' have hcardle : ((G.edgeFinset.filter (fun e => ∃ a ∈ X, ∃ b ∈ (Xᶜ : Finset V), e = s(a, b))) : Set (Sym2 V)).encard ≤ (graph_edge_connectivity G : ℕ∞) := le_trans (Set.encard_le_encard hsub) hleκ rw [Set.encard_coe_eq_coe_finsetCard] at hcardle exact ENat.natCast_le_natCast.mp hcardle
le_csSup- In a conditionally complete lattice, an element of a bounded-above set is less than or equal to the supremum of the set.
SimpleGraph.IsEdgeConnected- A graph is k-edge-connected if every pair of vertices is k-edge-reachable.
SimpleGraph.IsEdgeReachable- Two vertices u and v are k-edge-reachable if u can reach v after deleting any set of edges with cardinality strictly less than k.
SimpleGraph.Reachable.rfl- Reachability in a graph is reflexive: every vertex can reach itself.
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to s and satisfies the predicate p.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The conjunction `True ∧ p` is logically equivalent to `p`.
Finset.coe_filter- The set coercion of `Finset.filter p s` consists of all elements in s satisfying p.
Set.mem_setOf_eq- An element belongs to the set comprehension `{y | p y}` if and only if it satisfies p.
Finset.mem_compl- An element belongs to the complement of a finset if and only if it does not belong to the finset.
SimpleGraph.mem_edgeSet- An unordered pair of vertices forms an edge in `G.edgeSet` if and only if the vertices are adjacent in G.
SimpleGraph.mem_edgeFinset- An edge belongs to the finite edge set `G.edgeFinset` if and only if it belongs to `G.edgeSet`.
SimpleGraph.deleteEdges_adj.mpr- Two vertices are adjacent in `G.deleteEdges s` if they are adjacent in G and the edge between them does not belong to s.
ENat.lt_add_one_iff- For extended natural numbers m and n with n finite, m < n + 1 is equivalent to m ≤ n.
le_trans- The order relation is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Set.encard_le_encard- If s ⊆ t, then the extended cardinality of s is at most the extended cardinality of t.
Set.encard_coe_eq_coe_finsetCard- The extended cardinality of a coerced finset equals its finset cardinality coerced to `ℕ∞`.
ENat.natCast_le_natCast.mp- If the coercions of natural numbers m and n to `ℕ∞` satisfy ↑m ≤ ↑n, then m ≤ n in `ℕ`.
- The proof performs intermediate cardinality bounds in the type of extended natural numbers `ℕ∞` (`ENat`), which Mathlib uses for edge-connectivity and `Set.encard`, before casting the final inequality back to `ℕ`.
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.
/-- For every finite connected graph G on at least two vertices, there exists a partition of the vertices into two non-empty sets X and X^c such that the number of crossing edges is at most the edge-connectivity κ'(G). -/theorem exists_min_cut_partition {V : Type} [Fintype V] [DecidableEq V] [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) : ∃ (X : Finset V), X.Nonempty ∧ (Xᶜ : Finset V).Nonempty ∧ (G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card ≤ graph_edge_connectivity G := by classical -- `κ'(G)+1` exceeds the sSup, so `G` is not `(κ'(G)+1)`-edge-connected. have hnot : ¬ G.IsEdgeConnected (graph_edge_connectivity G + 1) := by intro h have hbound : graph_edge_connectivity G + 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 h omega rw [SimpleGraph.IsEdgeConnected] at hnot push_neg at hnot obtain ⟨u, v, huv⟩ := hnot rw [SimpleGraph.IsEdgeReachable] at huv push_neg at huv obtain ⟨s, hs, hreach⟩ := huv -- Work in `H = G` with the edge set `s` deleted, and take the component of `u`. let H := G.deleteEdges s let X : Finset V := Finset.univ.filter (fun x => H.Reachable u x) have huX : u ∈ X := by simp [X, SimpleGraph.Reachable.rfl] have hvX : v ∉ X := by simp only [X, Finset.mem_filter, Finset.mem_univ, true_and] exact hreach have hXne : X.Nonempty := ⟨u, huX⟩ have hXcne : (Xᶜ : Finset V).Nonempty := ⟨v, by simp [hvX]⟩ refine ⟨X, hXne, hXcne, ?_⟩ -- Every edge crossing the cut `(X, Xᶜ)` must belong to `s`. have hsub : ((G.edgeFinset.filter (fun e => ∃ a ∈ X, ∃ b ∈ (Xᶜ : Finset V), e = s(a, b))) : Set (Sym2 V)) ⊆ s := by intro e he simp only [Finset.coe_filter, Set.mem_setOf_eq] at he obtain ⟨heedge, a, haX, b, hbXc, rfl⟩ := he simp only [X, Finset.mem_filter, Finset.mem_univ, true_and] at haX simp only [Finset.mem_compl, X, Finset.mem_filter, Finset.mem_univ, true_and] at hbXc by_contra hmem have hadj : G.Adj a b := (SimpleGraph.mem_edgeSet G).mp ((SimpleGraph.mem_edgeFinset).mp heedge) have hHadj : H.Adj a b := SimpleGraph.deleteEdges_adj.mpr ⟨hadj, hmem⟩ exact hbXc (haX.trans hHadj.reachable) -- Since `s.encard < κ'(G)+1`, we have `s.encard ≤ κ'(G)`, bounding the cut size. have hleκ : s.encard ≤ (graph_edge_connectivity G : ℕ∞) := by have hs' : s.encard < (graph_edge_connectivity G : ℕ∞) + 1 := by simpa using hs exact (ENat.lt_add_one_iff (by simp)).mp hs' have hcardle : ((G.edgeFinset.filter (fun e => ∃ a ∈ X, ∃ b ∈ (Xᶜ : Finset V), e = s(a, b))) : Set (Sym2 V)).encard ≤ (graph_edge_connectivity G : ℕ∞) := le_trans (Set.encard_le_encard hsub) hleκ rw [Set.encard_coe_eq_coe_finsetCard] at hcardle exact ENat.natCast_le_natCast.mp hcardle