digraph_both_cuts_ge_ceil_div_six_of_high_indegree
Case 1 of the proof of Theorem 1.4: in a loopless digraph with m arcs, if a vertex z has in-degree at least m/3 + 1 and some set A₀ ∋ z has e(A₀, V∖A₀) ≥ m/6, then some set A has e(A, V∖A) ≥ ⌈m/6⌉ and e(V∖A, A) ≥ ⌈m/6⌉ (keep z and the tails of ⌈m/6⌉ arcs leaving A₀).
Statement
theorem digraph_both_cuts_ge_ceil_div_six_of_high_indegree {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hloop : ∀ v, ¬ G.Adj v v) (z : V) (A₀ : Finset V) (hz : z ∈ A₀) (hcut : (digraph_edge_count G : ℚ) / 6 ≤ digraph_cut_count G A₀ A₀ᶜ) (hin : (digraph_edge_count G : ℚ) / 3 + 1 ≤ (Finset.univ.filter fun u => G.Adj u z).card) : ∃ A : Finset V, ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A Aᶜ ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G Aᶜ A
- Source
- arXiv:2610.21381, proof of Theorem 1.4 (Section 5), the case d⁻(z) ≥ m/3 + 1
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
The proof, explained
The proof chooses a subset C of k = ⌈m/6⌉ edges leaving A₀ and defines A to be {z} ∪ T, where T is the set of tails of C. Since T ⊆ A₀ and z ∈ A₀, all edges of C leave A, guaranteeing that e(A, V \ A) ≥ k. For the reverse cut, the in-degree hypothesis implies that z has at least 2k in-neighbors. Because the digraph has no self-loops, z itself is not an in-neighbor, so at most |T| ≤ k in-neighbors lie in A; the remaining at least k in-neighbors lie in V \ A and each sends an edge to z ∈ A, ensuring e(V \ A, A) ≥ k.
Let m = |E(G)| and k = ⌈m/6⌉; choose a subset C of k edges leaving A₀, and let T be the set of tails of C.
We define m to be the edge count of G, k to be ⌈m/6⌉, and S to be the set of directed edges leaving A₀. Since |S| ≥ m/6 by assumption, the ceiling property gives k ≤ |S|. Hence there exists a subset C ⊆ S with exactly k edges, and we define T to be the projection of C onto the first component (the set of tails of C).
uses
Nat.ceil_le.2,Finset.exists_subset_card_eqset m := digraph_edge_count G set k := ⌈(m : ℚ) / 6⌉₊ set S := (A₀ ×ˢ A₀ᶜ).filter fun p => G.Adj p.1 p.2 with hS have hkS : k ≤ S.card := Nat.ceil_le.2 hcut obtain ⟨C, hCS, hCk⟩ := Finset.exists_subset_card_eq hkS set T := C.image Prod.fst
T is a subset of A₀.
Every vertex u ∈ T is the tail of some edge p ∈ C. Since C ⊆ S and every edge in S originates in A₀, its tail must belong to A₀.
uses
Finset.mem_image.1,Finset.mem_filter,Finset.mem_producthave hTA₀ : T ⊆ A₀ := by intro u hu obtain ⟨p, hp, rfl⟩ := Finset.mem_image.1 hu have := hCS hp simp only [hS, Finset.mem_filter, Finset.mem_product] at this exact this.1.1
It suffices to show that the candidate set A = {z} ∪ T satisfies e(A, V \ A) ≥ k and e(V \ A, A) ≥ k.
We instantiate the existential quantifier with A = {z} ∪ T (written insert z T). This produces two subgoals: bounding the forward cut e(A, V \ A) from below by k, and bounding the backward cut e(V \ A, A) from below by k.
refine ⟨insert z T, ?_, ?_⟩The cut leaving A has at least k edges: e(A, V \ A) ≥ k.
Since |C| = k, it suffices to show that C is contained in the cut edges from A to V \ A. For any edge p = (u, v) ∈ C, its tail u is in T ⊆ A. Its head v is not in A₀ because p leaves A₀. Since A = {z} ∪ T ⊆ A₀ (as z ∈ A₀ and T ⊆ A₀), v cannot belong to A. Therefore every edge in C crosses from A to V \ A, which implies e(A, V \ A) ≥ |C| = k.
uses
Finset.card_le_card,Finset.mem_filter,Finset.mem_product,Finset.mem_compl,Finset.mem_insert,Or.inr,Finset.mem_image_of_mem· rw [← hCk] unfold digraph_cut_count apply Finset.card_le_card intro p hp have hp' := hCS hp simp only [hS, Finset.mem_filter, Finset.mem_product, Finset.mem_compl] at hp' simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert] refine ⟨⟨Or.inr (Finset.mem_image_of_mem _ hp), ?_⟩, hp'.2⟩ rintro (h | h) · exact hp'.1.2 (h ▸ hz) · exact hp'.1.2 (hTA₀ h)
The in-neighborhood I of z has cardinality at least 2k.
Let I be the in-neighborhood of z. The ceiling inequality k < m/6 + 1 implies 2k < m/3 + 2. Combining this with the in-degree hypothesis m/3 + 1 ≤ |I| yields 2k < |I| + 1 over the rationals. For natural numbers, this strict inequality is equivalent to 2k ≤ |I|.
uses
Nat.ceil_lt_add_one,Nat.lt_add_one_iff.1· set I := Finset.univ.filter fun u => G.Adj u z have hk : (k : ℚ) < m / 6 + 1 := Nat.ceil_lt_add_one (by positivity) have h2k : 2 * k ≤ I.card := by have : ((2 * k : ℕ) : ℚ) < (I.card : ℚ) + 1 := by push_cast; linarith exact Nat.lt_add_one_iff.1 (by exact_mod_cast this)
At most k in-neighbors of z lie in A, so |I| ≤ |I \ A| + k.
We show I ⊆ (I \ A) ∪ T. For any u ∈ I, if u ∉ T, then u cannot equal z because G has no self-loops, so u ∉ {z} ∪ T = A, meaning u ∈ I \ A. Hence |I| ≤ |(I \ A) ∪ T| ≤ |I \ A| + |T|. Since T is the image of C under first projection, |T| ≤ |C| = k, which gives |I| ≤ |I \ A| + k.
uses
Finset.mem_union_right,Finset.mem_union_left,Finset.mem_sdiff.2,Finset.mem_insert,Finset.mem_filter.1,Finset.card_le_card,Finset.card_union_le,Finset.card_image_lehave hIT : I.card ≤ (I \ insert z T).card + k := by have h1 : I ⊆ (I \ insert z T) ∪ T := by intro u hu by_cases huT : u ∈ T · exact Finset.mem_union_right _ huT · refine Finset.mem_union_left _ (Finset.mem_sdiff.2 ⟨hu, ?_⟩) rw [Finset.mem_insert] rintro (rfl | h) · exact hloop u (Finset.mem_filter.1 hu).2 · exact huT h calc I.card ≤ ((I \ insert z T) ∪ T).card := Finset.card_le_card h1 _ ≤ (I \ insert z T).card + T.card := Finset.card_union_le _ _ _ ≤ (I \ insert z T).card + k := by have : T.card ≤ C.card := Finset.card_image_le omega
The vertices in I \ A provide at least |I \ A| edges from V \ A to A: |I \ A| ≤ e(V \ A, A).
The map u ↦ (u, z) is injective. For any u ∈ I \ A, u lies in V \ A, z lies in A, and (u, z) is an edge of G because u ∈ I. Thus the image of I \ A under this map is a subset of the cut edges from V \ A to A, proving that |I \ A| ≤ e(V \ A, A).
uses
Finset.card_image_of_injective,Prod.mk.inj,Finset.card_le_card,Finset.mem_image.1,Finset.mem_sdiff,Finset.mem_filter,Finset.mem_product,Finset.mem_compl,Finset.mem_insert_self,and_true,Finset.mem_filter.1have hD : (I \ insert z T).card ≤ digraph_cut_count G (insert z T)ᶜ (insert z T) := by unfold digraph_cut_count rw [← Finset.card_image_of_injective _ (fun a b h => (Prod.mk.inj h).1 : Function.Injective fun u : V => (u, z))] apply Finset.card_le_card intro p hp obtain ⟨u, hu, rfl⟩ := Finset.mem_image.1 hp rw [Finset.mem_sdiff] at hu simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert_self, and_true] exact ⟨hu.2, (Finset.mem_filter.1 hu.1).2⟩
The cut entering A has at least k edges: e(V \ A, A) ≥ k.
Combining 2k ≤ |I|, |I| ≤ |I \ A| + k, and |I \ A| ≤ e(V \ A, A) yields e(V \ A, A) ≥ |I| - k ≥ 2k - k = k by linear integer arithmetic, concluding the proof.
omega
Nat.ceil_le.2- If a rational number x is at most a natural number n, then ⌈x⌉ ≤ n.
Finset.exists_subset_card_eq- A finite set with cardinality at least n contains a subset of cardinality exactly n.
Finset.mem_image.1- If an element is in the image f(S), then it equals f(a) for some a ∈ S.
Finset.mem_filter- An element belongs to the filtered set {x ∈ S | P x} if and only if it belongs to S and satisfies P.
Finset.mem_product- A pair (a, b) belongs to the Cartesian product S ×ˢ T if and only if a ∈ S and b ∈ T.
Finset.card_le_card- If S ⊆ T, then |S| ≤ |T|.
Finset.mem_compl- An element belongs to the complement Sᶜ if and only if it does not belong to S.
Finset.mem_insert- An element belongs to {b} ∪ S if and only if it equals b or belongs to S.
Or.inr- If B holds, then A ∨ B holds.
Finset.mem_image_of_mem- If a ∈ S, then f(a) belongs to the image f(S).
Nat.ceil_lt_add_one- For any nonnegative number a, ⌈a⌉ < a + 1.
Nat.lt_add_one_iff.1- For natural numbers, a < b + 1 implies a ≤ b.
Finset.mem_union_right- If a ∈ T, then a ∈ S ∪ T.
Finset.mem_union_left- If a ∈ S, then a ∈ S ∪ T.
Finset.mem_sdiff.2- If a ∈ S and a ∉ T, then a ∈ S \ T.
Finset.mem_filter.1- If an element belongs to {x ∈ S | P x}, then it belongs to S and satisfies P.
Finset.card_union_le- For finite sets S and T, |S ∪ T| ≤ |S| + |T|.
Finset.card_image_le- The image of a finite set under any function has size at most that of the domain: |f(S)| ≤ |S|.
Finset.card_image_of_injective- An injective function on a finite set preserves cardinality: |f(S)| = |S|.
Prod.mk.inj- If two pairs (a, b) and (c, d) are equal, then their first components are equal: a = c.
Finset.mem_sdiff- An element belongs to S \ T if and only if it belongs to S and not to T.
Finset.mem_insert_self- An element a always belongs to {a} ∪ S.
and_true- For any proposition P, the conjunction P ∧ True is equivalent to P.
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.
theorem digraph_both_cuts_ge_ceil_div_six_of_high_indegree {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hloop : ∀ v, ¬ G.Adj v v) (z : V) (A₀ : Finset V) (hz : z ∈ A₀) (hcut : (digraph_edge_count G : ℚ) / 6 ≤ digraph_cut_count G A₀ A₀ᶜ) (hin : (digraph_edge_count G : ℚ) / 3 + 1 ≤ (Finset.univ.filter fun u => G.Adj u z).card) : ∃ A : Finset V, ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A Aᶜ ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G Aᶜ A := by set m := digraph_edge_count G set k := ⌈(m : ℚ) / 6⌉₊ set S := (A₀ ×ˢ A₀ᶜ).filter fun p => G.Adj p.1 p.2 with hS have hkS : k ≤ S.card := Nat.ceil_le.2 hcut obtain ⟨C, hCS, hCk⟩ := Finset.exists_subset_card_eq hkS set T := C.image Prod.fst have hTA₀ : T ⊆ A₀ := by intro u hu obtain ⟨p, hp, rfl⟩ := Finset.mem_image.1 hu have := hCS hp simp only [hS, Finset.mem_filter, Finset.mem_product] at this exact this.1.1 refine ⟨insert z T, ?_, ?_⟩ · rw [← hCk] unfold digraph_cut_count apply Finset.card_le_card intro p hp have hp' := hCS hp simp only [hS, Finset.mem_filter, Finset.mem_product, Finset.mem_compl] at hp' simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert] refine ⟨⟨Or.inr (Finset.mem_image_of_mem _ hp), ?_⟩, hp'.2⟩ rintro (h | h) · exact hp'.1.2 (h ▸ hz) · exact hp'.1.2 (hTA₀ h) · set I := Finset.univ.filter fun u => G.Adj u z have hk : (k : ℚ) < m / 6 + 1 := Nat.ceil_lt_add_one (by positivity) have h2k : 2 * k ≤ I.card := by have : ((2 * k : ℕ) : ℚ) < (I.card : ℚ) + 1 := by push_cast; linarith exact Nat.lt_add_one_iff.1 (by exact_mod_cast this) have hIT : I.card ≤ (I \ insert z T).card + k := by have h1 : I ⊆ (I \ insert z T) ∪ T := by intro u hu by_cases huT : u ∈ T · exact Finset.mem_union_right _ huT · refine Finset.mem_union_left _ (Finset.mem_sdiff.2 ⟨hu, ?_⟩) rw [Finset.mem_insert] rintro (rfl | h) · exact hloop u (Finset.mem_filter.1 hu).2 · exact huT h calc I.card ≤ ((I \ insert z T) ∪ T).card := Finset.card_le_card h1 _ ≤ (I \ insert z T).card + T.card := Finset.card_union_le _ _ _ ≤ (I \ insert z T).card + k := by have : T.card ≤ C.card := Finset.card_image_le omega have hD : (I \ insert z T).card ≤ digraph_cut_count G (insert z T)ᶜ (insert z T) := by unfold digraph_cut_count rw [← Finset.card_image_of_injective _ (fun a b h => (Prod.mk.inj h).1 : Function.Injective fun u : V => (u, z))] apply Finset.card_le_card intro p hp obtain ⟨u, hu, rfl⟩ := Finset.mem_image.1 hp rw [Finset.mem_sdiff] at hu simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_compl, Finset.mem_insert_self, and_true] exact ⟨hu.2, (Finset.mem_filter.1 hu.1).2⟩ omega