Let G = be a digraph and letM be an abelian group. A map φ: E → M is an M-circulation if for every vertexv ∈ V where δ+ denotes the set of edges out of v and δ− denotes the set of edges into v. Sometimes, this condition is referred to as Kirchhoff's law. If φ ≠ 0 for every e ∈ E, we call φ a nowhere-zero flow, an M-flow, or an NZ-flow. If k is an integer and 0 < |φ| < k then φ is a k-flow.
Other notions
Let G = be an undirected graph. An orientation of E is a modulark-flow if for every vertex v ∈ V we have:
Properties
The set of M-flows does not necessarily form a group as the sum of two flows on one edge may add to 0.
A graph G has an M-flow if and only if it has a |M|-flow. As a consequence, a flow exists if and only if a k-flow exists. As a consequence G admits a k-flow then it admits an h-flow where.
Orientation independence. Modify a nowhere-zero flow φ on a graph G by choosing an edge e, reversing it, and then replacingφ with −φ. After this adjustment, φ is still a nowhere-zero flow. Furthermore, if φ was originally a k-flow, then the resulting φ is also a k-flow. Thus, the existence of a nowhere-zero M-flow or a nowhere-zero k-flow is independent of the orientation of the graph. Thus, an undirected graph G is said to have a nowhere-zero M-flow or nowhere-zero k-flow if some orientation of G has such a flow.
Let be the number of M-flows on G. It satisfies the deletion–contraction formula: Combining this with induction we can show is a polynomial in where is the order of the group M. We call the flow polynomial of G and abelian group M. The above implies that two groups of equal order have an equal number of NZ flows. The order is the only group parameter that matters, not the structure of M. In particular if The above results were proved by Tutte in 1953 when he was studying the Tutte polynomial, a generalization of the flow polynomial.
There is a duality between k-face colorings and k-flows for bridgeless planar graphs. To see this, let G be a directed bridgeless planar graph with a proper k-face-coloring with colors Construct a map by the following rule: if the edge e has a face of colorx to the left and a face of color y to the right, then let φ = x – y. Then φ is a k-flow since x and y must be different colors. So if G and G* are planar dual graphs and G* is k-colorable, then G has a NZ k-flow. Using induction on |E| Tutte proved the converse is also true. This can be expressed concisely as: where the RHS is the flow number, the smallest k for which G permits a k-flow.
General Graphs
The duality is true for general M-flows as well:
Let the be face-coloring function with values in M.
Define where r1 is the face to the left of e and r2 is to the right.
For every M-circulation there is a coloring function c such that .
c is a |E|-face-coloring if and only if is a NZ M-flow.
The duality follows by combining the last two points. We can specialize to to obtain the similar results for k-flows discussed above. Given this duality between NZ flows and colorings, and since we can define NZ flows for arbitrary graphs, we can use this to extend face-colorings to non-planar graphs.
Applications
G is 2-face-colorable if and only if every vertex has even degree.
Let be the Klein-4 group. Then a cubic graph has a K-flow if and only if it is 3-edge-colorable. As a corollary a cubic graph that is 3-edge colorable is 4-face colorable.
A graph is 4-face colorable if and only if it permits a NZ 4-flow. The Petersen graph does not have a NZ 4-flow, and this led to the 4-flow conjecture.
If G is a triangulation then G is 3- colorable if and only if every vertex has even degree. By the first bullet, the dual graphG* is 2-colorable and thus bipartite and planar cubic. So G* has a NZ 3-flow and is thus 3-face colorable, making G 3-vertex colorable.
Just as no graph with a loop edge has a proper vertex coloring, no graph with a bridge can have a NZ M-flow for any group M. Conversely, every bridgeless graph has a NZ -flow.
Existence of ''k''-flows
Interesting questions arise when trying to find nowhere-zero k-flows for small values of k. The following have been proven:
4-flow and 5-flow conjectures
As of 2019, the following are currently unsolved : The converse of the 4-flow Conjecture does not hold since the complete graphK11 contains a Petersen graph and a 4-flow. For bridgeless cubic graphs with no Petersen minor, 4-flows exist by the snark theorem. The four color theorem is equivalent to the statement that no snark is planar.
