## New answers tagged directed-graphs

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).
...

Top 50 recent answers are included

#### Related Tags

directed-graphs × 112graph-theory × 88

co.combinatorics × 37

reference-request × 11

spectral-graph-theory × 8

graph-colorings × 7

hamiltonian-paths × 7

terminology × 6

algorithms × 5

matrices × 4

random-graphs × 4

hamiltonian-graphs × 4

orientation × 4

linear-algebra × 3

lo.logic × 3

computational-complexity × 3

eigenvalues × 3

semigroups-and-monoids × 3

enumerative-combinatorics × 3

extremal-graph-theory × 3

adjacency-matrices × 3

at.algebraic-topology × 2

gr.group-theory × 2

ct.category-theory × 2

set-theory × 2