% Copyright 2026 Arthur Freitas Ramos, David Barros Hulak, % and Ruy J. G. B. de Queiroz. Manuscript source licensed CC BY 4.0. \documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[a4paper,margin=27mm]{geometry} \usepackage{amsmath,amssymb,amsthm,booktabs,array} \usepackage{tikz} \usetikzlibrary{arrows.meta} \usepackage{microtype,xurl} \usepackage[hidelinks]{hyperref} \hypersetup{pdftitle={A Lean Certificate for the Single Source Unsplittable Flow Cost Counterexample},pdfauthor={Arthur Freitas Ramos; David Barros Hulak; Ruy J. G. B. de Queiroz},pdfsubject={Exposition of a finite source-based counterexample certificate},pdfkeywords={unsplittable flow, Goemans cost conjecture, Rybin counterexample, Lean 4, Mathlib}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newcommand{\Q}{\mathbb Q} \newcommand{\decl}[1]{\nolinkurl{#1}} \newcommand{\source}[2]{\href{https://github.com/Arthur742Ramos/dinitz-garg-goemans-counterexample-lean/blob/cc7284cf415fc2a773f00d400319ef39663c277a/#1}{#2}} \newcommand{\Pth}{\mathcal P} \title[Unsplittable flow cost certificate in Lean]{A Lean Certificate for the Single Source Unsplittable Flow Cost Counterexample} \author{Arthur Freitas Ramos} \author{David Barros Hulak} \author{Ruy J. G. B. de Queiroz} \thanks{Author ORCID identifiers: Arthur Freitas Ramos, \href{https://orcid.org/0009-0003-3568-0325}{0009-0003-3568-0325}; David Barros Hulak, \href{https://orcid.org/0009-0002-8056-1774}{0009-0002-8056-1774}; Ruy J. G. B. de Queiroz, \href{https://orcid.org/0000-0003-1482-0977}{0000-0003-1482-0977}.} \thanks{Copyright 2026 the authors. Licensed under \href{https://creativecommons.org/licenses/by/4.0/}{Creative Commons Attribution 4.0 International (CC BY 4.0)}.} \date{October 1, 2026} \subjclass[2020]{68R10, 90C27, 03B35} \keywords{Single-source unsplittable flow, cost-preserving rounding, finite counterexample, Lean 4, Mathlib, formal verification} \begin{document} \begin{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. \end{abstract} \maketitle \raggedbottom \section{The cost question and the certified result} In single-source unsplittable flow, a terminal's entire demand must be sent along one path from a common source. Dinitz, Garg, and Goemans established a rounding theorem with additive congestion bounded by the largest demand \cite{DGG1999}. The cost-enhanced conjecture attributed to Goemans additionally asks that the rounded flow cost no more than the given fractional flow. We use the explicit formulation in Traub, Vargas Koch, and Zenklusen, Conjecture~1.3 \cite{TVZ2026}. The 1999 paper is background for the congestion theorem; it is not used here as a source for the wording of the cost conjecture. For the positive-demand subcase sufficient here, take a finite directed graph $G=(V,A)$, source $s$, distinct terminals $t_k$ different from $s$, positive demands $d_k$, a feasible nonnegative fractional flow $x$, and nonnegative per-unit arc costs $c_a$, put $D=\max_k d_k$. The existential cost-preserving assertion is that paths $P_k$ from $s$ to $t_k$ can be selected so that, for every arc, \begin{equation}\label{eq:weak} y_a:=\sum_{k:a\in P_k}d_k\ \le\ x_a+D, \qquad \sum_{a\in A}c_ay_a\ \le\ \sum_{a\in A}c_ax_a. \end{equation} Conjecture~1.3 also asserts polynomial-time computation. Refuting its existential part suffices to refute that stronger claim, without formalizing a computational model. The cited formulation permits zero demands; our witness satisfies the stricter positivity condition of the Lean interface. A strict variant replaces the first inequality by $y_a=Stealth,vertex/.style={circle,draw,inner sep=3pt},scale=0.95] \node[vertex] (s) at (0,0) {$s$}; \node[vertex] (u) at (2.2,0) {$u$}; \node[vertex] (v) at (4.4,0) {$v$}; \node[vertex] (w) at (6.6,0) {$w$}; \node[vertex] (t1) at (4.4,1.7) {$t_1$}; \node[vertex] (t2) at (6.6,2.4) {$t_2$}; \node[vertex] (t3) at (6.6,-1.7) {$t_3$}; \draw[->] (s)--(u); \draw[->] (u)--(v); \draw[->] (v)--(w); \draw[->] (v)--(t1); \draw[->] (w)--(t2); \draw[->] (w)--(t3); \draw[->] (s) to[out=55,in=180] (t1); \draw[->] (s) to[out=90,in=160] (t2); \draw[->] (u) to[out=-45,in=180] (t3); \end{tikzpicture} \caption{The seven vertices and nine arcs. Numerical labels are in Table~\ref{tab:arcs}; the drawing asserts only the endpoint relation.} \label{fig:graph} \end{figure} For each terminal there is one paid route $E_k$ and one free route $Z_k$: \begin{align*} E_1&=(s,t_1),& Z_1&=(s,u,v,t_1),\\ E_2&=(s,t_2),& Z_2&=(s,u,v,w,t_2),\\ E_3&=(s,u,t_3),& Z_3&=(s,u,v,w,t_3). \end{align*} Here vertex lists abbreviate the consecutive directed arcs. The names paid and free refer to total route cost, not to disjointness: $E_3$ and $Z_3$ both use $s\to u$. \begin{lemma}\label{lem:paths} Every directed source-to-$t_k$ path is exactly $E_k$ or $Z_k$. \end{lemma} \begin{proof} From $w$ a nonempty path goes directly to $t_2$ or $t_3$ and then stops. From $v$ it goes to $t_1$ or to $w$; from $u$ it goes to $t_3$ or to $v$; from $s$ it goes to $t_1$, $t_2$, or $u$. Following these alternatives gives precisely the six displayed terminal paths. There are no additional continuations from any terminal. \end{proof} The formal predicate \decl{edgePath} is recursive on a list of arcs. It checks each tail against the current vertex, advances to the head, and accepts the empty list exactly when the current and final vertices agree. It does not assume vertex simplicity. The proof classifies all such lists from each terminal, then from $w,v,u,s$, and obtains \decl{allSourceTerminalPaths}. Thus no longer walk, omitted splice, or additional source-to-terminal route escapes the two-choice model. The fractional route amounts are \[ \begin{array}{c|rr|r} k&f_{k,E_k}&f_{k,Z_k}&d_k\\\hline 1&10&5&15\\ 2&6&4&10\\ 3&10&5&15 \end{array} \] They are all nonnegative and meet the three demands. Summing their incidences gives Table~\ref{tab:arcs}, proving feasibility and saturation. For example the backbone loads are $5+4+10+5=24$ on $s\to u$, $5+4+5=14$ on $u\to v$, and $4+5=9$ on $v\to w$. As an arc-flow check, the source outflow is $10+6+24=40$; conservation at $u,v,w$ is respectively $24=14+10$, $14=5+9$, and $9=4+5$. The terminal inflows are $15,10,15$. Only three arcs have positive cost, so \begin{equation}\label{eq:58} C(f)=2\cdot10+3\cdot6+2\cdot10=58, \qquad D=\max\{15,10,15\}=15. \end{equation} The corresponding Lean facts are \decl{fractionalLoadEqCapacity}, \decl{splitFlowFeasible}, \decl{fractionalCostValue}, and \decl{counterexampleMaximumDemand}. \section{The obstruction to cost preserving rounding} Let $z_k$ be $1$ if $q$ selects $Z_k$, and $0$ if it selects $E_k$. Every paid route contributes $30$: its cost is respectively $15\cdot2$, $10\cdot3$, or $15\cdot2$. Every free route contributes zero. Hence \begin{equation}\label{eq:costcount} C(q)=30\bigl(3-z_1-z_2-z_3\bigr). \end{equation} The crucial shared-arc loads are \begin{equation}\label{eq:backbone} y_{su}=15z_1+10z_2+15,\quad y_{uv}=15z_1+10z_2+15z_3,\quad y_{vw}=10z_2+15z_3. \end{equation} The constant $15$ in $y_{su}$ comes from terminal $t_3$ on either route. \begin{lemma}\label{lem:two} If $y_a(q)\le x_a+15$ on every arc, then at most one free route is selected, and at least two paid routes are selected. \end{lemma} \begin{proof} If $Z_1,Z_2$ are selected, then $y_{su}=40>24+15=39$. If $Z_1,Z_3$ are selected, then $y_{uv}\ge30>14+15=29$. If $Z_2,Z_3$ are selected, then $y_{vw}=25>9+15=24$. Any selection of at least two free routes contains one of these pairs, so it violates a congestion inequality. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] The preceding fractional witness is feasible and has cost $58$. By Lemma~\ref{lem:paths}, every unsplittable graph routing is represented by the three binary choices. Lemma~\ref{lem:two} and \eqref{eq:costcount} give $C(q)\ge60>58$ for any weakly bounded routing. Thus no routing can satisfy both inequalities in \eqref{eq:weak}. A strict congestion bound implies the weak bound, so the strict cost-preserving assertion fails as well. \end{proof} Table~\ref{tab:routings} is an exhaustive numerical cross-check. Its excess column means $\max_a(y_a-x_a)$, so weak congestion feasibility is exactly excess at most $15$. All four feasible assignments actually have excess strictly below $15$. This also shows that the obstruction is the cost requirement, rather than a lack of any bounded routing. \begin{table}[ht] \centering \caption{All eight routing assignments, computed from the arc incidences.} \label{tab:routings} \renewcommand{\arraystretch}{1.13} \begin{tabular}{cccrrc} \toprule $t_1$&$t_2$&$t_3$&Cost&Maximum excess&Bound $\le15$\\ \midrule $E_1$&$E_2$&$E_3$&90&5&Yes\\ $E_1$&$E_2$&$Z_3$&60&10&Yes\\ $E_1$&$Z_2$&$E_3$&60&6&Yes\\ $E_1$&$Z_2$&$Z_3$&30&16&No\\ $Z_1$&$E_2$&$E_3$&60&10&Yes\\ $Z_1$&$E_2$&$Z_3$&30&16&No\\ $Z_1$&$Z_2$&$E_3$&30&16&No\\ $Z_1$&$Z_2$&$Z_3$&0&26&No\\ \bottomrule \end{tabular} \end{table} For example $(E_1,E_2,Z_3)$ has loads, in the arc order of Table~\ref{tab:arcs}, \[ (15,10,15,15,0,0,15,0,15). \] Every load is strictly below $x_a+15$, and its cost is $60$. Thus $60$ is the exact minimum under either congestion reading. This attainment check and the full table are elementary consequences of the displayed data; the pinned selected Lean result asserts the lower bound, not a separately packaged optimum-attainment theorem. The all-free routing has cost zero and maximum excess $26$, illustrating that cost alone is also satisfiable. The example makes no claim against rounding guarantees allowing larger additive error, such as $2D$. \section{The Lean proof and its verification boundary} The development uses Lean~4 \cite{Lean4} and Mathlib \cite{Mathlib2020}. The graph, route lists, rational amounts, loads, and predicates are in \source{DinitzGargGoemans/Definitions.lean}{Definitions.lean}. The substantive proofs are in \source{DinitzGargGoemans/Proof.lean}{Proof.lean}. Finite carrier instances explicitly list the three commodities, two route choices, and nine arcs. This permits finite sums to simplify to exact rational expressions. Path completeness is proved structurally, not stipulated by making all binary choices admissible. In the concrete instance both choices are declared admissible, but \decl{routeEdgesValid} proves their graph validity and \decl{allSourceTerminalPaths} proves completeness for arbitrary arc lists. This separation is essential: an incidence-table counterexample would otherwise leave open whether the real graph admits an unlisted cheap routing. The arithmetic proof first identifies the finite universes. It uses \decl{simp} and \decl{norm_num} for well-formedness, demand sums, capacity saturation, maximum demand, and fractional cost. The three backbone-load formulas and \decl{unsplittableCostEqPaidCount} are proved by cases on the three route choices. In \decl{boundedRoutingHasTwoPaid}, the hypotheses for $s\to u,u\to v,v\to w$ are extracted; each of the eight cases reduces to rational arithmetic, and \decl{linarith} closes the impossible ones. Coercing the paid-count bound to $\Q$ yields \decl{boundedUnsplittableCost}. The remaining witness and universal negations instantiate the property at the concrete instance and combine $60\le C(q)\le58$. The statement surface \source{Challenge.lean}{Challenge.lean} repeats the definitions and states seven targets with deliberate \decl{sorry} bodies. It is an interface for statement comparison, not the completed proof. \source{Solution.lean}{Solution.lean} imports \decl{DinitzGargGoemans.Proof}, whose import chain goes through Definitions rather than Challenge. The inspected implementation files contain no \decl{sorry}, \decl{admit}, \decl{native_decide}, or custom axiom declaration. A textual inspection by itself does not establish the transitive axiom footprint. The pinned comparator configuration selects the seven theorems named in the registry and ten load, cost, feasibility, rounding, and witness definitions. It permits only \decl{propext}, \decl{Quot.sound}, and \decl{Classical.choice}, and enables NanoDa checking. The registry records successful historical mechanical verification on August~28, 2026, under Lean \decl{v4.33.0}; the Mathlib manifest resolves to \nolinkurl{db584cd6d46c92f209a44c0f1c829460d327499d}. Its linked workflow is \href{https://github.com/PalomarRegistry/PalomarSubmission/actions/runs/33131019615}{run 33131019615} \cite{Palomar2026}. These are historical verification records, not a new kernel or comparator run performed during manuscript preparation. The boundary of the formal result is therefore explicit. It is a finite rational counterexample with exhaustive graph-path coverage and exact cost separation. Interpretation as an ordinary real-valued graph-flow counterexample uses the same integer incidence and arithmetic, and does not require choosing any irrational route amounts: the routing domain is still the same eight assignments. Source alignment, the conjecture's historical attribution, and prose claims about other work are scholarly judgments outside the Lean kernel. The development does not formalize the general Dinitz--Garg--Goemans theorem, algorithmic complexity, parameterized counterexample families, or every published variant of the cost conjecture. \section{Provenance and reproducibility} This manuscript is a new exposition of the pinned Lean certificate. The counterexample is credited to Rybin and the GPT-5.6 Pro session he published; the prior AFP proof document remains a separate Isabelle artifact \cite{RybinSession,AFP2026}. No prior proof-document text or figure is reproduced here. The data tables and diagram were prepared from the inspected Lean definitions, with an independent exact-arithmetic enumeration used as a numerical cross-check. A matching enumeration is not a substitute for formal theorem verification. The repository metadata records GPT-5 agent assistance for the historical Lean proof engineering. The present manuscript was generated primarily with OpenAI GPT-6.1 assistance for exposition, source comparison, bibliographic research, and typesetting. Arthur Freitas Ramos directed the submission and reports understanding some parts of the manuscript. No comprehensive personal line-by-line review by Arthur, or complete understanding by every listed author, is claimed. Model-assisted manuscript checks should not be read as independent human peer review. The referenced Lean repository is licensed Apache~2.0, and the AFP entry has a BSD license. Those artifact licenses remain distinct from this manuscript's CC BY~4.0 license. The source archive for this article contains only its \LaTeX{} source and bibliography; it does not bundle the Lean project or the prior Isabelle document. The immutable source and registry references identify the formal artifact needed to inspect or independently reproduce the mathematical verification. \bibliographystyle{amsplain} \bibliography{references} \end{document}