Almost all 5-regular graphs have a 3-flow

Paweł Prałat, Nick Wormald

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.

Original languageEnglish
Pages (from-to)147-156
Number of pages10
JournalJournal of Graph Theory
Volume93
Issue number2
DOIs
Publication statusPublished - 1 Feb 2020

Keywords

  • 3-flow
  • random graphs
  • small subgraph conditioning method

Cite this