Tutte’s \(3\)-flow Conjecture and Matchings in Bipartite Graphs

Abstract

Tutte’s \(3\)-flow conjecture is equivalent to the assertion that there exists an orientation of the edges of a \(4\)-edge-connected, \(5\)-regular graph \(G\)for which the out-flow at each vertex is \(+3\) or \(-3\). The existence of one such orientation of the edges implies the existence of an equipartition of the vertices of \(G\) that separates the two possible types of vertices. Such an equipartition is called mod \(3\)-orientable. We give necessary and sufficient conditions for the existence of mod \(3\)-orientable equipartitions in general \(5\)-regular graphs, in terms of:(i) a perfect matching of a bipartite graph derived from the equipartition;(ii) the sizes of cuts in \(G\).Also, we give a polynomial-time algorithm for testing whether an equipartition of a \(5\)-regular graph is mod \(3\)-orientable.