Almost all 5-regular graphs have a 3-flow

Paweł Prałat, Nick Wormald

Research output: Contribution to journalArticleOtherpeer-review

Abstract

Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This is equivalent to every 5-regular 4-edge-connected graph having an edge orientation in which every out-degree is either 1 or 4. We show that this property holds asymptotically almost surely for random 5-regular graphs.

Original languageEnglish
Pages (from-to)89-94
Number of pages6
JournalTrends in Mathematics
Volume6
DOIs
Publication statusPublished - 2017

Cite this