How would you incorporate probability into this graph theory problem?

Question

A non-closed path is chosen at random on the complete graph K9. All paths are equally likely. What is the probability that the path contains the edges {23} and {34} given that it is length 6? Given that it has the edge {89}?

Answer 1

Hint: A (directed) path of length $6$ can be encoded as a string of $7$ digits from $\{1,2,\ldots,9\}$, where each digit represents a vertex from $K_9$. For example, one possible path could be: $$ 1254367 $$ But observe that since paths are undirected, we can reverse this path and it would still be the same thing. So the total number of paths of length $6$ in $K_9$ is: $$ \frac{9!}{2 \cdot (9 - 7)!} $$

---

Now suppose that we want to count the number of paths of length $6$ that also contain the edges $\{23\}$ and $\{34\}$. Then this amounts to finding the number of strings of $7$ digits from $\{1,2,\ldots,9\}$ that contain $234$ or $432$ as a substring, then dividing the result by $2$. To do this, notice that:

• There are $2$ possible substrings: $234$ or $432$.
• There are $5$ possible positions that this substring can be in the path: $$ 234???? ,~~~ ?234??? ,~~~ ??234?? ,~~~ ???234? ,~~~ ????234 $$
• There are $9 - 3 = 6$ remaining vertices that can fill the $4$ remaining question marks.

Hence, the total number of paths of length $6$ in $K_9$ that also contain the edges $\{23\}$ and $\{34\}$ is: $$ 2 \cdot 5 \cdot \frac{6!}{2 \cdot (6 - 4)!} $$