Nowhere-zero 3-flows and -connectivity in bipartite graphs

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. Let F 12 be a family of graphs such that G ∈ F 12 if and only if G is a simple bipartite graph on 12 vertices and δ ( G ) = 4 . Let G be a simple bipartite graph on n vertices. It is proved in this paper that if δ ( G ) ≥ ⌈ n 4 ⌉ + 1 , then G admits a nowhere-zero 3-flow with only one exceptional graph. Moreover, if G ∉ F 12 with the minimum degree at least ⌈ n 4 ⌉ + 1 is Z 3 -connected. The bound is best possible in the sense that the lower bound for the minimum degree cannot be decreased.