Broken Bridges

Let's model the village as an undirected graph, with 10 nodes, and, initially, 45 edges for bridge completeness. We are looking for the probability that, if each edge is removed with independent probability 50%, the graph remains connected. Since we require 10 digits of precision, Monte Carlo methods are not going to help us, and since there are, counting isomorphisms, $2^{45}$ such graphs, direct counting isn't going to help either!

---

The first bit we need to understand is that every possible graph is equally likely . That is, by simply numbering the edges of the graph, any number-labeled configuration of edges that remain and edges that are destroyed can occur with probability $2^{-45}$ . So, if we are able to compute the total number of possible connected graphs, then we can easily compute the probability that our graph is one of them.

We'll let $T(n)$ be the total number of graphs of size $n$ , with vertices labeled $\{1, 2, 3, ..., n\}$ . Let $C(n)$ be the total number of connected graphs of size $n$ , and let $D(n)$ be the total number of disconnected graphs of size $n$ . We find that:

$T(n) = 2^{\left( \frac{n(n-1)}{2} \right)}$

$C(n) = T(n) - D(n)$

$D(n) = \sum_{k=1}^{n-1} {\binom{n-1}{k-1} \cdot C(k) \cdot T(n-k)}$

That last definition is the most interesting one, as it allows us to actually compute $C(10)$ , which we need to get $P$ . Let's break it down a bit:

• A disconnected graph is the union of 2 or more connected components whose vertices are disjoint.
• Suppose vertex $1$ in a graph of size $n$ is in a connected component of size $k$ , and let that component be fixed. There are thus precisely $T(n-k)$ ways to populate the remainder of the graph.
• To make a connected component of size $k$ , we need $k-1$ nodes to add to node $1$ . There are $\binom{n-1}{k-1}$ ways to choose these nodes.
• With the nodes chosen, there are $C(k)$ ways to actually connect them all.
• Thus, there are $\binom{n-1}{k-1} \cdot C(k) \cdot T(n-k)$ ways to construct a disconnected graph of size $n$ such that vertex $1$ lives in a connected component of size $k$ .
• Sum over all possible $k$ , and we get $D(n)$ .

The scale of the problem is such that we don't need to cache values for $C(n)$ or $D(n)$ to compute $C(10)$ in reasonable time, as it is a mere $10 \cdot 2^{10}$ operations to do so. Using dynamic programming, however, would allow us to compute such outlandish values as $C(100)$ and $D(1000)$ instantly.

The answer is thus, simply:

$\left\lfloor 10^{10} \cdot \frac{C(10)}{T(10)}\right \rfloor = \boxed{9804491752}$

---

So John and company actually have a healthy 98% chance of remaining fully connected after the storm. Ten houses seems quite ideal indeed!

---

Update: Apparently $C(n)$ is defined in OEIS . So, if you're skeptical, just grab $a(10)$ from over there, divide by $2^{45}$ with a calculator, and see the decimal representation of $P$ for yourself.

I wrote some code to solve this problem. Have a look at the repository https://github.com/kpardeshi/Broken-Bridges