A Lean Certificate for the Single Source Unsplittable Flow Cost Counterexample
Version 1 / Oct 01, 2026 / CC BY 4.0
Abstract
We explain a standalone Lean 4 and Mathlib verification of the finite counterexample announced by Dmitry Rybin to the cost-preserving single-source unsplittable-flow conjecture. The instance has seven vertices, nine directed arcs, and three terminal demands. An exact rational path flow saturates every arc, has cost 58, and has largest demand 15. Exhaustive graph-path classification reduces every unsplittable routing to two choices per terminal. Three backbone-arc inequalities force any routing with load at most the fractional load plus 15 to use at least two paid routes, each costing 30. Thus every such routing costs at least 60, ruling out cost preservation even with a non-strict congestion bound. We present the numerical certificate, its graph realization, and the boundary between the pinned proved implementation and its statement-only verification interface. The contribution is an exposition of a source-based formal certificate; no new counterexample, first formalization, or general rounding algorithm is claimed.
Provenance statement
Formalizations
Tools used
- Lean
- LeanVersion 4.33.0 (historical pinned proofs)
- OpenAI
- CodexVersion GPT-6.1 (manuscript)
References
- de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 Theorem Prover and Programming Language. Automated Deduction – CADE 28, vol. 12699, pp. 625–635. 2021. \urlhttps://doi.org/10.1007/978-3-030-79876-5_37DOI
- Dinitz, Yefim; Garg, Naveen; Goemans, Michel X. On the Single-Source Unsplittable Flow Problem. Combinatorica, vol. 19, no. 1, pp. 17–41. 1999. \urlhttps://doi.org/10.1007/s004930050043DOI
- DiscreteAlias. unsplittable-flow. 2026. Separate verification and catalogue of cost-conjecture formulations. Repository consulted October 1, 2026. \urlhttps://github.com/DiscreteAlias/unsplittable-flow
- Hickey, Jason. dinitz-verify. 2026. With Claude assistance; separate verification of the same finite witness. Repository consulted October 1, 2026. \urlhttps://github.com/jyh/dinitz-verify
- Palomar Registry. PALOMAR-2026-08-29-000003, version 1. 2026. Registered August 29, 2026. \urlhttps://palomar-registry.org/entry?id=PALOMAR-2026-08-29-000003&version=1
- Ramos, Arthur Freitas; Hulak, David Barros; de Queiroz, Ruy Jose Guerra Barretto. A Formal Counterexample to the Cost-Preserving Single-Source Unsplittable Flow Conjecture. 2026. Entry dated July 22, 2026. Isabelle/HOL formalization. \urlhttps://isa-afp.org/entries/Dinitz_Garg_Goemans_Counterexample.html
- Ramos, Arthur Freitas; Hulak, David Barros; de Queiroz, Ruy Jose Guerra Barretto. Lean formalization of the Dinitz–Garg–Goemans cost counterexample. 2026. Revision \nolinkurlcc7284cf415fc2a773f00d400319ef39663c277a. \urlhttps://github.com/Arthur742Ramos/dinitz-garg-goemans-counterexample-lean/tree/cc7284cf415fc2a773f00d400319ef39663c277a
- Rybin, Dmitry. Counterexample to Dinitz Conjecture. 2026. Source discovery transcript, including the complete finite certificate. \urlhttps://chatgpt.com/share/6a60b2eb-0b64-83ee-9c76-7931ca1de063
- Rybin, Dmitry. Counterexample to the Dinitz–Garg–Goemans cost conjecture. 2026. \urlhttps://x.com/DmitryRybin1/status/2079904005652893709
- The mathlib Community. The Lean mathematical library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, pp. 367–381. 2020. \urlhttps://doi.org/10.1145/3372885.3373824DOI
Show all 11 referencesShow fewer references
- Traub, Vera; Vargas Koch, Laura; Zenklusen, Rico. Single-source unsplittable flows in planar and bounded-genus graphs. 2026. Published July 22, 2026. Definition 1.1 and Conjecture 1.3. \urlhttps://doi.org/10.1007/s10107-026-02365-xDOI