If you take a random $k$-regular graph, with high probability (tending to 1 as the size of the graph grows) almost all of the nodes will be in one giant connected component. How well connected is this component? How many edges will I have to remove in order to disconnect this graph?
This is motivated by an application where I generate a random connected $k$-regular graphs and then remove $r$ many random spanning trees. The concern: how large can $r$ be (on average) for a $k$-regular graph on $n$ vertices?