Flows, View Obstructions, and the Lonely Runner

We prove the following result: LetGbe an undirected graph. IfGhas a nowhere zero flow with at mostkdifferent values, then it also has one with values from the set {1, …, k}. Whenk⩾5, this is a trivial consequence of Seymourʹs “six-flow theorem”. Whenk⩽4 our proof is based on a lovely number theoretic problem which we call the “Lonely Runner Conjecture:” Supposekrunners having nonzero constant speeds run laps on a unit-length circular track. Then there is a time at which all runners are at least 1/(k+1) from their common starting point. This conjecture appears to have been formulated by J. Wills (Monatsch. Math.71, 1967) and independently by T. Cusick (Aequationes Math.9, 1973). This conjecture has been verified fork⩽4 by Cusick and Pomerance (J. Number Theory19, 1984) in a complicated argument involving exponential sums and electronic case checking. A major part of this paper is an elementary selfcontained proof of the casek=4 of the Lonely Runner Conjecture.