| Abstract: | We develop four constructions for nowhere-zero 5-flows of 3-regular graphs that satisfy special structural conditions. Using these constructions we show a minimal counter-example to Tutte's 5-Flow Conjecture is of order ≥44 and therefore every bridgeless graph of nonorientable genus ≤5 has a nowhere-zero 5-flow. One of the structural properties is formulated in terms of the structure of the multigraph G(F) obtained from a given 3-regular graph G by contracting the cycles of a 2-factor F in G. © 1996 John Wiley & Sons, Inc. |
