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

Question

Consider a directed graph with out-degree exactly two with $n$ vertices $v_1, v_2 \cdots v_n$ that is constructed as follows: For each vertex $v_i$, one chooses uniformly at random two (not necessarily distinct) $i$ and $j$ from $\{1,2 \cdots n \}$ to be the targets of the edges of $v_i$.

Question 1: Is it true that (allowing $n$ to go to infinity) with probability 1 if one takes a graph of that sort, removes a single edge at random such a graph will be strongly connected

It is not too hard to see that with probability 1, the graph will not have any vertex $v$ where both of $v$s edges point back to itself but this is a much weaker claim.

The motivation for the question comes from thinking about Busy Beaver Turing machines as follows:

In Scott Aaronson's Busy Beaver there is a conjecture on page 20 that every Turing machine which makes a Busy Beaver aside from the trivial smallest has a corresponding directed graph which is strongly connected. (That conjecture is credited to me in that survey, but multiple other people have independently come up with the same conjecture, and I strongly suspect that some of them came up with the hypothesis well before I did.) Given the recent resolution of BB(5), this conjecture is now known to be true for n=5. Note also that a random Turing machine can be made by taking one of the graphs generated by the above procedure, with the additoinal step of flipping coins at each vertex to determine which of the edges corresponds to a transition from a 1, and which to a 0. The vertex with the single out arrow corresponds to then having the the halt condition.

However here is a bolder hypothesis (one hesitates to call it a conjecture): Let $P(G)$ be a property of directed graphs with out degree exactly 2 except at a single vertex of out degree 1, and with one vertex designated as a start vertex. Assume that $P(G)$ is computable, and assume further that $P(G)$ is true with probability 1 for a random graph G(where the graph is made from the procedure in the first paragraph and then a start state is designated). Then for all sufficiently large $n$, the graph of the $n$th Busy Beaver machine satisfies $P(G)$.

This hypothesis is in some sense statement that any general property of Turing machines will never rule out more than a tiny fraction of potential Turing machines as potential Busy Beaver candidates. The hypothesis together with the conjecture that Busy Beaver machines are strongly connected implies question 1. But question 1 is just a graph theory question with nothing in it about Turing machines.

I'd also be happy if someone could show that the answer to Question 1 is yes without the added complication of the single removed edge, which if it is true seems easier to prove and a more natural thing to ask about from a purely graph theory standpoint.

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

(What happens if you condition to every vertex having in-degree 2? Or at least one? In the undirected setting, random $4$-regular graphs are expanders, so very connected.)

Edit: Actually, given your motivation, one should restrict to "trim" automata, i.e., every vertex can be reached from the start vertex. Then maybe a better conclusion to aim for would be “essentially ergodic” with high probability.