Setting, a random three regular graph. If I start removing edges, what's the probability that I disconnect it? What I know is that if I disconnect a graph I get a subgraph, and that the expected number of copies of a given subgraph goes like $n^{-1}$ where $n$ is number of vertices. Are there any references anyone knows to direct calculations about this question?


  • 2
    $\begingroup$ Those voting to close might perhaps like to give some indication of why they are doing so? $\endgroup$ – Gerry Myerson Mar 27 '14 at 23:50
  • 2
    $\begingroup$ @Gerry: I voted to close because I absolutely cannot understand the question. Certainly, if you remove enough edges from any graph, this will disconnect it - but how is this related to probability and 3-regularity? What does it mean "if I disconnect a graph, I get a subgraph"? What is the exact meaning of the sentence that follows? $\endgroup$ – Seva Mar 28 '14 at 7:15
  • $\begingroup$ Thanks, @Seva --- now at least the author has something to go on. $\endgroup$ – Gerry Myerson Mar 28 '14 at 9:57
  • $\begingroup$ Seva,I'm not sure what the issue is? Of course if you remove enough edges from essentially any graph you will disconnect it, but it is an interesting question to many people to ask, how many edges you have to remove before you are likely to disconnect it. It's obvious of course that if you have a $d$ regular graph, the larger $d$ is the more edges you can remove without disconnecting in general, but I'm asking of $d=3$ I have some ideas about how to maybe consider this, for example by looking at powers of the adjacency matrix, but thought it likely this had been looked at before $\endgroup$ – Jeff McGowan Mar 28 '14 at 19:22
  • $\begingroup$ Oh and as far as the subgraph goes, sorry, thought that was obvious. Suppose I have a connected graph, and I remove edges until it's disconnected. I now have two connected graphs, both of which are subgraphs of the original graph. $\endgroup$ – Jeff McGowan Mar 28 '14 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.