Probability of the existence of a path of a specified length between any tw0 vertices in a random graph

611 Views Asked by At

Let $G$ be a graph with $n$ vertices, whose average degree is $k$. What is the probability that between any two vertices, there exists a path of length at most $l$? NOTE: For the above problem the random graphs follow a $G(n, p)$ model, i.e., in a random graph, each edge occurs with a probability $p=k/n$.