Graphic additive bases and graph flows

Abstract

The lattice-coset method of Alon, Buci\'c, and Davies gives real solutions with controlled coordinates. We combine it with integer rounding to prescribe outdegrees and flows from spanning-tree packing. For every integer $q\ge3$, $q$ edge-disjoint spanning trees suffice for every outdegree prescription modulo $q$ whose sum is compatible with the number of edges. The tree count is optimal even for simple graphs. A common interval theorem extends the argument to totally unimodular matrices; for graphs, its partition inequalities admit a sharp allowance of two. Fractional packing characterizes when every prescription has a strongly connected realization and gives circular-flow bounds. In particular, for every integer $k\ge1$, every $(4k+2)$-edge-connected graph has circular flow number strictly below $2+1/k$, with optimal connectivity for this strict inequality. As a structural application, every four-edge-connected graph with no bond of size six, seven or eight has a nowhere-zero three-flow. Further consequences concern star decompositions, antisymmetric flows and contraction.