Is there a version of Menger's Theorem for a random graph?

Question

I'm curious about finding the number of disjoint paths between two nodes in a random graph $G(n,p)$. What I would like to do is to treat the number of paths as a random variable, and find its expectation. I'm thinking this should depend on $p$, but even for $n=4$ I'm having trouble computing this.

Answer 1

I don't think you are exactly looking for "a version of Menger's theorem for random graphs". Menger's theorem states that

In any finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.

But you can use it to transfer existing results on $k$-connectivity : It is known that for a random graph in $G(n,p)$, with $p$ fixed, for any $k\in \mathbb{N}$, then almost every graph is $k$-connected, i.e. for any $k$, the probability that $G\in G(n,p)$ is $k$ connected tends to one.

Therefore by Menger's theorem, for any $k$, for any two dinctinct vertices $u$ and $v$, the probability that there are $k$ disjoint paths between $u$ and $v$ tends to 1.

I don't know if you can do much better though (with explicit formula for the number of paths, given $n$). There are also existing results on $k$-connectivity with $p=c/n$.