digraph_cut_twenty_superlevel_equality_patterns
The five robust two-cycle superlevel alternatives have exactly four equality patterns when their six counts sum to twenty.
Statement
theorem digraph_cut_twenty_superlevel_equality_patterns
(n1 n2 n3 n4 n5 n6 : ℕ)
(hmono : n6 ≤ n5 ∧ n5 ≤ n4 ∧ n4 ≤ n3 ∧ n3 ≤ n2 ∧ n2 ≤ n1)
(hsum : n1+n2+n3+n4+n5+n6=20)
(h6 : 1 ≤ n6 ∨ 3 ≤ n5) (h5 : 2 ≤ n5 ∨ 4 ≤ n4)
(h4 : 3 ≤ n4 ∨ 5 ≤ n3) (h3 : 4 ≤ n3 ∨ 6 ≤ n2)
(h2 : 5 ≤ n2 ∨ 7 ≤ n1) :
(n1=5 ∧ n2=5 ∧ n3=4 ∧ n4=3 ∧ n5=3 ∧ n6=0) ∨
(n1=5 ∧ n2=5 ∧ n3=4 ∧ n4=4 ∧ n5=1 ∧ n6=1) ∨
(n1=5 ∧ n2=5 ∧ n3=5 ∧ n4=2 ∧ n5=2 ∧ n6=1) ∨
(n1=5 ∧ n2=5 ∧ n3=4 ∧ n4=3 ∧ n5=2 ∧ n6=1)- Source
- Finite arithmetic in experiment 26240; equality case of digraph_seven_out_robust_cut_thresholds.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_twenty_cut_degree_profile_under_two_cycle_sequencesFor a seven-outregular two-cycle-free part with a twenty-arc outgoing cut, the displayed robust and two-cycle degree-sequence criteria…
The proof, explained
The proof proceeds by an exhaustive case analysis across the five disjunctive hypotheses. Expanding each binary alternative produces $2^5 = 32$ branches. In each branch, Presburger linear arithmetic (`omega`) combines the monotonicity constraints, the fixed sum of 20, and the case's lower bounds to show that the only integer solutions are the four enumerated patterns.
The sequence $(n_1, n_2, n_3, n_4, n_5, n_6)$ is equal to one of the four candidate patterns: $(5, 5, 4, 3, 3, 0)$, $(5, 5, 4, 4, 1, 1)$, $(5, 5, 5, 2, 2, 1)$, or $(5, 5, 4, 3, 2, 1)$. automation
Perform a full case split on each of the five disjunctions $h_6, h_5, h_4, h_3, h_2$ in turn, yielding $2^5 = 32$ subcases. In each subcase, the linear integer constraints—consisting of the ordering $n_6 \le n_5 \le n_4 \le n_3 \le n_2 \le n_1$, the sum condition $\sum_{i=1}^6 n_i = 20$, and the specific lower bounds chosen in that branch—are checked by Presburger linear arithmetic (`omega`), which verifies that every feasible assignment matches one of the four stated tuples.
rcases h6 with h6 | h6 <;> rcases h5 with h5 | h5 <;> rcases h4 with h4 | h4 <;> rcases h3 with h3 | h3 <;> rcases h2 with h2 | h2 <;> omega
- The proof relies on Lean's `omega` tactic to automatically resolve 32 systems of linear integer inequalities and equalities without spelling out the individual arithmetic deductions on paper.
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_cut_twenty_superlevel_equality_patterns (n1 n2 n3 n4 n5 n6 : ℕ) (hmono : n6 ≤ n5 ∧ n5 ≤ n4 ∧ n4 ≤ n3 ∧ n3 ≤ n2 ∧ n2 ≤ n1) (hsum : n1+n2+n3+n4+n5+n6=20) (h6 : 1 ≤ n6 ∨ 3 ≤ n5) (h5 : 2 ≤ n5 ∨ 4 ≤ n4) (h4 : 3 ≤ n4 ∨ 5 ≤ n3) (h3 : 4 ≤ n3 ∨ 6 ≤ n2) (h2 : 5 ≤ n2 ∨ 7 ≤ n1) : (n1=5 ∧ n2=5 ∧ n3=4 ∧ n4=3 ∧ n5=3 ∧ n6=0) ∨ (n1=5 ∧ n2=5 ∧ n3=4 ∧ n4=4 ∧ n5=1 ∧ n6=1) ∨ (n1=5 ∧ n2=5 ∧ n3=5 ∧ n4=2 ∧ n5=2 ∧ n6=1) ∨ (n1=5 ∧ n2=5 ∧ n3=4 ∧ n4=3 ∧ n5=2 ∧ n6=1) := by rcases h6 with h6 | h6 <;> rcases h5 with h5 | h5 <;> rcases h4 with h4 | h4 <;> rcases h3 with h3 | h3 <;> rcases h2 with h2 | h2 <;> omega