AFTD Auto-Formalizing Theoretical Domains

cross_cut_card_ge_minDegree_of_diam_two

theoremverified

Plesník's cut lemma: in a finite connected graph G with diam(G) = 2, every nontrivial vertex cut (A, Aᶜ) has at least δ(G) crossing edges.

Statement

theorem cross_cut_card_ge_minDegree_of_diam_two {V : Type} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : G.diam = 2)
    (A : Finset V) (hA : A.Nonempty) (hAc : (Aᶜ : Finset V).Nonempty) :
    G.minDegree ≤ (G.edgeFinset.filter (fun e => ∃ u ∈ A, ∃ v ∈ (Aᶜ : Finset V), e = s(u, v))).card
Source
step towards edge_connectivity_ge_min_degree_mul_lly_lower_bound_two
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

The proof, explained

Plesník's cut lemma states that in any finite connected graph with diameter 2, every nontrivial cut (A, Aᶜ) contains at least δ(G) crossing edges. The proof splits on whether every vertex in Aᶜ has at least one neighbor in A. When it does, the cut size is expressed as the sum of neighbors in A, which is bounded below by δ(G) through a degree decomposition and a quadratic inequality. When some vertex in Aᶜ has no neighbors in A, the diameter-2 condition forces every vertex in A to have a neighbor in Aᶜ, which reduces to the first case by cut symmetry.

  1. The number of crossing edges between Aᶜ and (Aᶜ)ᶜ is equal to the number of crossing edges between A and Aᶜ.

    Since the double complement (Aᶜ)ᶜ is A by compl_compl and undirected edges satisfy s(u, v) = s(v, u) by Sym2.eq_swap, the two filtered finsets of crossing edges are identical elementwise.

    lines 5–13

    uses compl_compl, Finset.mem_filter, Sym2.eq_swap

      congr 1
      simp only [compl_compl]
      ext e
      simp only [Finset.mem_filter]
      constructor
      · rintro ⟨he, u, hu, v, hv, rfl⟩
        exact ⟨he, v, hv, u, hu, Sym2.eq_swap⟩
      · rintro ⟨he, u, hu, v, hv, rfl⟩
        exact ⟨he, v, hv, u, hu, Sym2.eq_swap⟩
  2. The number of directed crossing pairs in A × Aᶜ that are edges equals the sum over b ∈ Aᶜ of the number of neighbors of b in A.

    Expressing the cardinality of the filtered Cartesian product as a sum of indicator 1s, swapping the order of summation so the outer sum runs over b ∈ Aᶜ, and identifying the inner sum as the cardinality of the neighbors of b in A.

    lines 19–22

    uses Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_product_right

      rw [Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_product_right]
      congr 1
      ext b
      rw [Finset.card_eq_sum_ones, Finset.sum_filter]
  3. For every vertex b, its degree deg(b) is the sum of its neighbors in Aᶜ and its neighbors in A.

    Partitioning the neighbor set of b into vertices in Aᶜ and vertices not in Aᶜ (which are precisely vertices in A, using symmetry of adjacency), and applying Finset.card_filter_add_card_filter_not.

    lines 28–35

    uses Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_compl, Finset.card_filter_add_card_filter_not

      have h : (G.neighborFinset b).filter (fun a => ¬ a ∈ (Aᶜ : Finset V)) = A.filter (fun a => G.Adj a b) := by
        ext a
        simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_compl]
        rw [G.adj_comm]
        tauto
      show (G.neighborFinset b).card = _
      rw [← h]
      exact (Finset.card_filter_add_card_filter_not (fun a => a ∈ (Aᶜ : Finset V))).symm
  4. For any vertex b ∈ Aᶜ, the number of its neighbors in Aᶜ is at most |Aᶜ| - 1.

    Because simple graphs have no self-loops, the neighbors of b in Aᶜ cannot include b itself, meaning they form a subset of Aᶜ \ {b}. The bound follows by monotonicity of cardinality and the fact that removing b decreases the cardinality by 1.

    lines 40–47

    uses Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_erase, Finset.card_le_card, Finset.card_erase_of_mem

      have h_sub : (G.neighborFinset b).filter (fun a => a ∈ (Aᶜ : Finset V)) ⊆ (Aᶜ : Finset V).erase b := by
        intro a ha
        rw [Finset.mem_filter, SimpleGraph.mem_neighborFinset] at ha
        rw [Finset.mem_erase]
        exact ⟨fun h => G.irrefl (h ▸ ha.1), ha.2⟩
      have h_card := Finset.card_le_card h_sub
      rw [Finset.card_erase_of_mem hb] at h_card
      exact h_card
  5. If every b ∈ Aᶜ has at least one neighbor in A, and |Aᶜ| ≥ δ(G), then the cut contains at least δ(G) edges. automation

    The number of crossing edges equals the sum of crossing degrees over b ∈ Aᶜ. When |Aᶜ| ≥ δ(G), summing the hypothesis that each b has at least 1 neighbor in A gives a sum of at least |Aᶜ| ≥ δ(G), which linear arithmetic closes.

    lines 53–59

    uses crossing_pairs_card_eq_crossing_edges_card, cross_cut_card_ge_minDegree_of_diam_two_sum, Finset.sum_le_sum

      rw [← crossing_pairs_card_eq_crossing_edges_card, cross_cut_card_ge_minDegree_of_diam_two_sum]
      by_cases h_card : G.minDegree ≤ (Aᶜ : Finset V).card
      · have h_sum : (Aᶜ : Finset V).card ≤ ∑ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card := by
          have : ∑ b ∈ (Aᶜ : Finset V), 1 ≤ ∑ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card :=
            Finset.sum_le_sum (fun b hb => h_ge1 b hb)
          simpa using this
        omega
  6. If every b ∈ Aᶜ has at least one neighbor in A, and |Aᶜ| < δ(G), then the cut also contains at least δ(G) edges. automation

    For each b ∈ Aᶜ, the degree formula and the bound on internal neighbors show that b has at least δ(G) + 1 - |Aᶜ| neighbors in A. Summing this over all b ∈ Aᶜ yields at least |Aᶜ|(δ(G) + 1 - |Aᶜ|). Since 1 ≤ |Aᶜ| ≤ δ(G), the quadratic inequality (|Aᶜ| - 1)(δ(G) - |Aᶜ|) ≥ 0 expands to show this lower bound is at least δ(G).

    lines 60–79

    uses cross_cut_card_ge_minDegree_of_diam_two_deg, cross_cut_card_ge_minDegree_of_diam_two_sub, Finset.sum_le_sum, Finset.sum_const_nat, mul_nonneg

      · have h_le : (Aᶜ : Finset V).card ≤ G.minDegree := by omega
        have h_pos : 1 ≤ (Aᶜ : Finset V).card := hAc.card_pos
        have h_each : ∀ b ∈ (Aᶜ : Finset V), G.minDegree + 1 - (Aᶜ : Finset V).card ≤ (A.filter (fun v => G.Adj v b)).card := by
          intro b hb
          have h1 := G.minDegree_le_degree b
          rw [cross_cut_card_ge_minDegree_of_diam_two_deg G A b] at h1
          have h2 := cross_cut_card_ge_minDegree_of_diam_two_sub G A b hb
          omega
        have h_sum : ∑ b ∈ (Aᶜ : Finset V), (G.minDegree + 1 - (Aᶜ : Finset V).card) ≤ ∑ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card :=
          Finset.sum_le_sum (fun b hb => h_each b hb)
        rw [Finset.sum_const_nat (fun _ _ => rfl)] at h_sum
        have h_ineq : G.minDegree ≤ (Aᶜ : Finset V).card * (G.minDegree + 1 - (Aᶜ : Finset V).card) := by
          have h_rew : G.minDegree + 1 - (Aᶜ : Finset V).card = G.minDegree - (Aᶜ : Finset V).card + 1 := by omega
          rw [h_rew]
          zify [h_le]
          have h1 : 0 ≤ ((Aᶜ : Finset V).card : ℤ) - 1 := by omega
          have h2 : 0 ≤ (G.minDegree : ℤ) - (Aᶜ : Finset V).card := by omega
          have h3 : 0 ≤ (((Aᶜ : Finset V).card : ℤ) - 1) * ((G.minDegree : ℤ) - (Aᶜ : Finset V).card) := mul_nonneg h1 h2
          nlinarith
        omega
  7. For any a ∈ A and b ∈ Aᶜ, if a and b are adjacent, then |N(a) ∩ Aᶜ| + |N(b) ∩ A| ≥ 1. automation

    First rule out infinite extended diameter using diam(G) = 2. When a and b are adjacent, b is a neighbor of a in Aᶜ, so |N(a) ∩ Aᶜ| ≥ 1, making the sum at least 1.

    lines 85–94

    uses SimpleGraph.diam_eq_zero_of_ediam_eq_top, Finset.mem_filter, Finset.card_pos.mpr

      have hediam : G.ediam ≠ ⊤ := by
        intro h
        have : G.diam = 0 := SimpleGraph.diam_eq_zero_of_ediam_eq_top h
        omega
      by_cases hab : G.Adj a b
      · have h1 : b ∈ Aᶜ.filter (G.Adj a ·) := by
          rw [Finset.mem_filter]
          exact ⟨hb, hab⟩
        have : 1 ≤ (Aᶜ.filter (G.Adj a ·)).card := Finset.card_pos.mpr ⟨b, h1⟩
        omega
  8. For any a ∈ A and b ∈ Aᶜ that are not adjacent, their distance is 2, so there exists a common neighbor c.

    Since a ∈ A and b ∈ Aᶜ, a ≠ b, so dist(a, b) > 0. Because a and b are not adjacent, dist(a, b) ≠ 1. Since diam(G) = 2, dist(a, b) ≤ 2, forcing dist(a, b) = 2. A walk of length 2 between a and b then provides a common neighbor c with a ~ c and c ~ b.

    lines 95–121

    uses SimpleGraph.dist_le_diam, SimpleGraph.dist_eq_one_iff_adj.mp, SimpleGraph.Walk.length_nil, SimpleGraph.Walk.length_cons

      · have hne : a ≠ b := by
          rintro rfl
          have : a ∈ A ∧ a ∈ Aᶜ := ⟨ha, hb⟩
          simp at this
        have hle : G.dist a b ≤ 2 := by
          have := SimpleGraph.dist_le_diam hediam (u := a) (v := b)
          omega
        have hpos : 0 < G.dist a b := hG.pos_dist_of_ne hne
        have hne1 : G.dist a b ≠ 1 := by
          intro h1
          have := (SimpleGraph.dist_eq_one_iff_adj.mp h1)
          contradiction
        have hdist2 : G.dist a b = 2 := by omega
        obtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist a b
        rw [hdist2] at hp
        have ⟨c, hac, hcb⟩ : ∃ c : V, G.Adj a c ∧ G.Adj c b := by
          cases p with
          | nil => simp [SimpleGraph.Walk.length_nil] at hp
          | cons hac p' =>
            cases p' with
            | nil => simp [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at hp
            | cons hcb p'' =>
              cases p'' with
              | nil => exact ⟨_, hac, hcb⟩
              | cons _ _ =>
                simp only [SimpleGraph.Walk.length_cons] at hp
                omega
  9. The common neighbor c lies in either A or Aᶜ, ensuring |N(a) ∩ Aᶜ| + |N(b) ∩ A| ≥ 1. automation

    If c ∈ A, then c is a neighbor of b in A, giving |N(b) ∩ A| ≥ 1. If c ∉ A, then c ∈ Aᶜ, so c is a neighbor of a in Aᶜ, giving |N(a) ∩ Aᶜ| ≥ 1. In either case, the sum is at least 1.

    lines 122–135

    uses Finset.mem_filter, Finset.card_pos.mpr, Finset.mem_compl

        by_cases hc : c ∈ A
        · have h1 : c ∈ A.filter (fun v => G.Adj v b) := by
            rw [Finset.mem_filter]
            exact ⟨hc, hcb⟩
          have : 1 ≤ (A.filter (fun v => G.Adj v b)).card := Finset.card_pos.mpr ⟨c, h1⟩
          omega
        · have hc' : c ∈ (Aᶜ : Finset V) := by
            rw [Finset.mem_compl]
            exact hc
          have h1 : c ∈ Aᶜ.filter (G.Adj a ·) := by
            rw [Finset.mem_filter]
            exact ⟨hc', hac⟩
          have : 1 ≤ (Aᶜ.filter (G.Adj a ·)).card := Finset.card_pos.mpr ⟨c, h1⟩
          omega
  10. If there exists some vertex b ∈ Aᶜ with no neighbors in A, then the cut has at least δ(G) crossing edges.

    Fix such a vertex b ∈ Aᶜ with |N(b) ∩ A| = 0. The local lemma implies that every a ∈ A must have at least 1 neighbor in Aᶜ. Swapping the roles of A and Aᶜ (using A = (Aᶜ)ᶜ) allows applying cross_cut_card_ge_minDegree_of_diam_two_of_ge1 to the cut (Aᶜ, (Aᶜ)ᶜ), and cross_cut_card_ge_minDegree_of_diam_two_symm equates this to the original cut size.

    lines 142–160

    uses cross_cut_card_ge_minDegree_of_diam_two_local, compl_compl, Finset.mem_filter, cross_cut_card_ge_minDegree_of_diam_two_of_ge1, cross_cut_card_ge_minDegree_of_diam_two_symm

      by_cases h : ∃ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card = 0
      · obtain ⟨b, hb, hb0⟩ := h
        have h_ge1 : ∀ a ∈ A, 1 ≤ (Aᶜ.filter (G.Adj a ·)).card := by
          intro a ha
          have h_loc := cross_cut_card_ge_minDegree_of_diam_two_local G hG hd A a b ha hb
          omega
        have h_ge1' : ∀ a ∈ (Aᶜᶜ : Finset V), 1 ≤ ((Aᶜ : Finset V).filter (fun v => G.Adj v a)).card := by
          simp only [compl_compl]
          intro a ha
          have h := h_ge1 a ha
          have heq : Aᶜ.filter (G.Adj a ·) = (Aᶜ : Finset V).filter (fun v => G.Adj v a) := by
            ext v
            simp only [Finset.mem_filter]
            rw [G.adj_comm]
          rw [heq] at h
          exact h
        have h_step := cross_cut_card_ge_minDegree_of_diam_two_of_ge1 G (Aᶜ : Finset V) (by simp [compl_compl, hA]) h_ge1'
        rw [cross_cut_card_ge_minDegree_of_diam_two_symm] at h_step
        exact h_step
  11. If every vertex b ∈ Aᶜ has at least one neighbor in A, then the cut has at least δ(G) crossing edges.

    When no b ∈ Aᶜ has 0 neighbors in A, every b ∈ Aᶜ has at least 1 neighbor in A by contradiction. The result then follows directly from cross_cut_card_ge_minDegree_of_diam_two_of_ge1 applied to (A, Aᶜ).

    lines 161–166

    uses cross_cut_card_ge_minDegree_of_diam_two_of_ge1

      · have h_ge1 : ∀ b ∈ (Aᶜ : Finset V), 1 ≤ (A.filter (fun v => G.Adj v b)).card := by
          intro b hb
          by_contra hc
          have : (A.filter (fun v => G.Adj v b)).card = 0 := by omega
          exact h ⟨b, hb, this⟩
        exact cross_cut_card_ge_minDegree_of_diam_two_of_ge1 G A hAc h_ge1
compl_compl
The double complement of a set or element in a Boolean algebra is itself (xᶜᶜ = x).
cross_cut_card_ge_minDegree_of_diam_two_symm
The number of crossing edges between Aᶜ and (Aᶜ)ᶜ equals the number of crossing edges between A and Aᶜ.
cross_cut_card_ge_minDegree_of_diam_two_deg
The degree of any vertex b equals the number of its neighbors in Aᶜ plus the number of its neighbors in A.
cross_cut_card_ge_minDegree_of_diam_two_local
For any a ∈ A and b ∈ Aᶜ in a connected diameter-2 graph, the number of neighbors of a in Aᶜ plus the number of neighbors of b in A is at least 1.
cross_cut_card_ge_minDegree_of_diam_two_of_ge1
If Aᶜ is nonempty and every vertex in Aᶜ has at least one neighbor in A, then the cut has at least δ(G) crossing edges.
cross_cut_card_ge_minDegree_of_diam_two_sub
Any vertex b ∈ Aᶜ has at most |Aᶜ| - 1 neighbors in Aᶜ.
cross_cut_card_ge_minDegree_of_diam_two_sum
The number of crossing pairs between A and Aᶜ equals the sum over all b ∈ Aᶜ of the number of neighbors of b in A.
crossing_pairs_card_eq_crossing_edges_card
The number of directed crossing pairs in A × Aᶜ that are edges equals the number of undirected crossing edges.
Finset.card_erase_of_mem
Removing an element that belongs to a finset decreases its cardinality by 1.
Finset.card_filter_add_card_filter_not
For any predicate on a finset, the number of elements satisfying it plus the number not satisfying it equals the total cardinality.
Finset.card_eq_sum_ones
The cardinality of a finset equals the sum of 1 over all of its elements.
Finset.card_le_card
If finset s is a subset of finset t, then |s| ≤ |t|.
Finset.card_pos.mpr
A finset has strictly positive cardinality if and only if it is nonempty.
Finset.mem_compl
An element belongs to the complement of a finset if and only if it does not belong to the finset.
Finset.mem_erase
An element a belongs to s \ {b} if and only if a ≠ b and a ∈ s.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filtering predicate.
Finset.sum_const_nat
The sum of a constant natural number m over a finset s equals |s| * m.
Finset.sum_filter
A sum of a function over elements satisfying a predicate equals the sum over the whole set with an indicator conditional.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finset, then the sum of f is at most the sum of g.
Finset.sum_product_right
A double sum over a Cartesian product can be evaluated by summing over the second component first.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
SimpleGraph.diam_eq_zero_of_ediam_eq_top
If the extended diameter of a graph is ∞, then its diameter is 0.
SimpleGraph.dist_eq_one_iff_adj.mp
If the distance between two vertices in a graph is 1, then they are adjacent.
SimpleGraph.dist_le_diam
The distance between any two vertices in a graph with finite extended diameter is at most its diameter.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
SimpleGraph.Walk.length_cons
Prepending an edge to a walk increases its length by 1.
SimpleGraph.Walk.length_nil
The trivial walk from a vertex to itself has length 0.
Sym2.eq_swap
An unordered pair s(a, b) equals s(b, a).

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

lemma cross_cut_card_ge_minDegree_of_diam_two_symm {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) :    (G.edgeFinset.filter (fun e => ∃ u ∈ (Aᶜ : Finset V), ∃ v ∈ (Aᶜᶜ : Finset V), e = s(u, v))).card =      (G.edgeFinset.filter (fun e => ∃ u ∈ A, ∃ v ∈ (Aᶜ : Finset V), e = s(u, v))).card := by  congr 1  simp only [compl_compl]  ext e  simp only [Finset.mem_filter]  constructor  · rintro ⟨he, u, hu, v, hv, rfl⟩    exact ⟨he, v, hv, u, hu, Sym2.eq_swap⟩  · rintro ⟨he, u, hu, v, hv, rfl⟩    exact ⟨he, v, hv, u, hu, Sym2.eq_swap⟩lemma cross_cut_card_ge_minDegree_of_diam_two_sum {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) :    ((A ×ˢ (Aᶜ : Finset V)).filter (fun p : V × V => G.Adj p.1 p.2)).card =      ∑ b ∈ (Aᶜ : Finset V), (A.filter (fun a => G.Adj a b)).card := by  rw [Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_product_right]  congr 1  ext b  rw [Finset.card_eq_sum_ones, Finset.sum_filter]lemma cross_cut_card_ge_minDegree_of_diam_two_deg {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) (b : V) :    G.degree b = ((G.neighborFinset b).filter (fun a => a ∈ (Aᶜ : Finset V))).card +      (A.filter (fun a => G.Adj a b)).card := by  have h : (G.neighborFinset b).filter (fun a => ¬ a ∈ (Aᶜ : Finset V)) = A.filter (fun a => G.Adj a b) := by    ext a    simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.mem_compl]    rw [G.adj_comm]    tauto  show (G.neighborFinset b).card = _  rw [← h]  exact (Finset.card_filter_add_card_filter_not (fun a => a ∈ (Aᶜ : Finset V))).symmlemma cross_cut_card_ge_minDegree_of_diam_two_sub {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) (b : V) (hb : b ∈ (Aᶜ : Finset V)) :    ((G.neighborFinset b).filter (fun a => a ∈ (Aᶜ : Finset V))).card ≤ (Aᶜ : Finset V).card - 1 := by  have h_sub : (G.neighborFinset b).filter (fun a => a ∈ (Aᶜ : Finset V)) ⊆ (Aᶜ : Finset V).erase b := by    intro a ha    rw [Finset.mem_filter, SimpleGraph.mem_neighborFinset] at ha    rw [Finset.mem_erase]    exact ⟨fun h => G.irrefl (h ▸ ha.1), ha.2⟩  have h_card := Finset.card_le_card h_sub  rw [Finset.card_erase_of_mem hb] at h_card  exact h_cardlemma cross_cut_card_ge_minDegree_of_diam_two_of_ge1 {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) (hAc : (Aᶜ : Finset V).Nonempty)    (h_ge1 : ∀ b ∈ (Aᶜ : Finset V), 1 ≤ (A.filter (fun v => G.Adj v b)).card) :    G.minDegree ≤ (G.edgeFinset.filter (fun e => ∃ u ∈ A, ∃ v ∈ (Aᶜ : Finset V), e = s(u, v))).card := by  rw [← crossing_pairs_card_eq_crossing_edges_card, cross_cut_card_ge_minDegree_of_diam_two_sum]  by_cases h_card : G.minDegree ≤ (Aᶜ : Finset V).card  · have h_sum : (Aᶜ : Finset V).card ≤ ∑ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card := by      have : ∑ b ∈ (Aᶜ : Finset V), 1 ≤ ∑ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card :=        Finset.sum_le_sum (fun b hb => h_ge1 b hb)      simpa using this    omega  · have h_le : (Aᶜ : Finset V).card ≤ G.minDegree := by omega    have h_pos : 1 ≤ (Aᶜ : Finset V).card := hAc.card_pos    have h_each : ∀ b ∈ (Aᶜ : Finset V), G.minDegree + 1 - (Aᶜ : Finset V).card ≤ (A.filter (fun v => G.Adj v b)).card := by      intro b hb      have h1 := G.minDegree_le_degree b      rw [cross_cut_card_ge_minDegree_of_diam_two_deg G A b] at h1      have h2 := cross_cut_card_ge_minDegree_of_diam_two_sub G A b hb      omega    have h_sum : ∑ b ∈ (Aᶜ : Finset V), (G.minDegree + 1 - (Aᶜ : Finset V).card) ≤ ∑ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card :=      Finset.sum_le_sum (fun b hb => h_each b hb)    rw [Finset.sum_const_nat (fun _ _ => rfl)] at h_sum    have h_ineq : G.minDegree ≤ (Aᶜ : Finset V).card * (G.minDegree + 1 - (Aᶜ : Finset V).card) := by      have h_rew : G.minDegree + 1 - (Aᶜ : Finset V).card = G.minDegree - (Aᶜ : Finset V).card + 1 := by omega      rw [h_rew]      zify [h_le]      have h1 : 0 ≤ ((Aᶜ : Finset V).card : ℤ) - 1 := by omega      have h2 : 0 ≤ (G.minDegree : ℤ) - (Aᶜ : Finset V).card := by omega      have h3 : 0 ≤ (((Aᶜ : Finset V).card : ℤ) - 1) * ((G.minDegree : ℤ) - (Aᶜ : Finset V).card) := mul_nonneg h1 h2      nlinarith    omegalemma cross_cut_card_ge_minDegree_of_diam_two_local {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : G.diam = 2)    (A : Finset V) (a b : V) (ha : a ∈ A) (hb : b ∈ (Aᶜ : Finset V)) :    1 ≤ (Aᶜ.filter (G.Adj a ·)).card + (A.filter (fun v => G.Adj v b)).card := by  have hediam : G.ediam ≠ ⊤ := by    intro h    have : G.diam = 0 := SimpleGraph.diam_eq_zero_of_ediam_eq_top h    omega  by_cases hab : G.Adj a b  · have h1 : b ∈ Aᶜ.filter (G.Adj a ·) := by      rw [Finset.mem_filter]      exact ⟨hb, hab⟩    have : 1 ≤ (Aᶜ.filter (G.Adj a ·)).card := Finset.card_pos.mpr ⟨b, h1⟩    omega  · have hne : a ≠ b := by      rintro rfl      have : a ∈ A ∧ a ∈ Aᶜ := ⟨ha, hb⟩      simp at this    have hle : G.dist a b ≤ 2 := by      have := SimpleGraph.dist_le_diam hediam (u := a) (v := b)      omega    have hpos : 0 < G.dist a b := hG.pos_dist_of_ne hne    have hne1 : G.dist a b ≠ 1 := by      intro h1      have := (SimpleGraph.dist_eq_one_iff_adj.mp h1)      contradiction    have hdist2 : G.dist a b = 2 := by omega    obtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist a b    rw [hdist2] at hp    have ⟨c, hac, hcb⟩ : ∃ c : V, G.Adj a c ∧ G.Adj c b := by      cases p with      | nil => simp [SimpleGraph.Walk.length_nil] at hp      | cons hac p' =>        cases p' with        | nil => simp [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at hp        | cons hcb p'' =>          cases p'' with          | nil => exact ⟨_, hac, hcb⟩          | cons _ _ =>            simp only [SimpleGraph.Walk.length_cons] at hp            omega    by_cases hc : c ∈ A    · have h1 : c ∈ A.filter (fun v => G.Adj v b) := by        rw [Finset.mem_filter]        exact ⟨hc, hcb⟩      have : 1 ≤ (A.filter (fun v => G.Adj v b)).card := Finset.card_pos.mpr ⟨c, h1⟩      omega    · have hc' : c ∈ (Aᶜ : Finset V) := by        rw [Finset.mem_compl]        exact hc      have h1 : c ∈ Aᶜ.filter (G.Adj a ·) := by        rw [Finset.mem_filter]        exact ⟨hc', hac⟩      have : 1 ≤ (Aᶜ.filter (G.Adj a ·)).card := Finset.card_pos.mpr ⟨c, h1⟩      omega/-- In a diameter-2 graph every nontrivial cut carries at least δ(G) edges. -/theorem cross_cut_card_ge_minDegree_of_diam_two {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : G.diam = 2)    (A : Finset V) (hA : A.Nonempty) (hAc : (Aᶜ : Finset V).Nonempty) :    G.minDegree ≤ (G.edgeFinset.filter (fun e => ∃ u ∈ A, ∃ v ∈ (Aᶜ : Finset V), e = s(u, v))).card := by  by_cases h : ∃ b ∈ (Aᶜ : Finset V), (A.filter (fun v => G.Adj v b)).card = 0  · obtain ⟨b, hb, hb0⟩ := h    have h_ge1 : ∀ a ∈ A, 1 ≤ (Aᶜ.filter (G.Adj a ·)).card := by      intro a ha      have h_loc := cross_cut_card_ge_minDegree_of_diam_two_local G hG hd A a b ha hb      omega    have h_ge1' : ∀ a ∈ (Aᶜᶜ : Finset V), 1 ≤ ((Aᶜ : Finset V).filter (fun v => G.Adj v a)).card := by      simp only [compl_compl]      intro a ha      have h := h_ge1 a ha      have heq : Aᶜ.filter (G.Adj a ·) = (Aᶜ : Finset V).filter (fun v => G.Adj v a) := by        ext v        simp only [Finset.mem_filter]        rw [G.adj_comm]      rw [heq] at h      exact h    have h_step := cross_cut_card_ge_minDegree_of_diam_two_of_ge1 G (Aᶜ : Finset V) (by simp [compl_compl, hA]) h_ge1'    rw [cross_cut_card_ge_minDegree_of_diam_two_symm] at h_step    exact h_step  · have h_ge1 : ∀ b ∈ (Aᶜ : Finset V), 1 ≤ (A.filter (fun v => G.Adj v b)).card := by      intro b hb      by_contra hc      have : (A.filter (fun v => G.Adj v b)).card = 0 := by omega      exact h ⟨b, hb, this⟩    exact cross_cut_card_ge_minDegree_of_diam_two_of_ge1 G A hAc h_ge1
See it in the graphDiscuss this resultChallenge it