On Star Decompositions of Random Regular Graphs

Barát 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 counterexample to this conjecture. Using the small subgraph conditioning method of Robinson and Wormald, we prove that a random 4-regular graph has an S3-decomposition asymptotically almost surely, provided that the number of vertices is divisible by 3.