Random 4-regular graphs have 3-star decompositions asymptotically almost surely

Abstract Barat and Thomassen conjectured in 2006 that the edges of every planar 4-regular 4-edge-connected graph can be decomposed into copies of the star with 3 leaves. Shortly afterward, Lai constructed a counterexampleto this conjecture. Using the small subgraph conditioning method of Robinson and Wormald, we prove that a random 4- regular graphhas an S 3 -decomposition asymptotically almost surely, provided the number of vertices is divisible by 3.