Nowhere-zero flow

Last updated May 11, 2024

In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs.

Definitions

Let G = (V,E) be a digraph and let M be an abelian group. A map φ: E → M is an M-circulation if for every vertex v ∈ V

\sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),

where δ⁺(v) denotes the set of edges out of v and δ⁻(v) denotes the set of edges into v. Sometimes, this condition is referred to as Kirchhoff's law.

If φ(e) ≠ 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 < |φ(e)| < k then φ is a k-flow.^[1]

Other notions

Let G = (V,E) be an undirected graph. An orientation of E is a modulark-flow if for every vertex v ∈ V we have:

|\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.

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.

(Tutte 1950) A graph G has an M-flow if and only if it has a |M|-flow. As a consequence, a $\mathbb {Z} _{k}$ flow exists if and only if a k-flow exists.^[1] As a consequence if G admits a k-flow then it admits an h-flow where $h\geq k$ .

Orientation independence. Modify a nowhere-zero flow φ on a graph G by choosing an edge e, reversing it, and then replacing φ(e) with −φ(e). 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 (and thus every) orientation of G has such a flow.

Flow polynomial

Let $N_{M}(G)$ be the number of M-flows on G. It satisfies the deletion–contraction formula:^[1]

N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).

Combining this with induction we can show $N_{M}(G)$ is a polynomial in $|M|-1$ where $|M|$ is the order of the group M. We call $N_{M}(G)$ 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 $N_{M_{1}}(G)=N_{M_{2}}(G)$ if $|M_{1}|=|M_{2}|.$

The above results were proved by Tutte in 1953 when he was studying the Tutte polynomial, a generalization of the flow polynomial.^[2]

Flow-coloring duality

Bridgeless Planar Graphs

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 $\{0,1,\ldots ,k-1\}.$ Construct a map

\phi :E(G)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}

by the following rule: if the edge e has a face of color x to the left and a face of color y to the right, then let φ(e) = x – y. Then φ is a (NZ) k-flow since x and y must be different colors.

So if G and G* are planar dual graphs and G* is k-colorable (there is a coloring of the faces of G), then G has a NZ k-flow. Using induction on |E(G)| Tutte proved the converse is also true. This can be expressed concisely as:^[1]

\chi (G^{*})=\phi (G),

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 $c$ be the face-coloring function with values in M.

Define $\phi _{c}(e)=c(r_{1})-c(r_{2})$ where r₁ is the face to the left of e and r₂ is to the right.

For every M-circulation $\phi$ there is a coloring function c such that $\phi =\phi _{c}$ (proven by induction).

c is a |E(G)|-face-coloring if and only if $\phi _{c}$ is a NZ M-flow (straightforward).

The duality follows by combining the last two points. We can specialize to $M=\mathbb {Z} _{k}$ 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 (not just planar), we can use this to extend face-colorings to non-planar graphs.^[1]

Applications

G is 2-face-colorable if and only if every vertex has even degree (consider NZ 2-flows).^[1]

Let $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ 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.^[1]

A graph is 4-face colorable if and only if it permits a NZ 4-flow (see Four color theorem). The Petersen graph does not have a NZ 4-flow, and this led to the 4-flow conjecture (see below).

If G is a triangulation then G is 3-(vertex) colorable if and only if every vertex has even degree. By the first bullet, the dual graph G* 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.^[1]

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 $\mathbb {Z}$ -flow (a form of Robbins' theorem).^[3]

Existence of k-flows

Unsolved problem in mathematics:

Does every bridgeless graph have a nowhere zero 5-flow? Does every bridgeless graph that does not have the Petersen graph as a minor have a nowhere zero 4-flow?

(more unsolved problems in mathematics)

Interesting questions arise when trying to find nowhere-zero k-flows for small values of k. The following have been proven:

Jaeger's 4-flow Theorem. Every 4-edge-connected graph has a 4-flow.^[4]

Seymour's 6-flow Theorem. Every bridgeless graph has a 6-flow.^[5]

3-flow, 4-flow and 5-flow conjectures

As of 2019, the following are currently unsolved (due to Tutte):

3-flow Conjecture. Every 4-edge-connected graph has a nowhere-zero 3-flow.^[6]

4-flow Conjecture. Every bridgeless graph that does not have the Petersen graph as a minor has a nowhere-zero 4-flow.^[7]

5-flow Conjecture. Every bridgeless graph has a nowhere-zero 5-flow.^[8]

The converse of the 4-flow Conjecture does not hold since the complete graph K₁₁ contains a Petersen graph and a 4-flow.^[1] For bridgeless cubic graphs with no Petersen minor, 4-flows exist by the snark theorem (Seymour, et al 1998, not yet published). The four color theorem is equivalent to the statement that no snark is planar.^[1]

Related Research Articles

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an undirected graph $H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges, vertices and by contracting edges.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.

<span class="mw-page-title-main">Paul Seymour (mathematician)</span> British mathematician

Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory, the Hadwiger number of an undirected graph $G$ is the size of the largest complete graph that can be obtained by contracting edges of $G$ . Equivalently, the Hadwiger number $h (G)$ is the largest number $n$ for which the complete graph $K n$ is a minor of $G$ , a smaller graph obtained from $G$ by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of $G$ or the homomorphism degree of $G$ . It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of $G$ .

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph $and contains information about how the graph is connected. It is denoted by .$

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.

<span class="mw-page-title-main">Petersen's theorem</span>

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.

References

1 2 3 4 5 6 7 8 9 10 Diestel, Reinhard (30 June 2017). Graph theory. ISBN 9783662536216. OCLC 1048203362.
↑ Tutte, W. T. (1954). "A contribution to the theory of chromatic polynomials". Canadian Journal of Mathematics. 6: 80–91. doi:10.4153/CJM-1954-010-9.
↑ For a stronger result on the enumeration of $\mathbb {Z}$ -flows with a bound on the maximum flow amount per edge, again using Robbins' theorem on totally cyclic orientations, see Theorem 2 of Kochol, Martin (2002), "Polynomials associated with nowhere-zero flows", Journal of Combinatorial Theory, Series B, 84 (2): 260–269, doi: 10.1006/jctb.2001.2081 , MR 1889258
↑ F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205–216.
↑ P. D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130–135.
↑ , Open Problem Garden.
↑ , Open Problem Garden.
↑ , Open Problem Garden.