Flows, view obstructions, and the lonely runner (Q1386416): Difference between revisions

It is shown that every undirected graph \(G\) for which a flow with at most \(k\) different positive values exists has also a flow with all values in the set \(\{1,2,\dots, k\}\). A flow is an orientation of the edges of \(G\) together with a vector of nonnegative values indexed by the edges such that for each node \(v\) the sum of the values of the edges entering \(v\) is the same as the sum of the values of the edges leaving \(v\). For \(k\geq 5\) the result is a trivial consequence of Seymour's ``six flow theorem.'' For \(k\leq 4\) the proof is based on a number-theoretic result of T. W. Cusick and C. Pomerance for which a short proof is given in this paper.