AFTD Auto-Formalizing Theoretical Domains

exists_min_cut_partition

theoremverified

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
Used by 1

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).

  1. 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`.

    lines 7–17

    uses le_csSup

      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
  2. 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.

    lines 18–23

    uses SimpleGraph.IsEdgeConnected, SimpleGraph.IsEdgeReachable

      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
  3. 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.

    lines 24–34

    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, ?_⟩
  4. 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.

    lines 35–45

    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)
  5. 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.

    lines 46–54

    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 `ℕ`.

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

/-- 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
See it in the graphDiscuss this resultChallenge it