Id: palomar/PALOMAR-2026-11-20-000001 Url: https://github.com/RBarish-UTokyo/PlanarMaxFlow-WordRAM-Lean4/tree/cfeb331b18ac14bccc38ef44ca640f0dff3f8c0a Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-20-000001-v1.json Repo: https://github.com/RBarish-UTokyo/PlanarMaxFlow-WordRAM-Lean4 Tags: math.CO, cs.DS, msc:05C10, msc:05C21, msc:05C38, msc:05C70, msc:05C85, msc:68Q25, msc:68W40, msc:90C35 Score: 0 Title: Flows and shortest paths in plane graphs, with machine programs including the maximum-flow algorithm of Borradaile, Klein, Mozes, Nussbaum and Wulff-Nilsen, in Lean 4 Trust: high Domain: math.CO Source: palomar Authors: Robert D. Barish Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-20 Formalized: true Formalizes: title=Maximal flow through a network identifier= relationship=formalizes Formalizes: title=Flow in planar graphs with multiple sources and sinks identifier= relationship=formalizes Formalizes: title=A note on two problems in connexion with graphs identifier= relationship=formalizes Formalizes: title=Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time identifier= relationship=formalizes Formalizes: title=Two theorems in graph theory identifier= relationship=adapts Page: https://delphi.science/r/palomar/PALOMAR-2026-11-20-000001 A Lean 4 and Mathlib formalization of maximum flows and shortest paths. Plane graphs are combinatorial maps (darts with a reversal, a tail vertex, a face and a next dart along the face boundary) whose graph and dual are connected and which satisfy Euler's formula V + F = D/2 + 2. The machine statements are about one explicit word RAM (unit cost per instruction, natural registers and memory cells bounded by a word bound W along the run) and fixed encodings of the inputs as lists of natural numbers; each asserts one fixed program for all inputs. Six theorems are compared: (1) the max-flow…