Tutte's 3-flow conjecture and short cycle covers (Q757422): Difference between revisions

In this paper we prove: (i) If a graph \(G\) has a nowhere-zero 6-flow \(\phi\) such that \(| E_{odd}(\phi)| \geq \frac{2}{3}| E(G)|,\) then G has a cycle cover in which the sum of the lengths of the cycles in the cycle cover is at most \(\frac{44}{27}| E(G)|\), where \(E_{odd}(\phi)=\{e\in E(G): \phi(e)\) is odd\}; (ii) if Tutte's 3-flow Conjecture is true, then every bridgeless graph \(G\) has a nowhere-zero 6-flow \(\phi\) such that \(| E_{odd}(\phi)| \geq \frac{2}{3}| E(G)|\).