TOPICS
Search

Nowhere-Zero Flow


A nowhere-zero k-flow on a graph G consists of a graph orientation of its edges and an integer value f(e) assigned to each graph edge such that 0<|f(e)|<k and the sum of the values on edges directed into each graph vertex equals the sum on edges directed out of it (Tutte 1954). Existence of such a flow is independent of the chosen graph orientation.

For positive integer u, the number of nowhere-zero u-flows on a graph is given by its flow polynomial.

For a bidirected graph, conservation uses the independent graph orientation at each end of a graph edge. A bidirected graph is flow-admissible if it has a nowhere-zero flow over the integers. Every bidirected graph that is flow-admissible and Eulerian has a nowhere-zero 4-flow. Chen and Fan (2026) strengthen this by showing that the edges on which the flow has magnitude 3 can all be confined to a single circle that is either unbalanced or has at least three edges.


See also

Bidirected Graph, Flow Polynomial, Tutte 4-Flow Conjecture

Explore with Wolfram|Alpha

References

Chen, J. and Fan, G. "Integral Flows on Bidirected Eulerian Graphs." Electron. J. Combin. 33, P3.79, 2026. https://doi.org/10.37236/14075.Tutte, W. T. "A Contribution to the Theory of Chromatic Polynomials." Canad. J. Math. 6, 80-91, 1954. https://doi.org/10.4153/CJM-1954-010-9.

Cite this as:

Weisstein, Eric W. "Nowhere-Zero Flow." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Nowhere-ZeroFlow.html

Subject classifications