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.