Simple vs non-simple loops on random regular graphs

Benjamin Dozier, Jenya Sapir

In this note we solve the ``birthday problem'' for loops on random regular graphs. Namely, for fixed $d\ge 3$, we prove that on a random $d$-regular graph with $n$ vertices, as $n$…