cross_cut_card_ge_minDegree_of_diam_two
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
- crossing_pairs_card_eq_crossing_edges_cardFor a finite simple graph G and a vertex set A, the number of ordered adjacent pairs (a, b) with a ∈ A and b ∈ Aᶜ equals the number of…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 2
- edge_connectivity_ge_min_degree_mul_lly_lower_bound_twoEvery finite connected graph of diameter 2 has κ'(G) ≥ δ(G) · κ_LLY^(2)(G).
- 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
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.
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.
uses
compl_compl,Finset.mem_filter,Sym2.eq_swapcongr 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⟩
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.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_product_rightrw [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]
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.
uses
Finset.mem_filter,SimpleGraph.mem_neighborFinset,Finset.mem_compl,Finset.card_filter_add_card_filter_nothave 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
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.
uses
Finset.mem_filter,SimpleGraph.mem_neighborFinset,Finset.mem_erase,Finset.card_le_card,Finset.card_erase_of_memhave 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
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.
uses
crossing_pairs_card_eq_crossing_edges_card,cross_cut_card_ge_minDegree_of_diam_two_sum,Finset.sum_le_sumrw [← 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
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).
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
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.
uses
SimpleGraph.diam_eq_zero_of_ediam_eq_top,Finset.mem_filter,Finset.card_pos.mprhave 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
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.
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
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.
uses
Finset.mem_filter,Finset.card_pos.mpr,Finset.mem_complby_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
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.
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_symmby_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
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ᶜ).
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
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.
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