A python program to test whether a graph has a k-flow or not.

Let k > 1 be an integer, let G be a graph, let D be an orientation of G and let phi be a weight function that associates to each edge of G a positive integer in the set {1, 2, ..., k - 1}. The pair (D, phi) is a (nowhere-zero) k-flow of G if the sum of the weights of all edges leaving every vertex v of G equals the sum of the weights of all edges entering v, and we call v balanced. Similarly, we say the pair (D, phi) is a (nowhere-zero) modular-k-flow, if every vertex v is balanced modulus k.

Tutte [1] defined the concept of k-flows as a generalization of the concept of k-face-colourings after observing that, for any planar graph, a k-flow can be obtained from k-face-colouring and vice-versa. Tutte proposed three celebrated conjectures regarding k-flows of graphs, known as the 5-, 4- and 3-Flow Conjectures.

[1] W. T. Tutte. A contribution to the theory of chromatic polynomials. Can. J. Math., 6:80–91, 1954.

One may use kflow.py as a standalone library. Its main function (and actually the only one which should be called by the client-side) is has_k_flow which takes as its two mandatory arguments the number k representing which of the flows (3, 4, 5 should be used and a graph G represented by an adjacency list. The function returns a boolean value that is True if the graph admits a modular-k-flow. If there is a flow, it is accessible through kflow.answer, which is a list of possibles k-flows found; However, as a current limitation, if there is a modular-k-flow, kflow.answer will only have the first found k-flow.

The file go.py is an example of how to read a graph from input and use the k-flow library.

The thm.py library was developed exclusively for 4-flows. Its main function is the same as the kflow.py function; However, one should call thm.has_k_flow instead. It works by identifying set of edges in the graph that could be used as weight 2 edges, such that their removal yields an Eulerian graph. It is exponentially faster than the brute-force approach, but still not extremely fast.