Nowhere-zero $k$-flows of Supergraphs

Abstract

Let $G$ be a 2-edge-connected graph with $o$ vertices of odd degree. It is well-known that one should (and can) add $o \over 2$ edges to $G$ in order to obtain a graph which admits a nowhere-zero 2-flow. We prove that one can add to $G$ a set of $\le \lfloor{o \over 4}\rfloor$, $\lceil{1 \over 2}\lfloor{o \over 5}\rfloor\rceil$, and $\lceil{1 \over 2}\lfloor{o \over 7}\rfloor\rceil$ edges such that the resulting graph admits a nowhere-zero 3-flow, 4-flow, and 5-flow, respectively.