Definition) The length of a path between two vertices in a graph is the number of edges in the path connecting them.
Definition) A random graph $G(n,p)$ is a graph with $n$ vertices, and the probability of drawing each edge is $p$ and independent of other edges.
Let $G(n,p)$ be a random graph.
- Event $A$ : There is at least one path with length $l$ between $v$ and $u$.
- Event $B_{1}$ : There is no path with length $1$ between $v$ and $u$.
- Event $B_{2}$ : There is no path with length $2$ between $v$ and $u$.
- ...
- Event $B_{l-1}$ : There is no path with length $l-1$ between $v$ and $u$.
Are $A,B_{1},...,B_{l-1}$ independent events?
Consider the path of length 1 between $u$ and $v$. There is only one such path. Since the usual convention is that paths do visit any vertex more than once, all longer paths between $u$ and $v$ cannot use the edge directly connecting $u$ and $v$. So the path of length 1 has no edge in common with the longer paths. This makes the event $B_1$ independent from all the other events since it uses its own unique potential edge that is randomly chosen to be present or not independently from the other edges.
Let's assume $n>3$. $B_1$ will be independent from $B_2$ and $B_3$. Generally however, $B_2$ and $B_3$ will not be independent. Intuitively, not having a path of length 2 would make it more likely that $u$ and $v$ have few edges, which in turn makes it more likely that there are no paths of length 3. For example, let's look at the simplest case, $G(4, 1/2)$.
$K_4$ has 6 edges, so we have $2^6=64$ equally probably graphs.
Exactly 28 of these graphs have at least one path of length 2 between two designated vertices $u$ and $v$. This means that 36 have none, so $P(B_2)=36/64=9/16$.
Exactly 14 of the 64 graphs have at least one path of length 3 between $u$ and $v$, so 50 have none and $P(B_3)=50/64=25/32$.
There are 32 graphs that have neither a path of length 2 nor a path of length 3, so $P(B_2 \cap B_3) = 32/64 = 1/2$.
So as expected we have: $$P(B_3|B_2) = \frac{P(B_3 \cap B_2)}{P(B_2)} = \frac{32}{36} = \frac{8}{9} > P(B_3)$$