Minimum Degree and Nowhere-Zero $3$-Flows

Abstract

Let $G$ be a $2$-edge-connected simple graph on $n$ vertices, $n\ge 3$. It is known that if $G$ satisfies $d(x)\ge \frac{n}{2}$ for every vertex $x\in V(G)$, then $G$ has a nowhere-zero $3$-flow, with several exceptions.In this paper, we prove that, with ten exceptions, all graphs with at most two vertices of degree less than $\frac{n}{2}$ have nowhere-zero $3$-flows. More precisely, if $G$ is a $2$-edge-connected graph on $n$ vertices, $n\ge 3$, in which at most two vertices have degree less than $\frac{n}{2}$, then $G$
has a nowhere-zero $3$-flow if and only if $G$ is not one of ten completely described graphs.