AFTD Auto-Formalizing Theoretical Domains

digraph_both_cuts_ge_ceil_div_six_of_cases

theoremverified

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

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.

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

    lines 16–17

      by_cases h : ∃ z : V, (digraph_edge_count G : ℚ) / 3 + 1 ≤
          ((Finset.univ.filter fun u => G.Adj u z).card : ℚ)
  2. 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.

    lines 18–22

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

    lines 23–26

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

    lines 27–31

    uses Finset.disjoint_left, Finset.mem_compl.mp, Finset.union_compl

        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'⟩
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.

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

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