pathGreedyRun_eq_count_and_odd
theoremverified
Twice the greedy count equals the number of true edges plus the number of odd true runs.
Statement
open scoped BigOperators in theorem pathGreedyRun_eq_count_and_odd (xs : List Bool) : 2 * pathGreedyRun false xs = xs.countP id + odd_run_count xs
- Source
- Finite-state path cut-matching certificate for OP-827; exhaustive transition check in experiment 22529.
- Verified
- 11 Nov 2026
- Axioms
Quot.soundpropext- Built on 6
- pathGreedyRun_identityThe greedy matching count and pending run parity satisfy an exact counting identity.
- pathOddRunFinish_identityThe pending parity counter agrees with the existing odd-run counter.
- odd_run_count
odd_run_count lis the number of maximal runs oftruein the boolean wordlwhose length is odd. The finalfalseis appended so… - pathGreedyRunGreedily count disjoint true edges in a Boolean edge word.
- pathOddRunFinishCount odd true runs while retaining a pending run parity.
- odd_run_aux
odd_run_aux inRun oddLen lscans the boolean listlleft to right, keeping a flaginRun(currently inside a run oftrues) and…
- Used by 1
- pathCertOddRunIneqFor any four-color path word, the signed sum of odd crossing-run counts for the seven masks is nonpositive.
Lean source view module on GitHub
open scoped BigOperators in theorem pathGreedyRun_eq_count_and_odd (xs : List Bool) : 2 * pathGreedyRun false xs = xs.countP id + odd_run_count xs := by have h := pathGreedyRun_identity false xs have h2 := pathOddRunFinish_identity false false xs simp only [Bool.false_and] at h h2 change odd_run_count xs = pathOddRunFinish false xs at h2 simpa [h2] using h