Ore Condition and Nowhere-Zero 3-Flows
Genghua Fan, Chuixiang Zhou · SIAM Journal on Discrete Mathematics · 2008
Let G be a simple graph on n vertices, $n\geq 3$. It is well known that if G satisfies the Ore condition that $d(x)+d(y)\geq n$ for every pair of nonadjacent vertices x and y, then G has a Hamiltonian circuit, which implies that G has a nowhere-zero 4-flow. But it is not necessary for G to have a nowhere-zero 3-flow. In this paper, we prove that with six exceptions, all graphs satisfying the Ore condition have a nowhere-zero 3-flow. More precisely, if G is a graph on n vertices, $n\geq 3$, in which $d(x)+d(y)\geq n$ for every pair of nonadjacent vertices x and y, then G has no nowhere-zero 3-flow if and only if G is one of six completely described graphs.