Almost all 5-regular graphs have a 3-flow |
| |
Authors: | Paweł Prałat Nick Wormald |
| |
Institution: | 1. Department of Mathematics, Ryerson University, Toronto, Ontario, Canada;2. School of Mathematical Sciences, Monash University, Clayton, Victoria, Australia |
| |
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. |
| |
Keywords: | 3-flow random graphs small subgraph conditioning method |
|
|