Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Just a short side note: A random $k$-regular graph will be not only very well connected, but remarkably will have the best connectivity possible. Random $k$-regular graphs with high probability are more "well connected" than any known constructions, and are as well connected as possible. This is a very deep theorem in Spectral Graph Theory. It is the Alon Conjecture which was resolved by Joel Friedmann in 2003. The proof is about 110 pages. If you like I could be more precise and elaborate on the above. – Eric Naslund Sep 18 '11 at 16:11
@Eric since random $k$-regular graphs are good expanders, it makes sense that they are VERY WELL connected. But I was wondering if there was a general bound or expression for the average $r$ in terms of $k$ and $n$. I could expand my question to clarify this. I would definitely like an explanation of "as well connected as possible" that doesn't require me to read a 110 page paper ;). – Artem Kaznatcheev Sep 18 '11 at 16:17
I take it we're assuming $k$ is at least $3$? – Chris Eagle Sep 18 '11 at 18:58
@ChrisEagle yeah, definitely. I will wait a bit longer to see if there is any other confusion about my question and then edit the remarks in, and maybe some random thoughts related to expander graphs (although I am interested in the question as stated, not the Cheeger constant). – Artem Kaznatcheev Sep 18 '11 at 19:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.