digraph_both_cuts_ge_ceil_div_six_of_cases
If a finite digraph G admits a vertex subset A with both directed cut counts e(A, Aᶜ) and e(Aᶜ, A) at least ⌈m/6⌉ whenever some vertex has in-degree at least m/3 + 1, and also whenever every vertex has in-degree strictly below m/3 + 1, then there exists a vertex bipartition V = A ⊔ B with e(A, B) ≥ ⌈m/6⌉ and e(B, A) ≥ ⌈m/6⌉.
Statement
theorem digraph_both_cuts_ge_ceil_div_six_of_cases {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (h_high : (∃ z : V, (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) (h_low : (∀ v : V, ((Finset.univ.filter fun u => G.Adj u v).card : ℚ) < (digraph_edge_count G : ℚ) / 3 + 1) → ∃ 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) : ∃ A B : Finset V, Disjoint A B ∧ A ∪ B = Finset.univ ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A B ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G B A
- Source
- arXiv:2610.21381 Section 5 lines 1506-1524
- Verified
- 25 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.
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a directed graph on $V$ with decidable adjacency relation $G.\text{Adj}$.
Assume the following two hypotheses:
1. h_high: If there exists a vertex $z \in V$ such that the in-degree of $z$ (the number of vertices $u \in V$ such that $G.\text{Adj}(u, z)$) is at least $\frac{|E(G)|}{3} + 1$ (as rational numbers), then there exists a subset $A \subseteq V$ such that both the directed cut from $A$ to $A^c$ and the directed cut from $A^c$ to $A$ have size at least $\lceil |E(G)| / 6 \rceil$.
2. h_low: If for every vertex $v \in V$, the in-degree of $v$ is strictly less than $\frac{|E(G)|}{3} + 1$ (as rational numbers), then there exists a subset $A \subseteq V$ such that both the directed cut from $A$ to $A^c$ and the directed cut from $A^c$ to $A$ have size at least $\lceil |E(G)| / 6 \rceil$.
Then there exist disjoint subsets $A, B \subseteq V$ partitioning $V$ ($A \cup B = V$) such that:
- the number of directed edges from $A$ to $B$ is at least $\lceil |E(G)| / 6 \rceil$, and
- the number of directed edges from $B$ to $A$ is at least $\lceil |E(G)| / 6 \rceil$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by case distinction on whether the digraph contains a vertex of high in-degree (at least m/3 + 1). In the high in-degree case, hypothesis h_high directly provides a subset A whose directed cuts with its complement both have size at least ⌈m/6⌉. In the remaining case, all vertices have in-degree strictly below m/3 + 1, so hypothesis h_low applies and yields such a subset A. In both cases, taking B to be the complement of A gives the desired bipartition V = A ⊔ B.
We split into two cases: either some vertex has in-degree at least m/3 + 1, or no vertex does.
We perform a case split on whether there exists a vertex z with in-degree (the number of vertices u with an edge to z) at least m/3 + 1, where m is the total number of edges in the digraph G.
by_cases h : ∃ z : V, (digraph_edge_count G : ℚ) / 3 + 1 ≤ ((Finset.univ.filter fun u => G.Adj u z).card : ℚ)
When a high in-degree vertex exists, we obtain the required bipartition.
Applying the hypothesis h_high gives a subset A ⊆ V such that both directed cuts e(A, Aᶜ) and e(Aᶜ, A) have cardinality at least ⌈m/6⌉. Setting B = Aᶜ, the pair (A, B) is disjoint by Finset.disjoint_left and Finset.mem_compl.mp, and covers V by Finset.union_compl, satisfying all requirements.
uses
Finset.disjoint_left,Finset.mem_compl.mp,Finset.union_compl· rcases h_high h with ⟨A, hA, hA'⟩ exact ⟨A, Aᶜ, by rw [Finset.disjoint_left] intro a ha hb exact (Finset.mem_compl.mp hb) ha, Finset.union_compl A, hA, hA'⟩
In the complementary case, every vertex has in-degree strictly less than m/3 + 1.
Since no vertex has in-degree at least m/3 + 1, any hypothetical vertex with in-degree ≥ m/3 + 1 would contradict the assumption. By not_le.mp, every vertex v must have in-degree strictly less than m/3 + 1.
uses
not_le.mp· have hlow : ∀ v : V, ((Finset.univ.filter fun u => G.Adj u v).card : ℚ) < (digraph_edge_count G : ℚ) / 3 + 1 := by intro v exact not_le.mp (fun hle => h ⟨v, hle⟩)
When all vertices have low in-degree, we obtain the required bipartition.
Applying the hypothesis h_low to the fact that all in-degrees are strictly below m/3 + 1 gives a subset A ⊆ V with both cut sizes at least ⌈m/6⌉. Setting B = Aᶜ, disjointness follows from Finset.disjoint_left and Finset.mem_compl.mp, and coverage from Finset.union_compl.
uses
Finset.disjoint_left,Finset.mem_compl.mp,Finset.union_complrcases h_low hlow with ⟨A, hA, hA'⟩ exact ⟨A, Aᶜ, by rw [Finset.disjoint_left] intro a ha hb exact (Finset.mem_compl.mp hb) ha, Finset.union_compl A, hA, hA'⟩
Finset.disjoint_left- Two finite sets s and t are disjoint if and only if no element of s belongs to t.
Finset.mem_compl.mp- If an element belongs to the complement of a finite set, then it does not belong to the set itself.
Finset.union_compl- The union of any finite subset of a finite type with its complement is the universal set.
not_le.mp- If a value is not less than or equal to another in a linear order, then it is strictly greater.
- The formal proof requires explicit verification that a subset and its complement are disjoint and cover the whole vertex set, whereas on paper setting B = Aᶜ trivially yields a bipartition.
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.
/-- Case reduction for Theorem 1.4: if a digraph admits ceil(m/6) cuts in both directions under high in-degree and under low in-degree, then it admits such a bipartition unconditionally. -/theorem digraph_both_cuts_ge_ceil_div_six_of_cases {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (h_high : (∃ z : V, (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) (h_low : (∀ v : V, ((Finset.univ.filter fun u => G.Adj u v).card : ℚ) < (digraph_edge_count G : ℚ) / 3 + 1) → ∃ 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) : ∃ A B : Finset V, Disjoint A B ∧ A ∪ B = Finset.univ ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A B ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G B A := by by_cases h : ∃ z : V, (digraph_edge_count G : ℚ) / 3 + 1 ≤ ((Finset.univ.filter fun u => G.Adj u z).card : ℚ) · rcases h_high h with ⟨A, hA, hA'⟩ exact ⟨A, Aᶜ, by rw [Finset.disjoint_left] intro a ha hb exact (Finset.mem_compl.mp hb) ha, Finset.union_compl A, hA, hA'⟩ · have hlow : ∀ v : V, ((Finset.univ.filter fun u => G.Adj u v).card : ℚ) < (digraph_edge_count G : ℚ) / 3 + 1 := by intro v exact not_le.mp (fun hle => h ⟨v, hle⟩) rcases h_low hlow with ⟨A, hA, hA'⟩ exact ⟨A, Aᶜ, by rw [Finset.disjoint_left] intro a ha hb exact (Finset.mem_compl.mp hb) ha, Finset.union_compl A, hA, hA'⟩