4-flow conjecture

Definitions and mathematical statement

Let $G$ be a finite undirected graph, allowing parallel edges. A bridge is an edge whose deletion increases the number of connected components. A nowhere-zero integer four-flow consists of an arbitrary orientation of the edges together with integer values $f(e)$ satisfying \[ 1\le |f(e)|\le3, \qquad \sum_{e\text{ leaving }v}f(e) -\sum_{e\text{ entering }v}f(e)=0 \quad(v\in V(G)). \] Negative values permit reversing an edge and changing its sign without changing feasibility. Loops, if present, contribute once to each sum and impose no difficulty. Conservation must hold as an equality of integers, not merely modulo four.

The Petersen graph has as its vertices the ten two-element subsets of $\{1,2,3,4,5\}$, with two vertices adjacent exactly when the corresponding subsets are disjoint. A Petersen minor in $G$ consists of ten disjoint nonempty connected branch sets, with the adjacencies of this graph represented by edges between the corresponding sets; extra adjacencies may be deleted.

The conjecture says that every bridgeless finite graph having no Petersen minor admits a nowhere-zero four-flow. The hypothesis excludes a minor rather than just a subgraph or subdivision. The graph need not be cubic or planar. If it is disconnected, the desired flow is assigned separately on each component. A bridge would force its own flow value to vanish, explaining why the bridgeless condition is necessary.

Short English statement

Does every bridgeless graph without a Petersen minor admit a nonzero integer flow using magnitudes at most three?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3215 (OPG-127), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, 4-flow conjecture. Original problem and discussion. http://www.openproblemgarden.org/op/4_flow_conjecture.