Almost all 5‐regular graphs have a 3‐flow. Issue 2 (1st July 2019) - Prałat, Paweł; Wormald, Nick
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.