Skip to main content

New answers tagged

8 votes
Accepted

Are directed graphs with out-degree exactly 2 strongly connected with probability 1?

No. The probability that a given vertex doesn't have any incoming edge is $(1-\frac1n)^{2n}\to e^{-2}$, so the graph will not be strongly connected with probability at least $e^{-2}$ (asymptotically). ...
Corentin B's user avatar
  • 1,459

Top 50 recent answers are included