Probability node A in a graph is isolated given that we know at least 1 node is isolated?

Question

Imagine we have this graph above and the probability that any edge doesn't exist is p(some given value). What is the probability that A is isolated(Not connected to any other node) given the the probability that edge i doesn't exist is p and we know that at least node is isolated?

I really have no idea how to calculate this because of the condition "at least 1 node is isolated."

Answer 1

This isn't an elegant solution, but I guess it is one. Maybe someone can come up with a better solution later. The only way I can think of solving this is to explicitly count it out. There are 8 edges.

• We cannot isolate any nodes without removing at least 2 edges.
• There are 3 ways to remove 2 edges so that a node is isolated (B,D,F)
• There are 20 ways to remove 3 edges so that a node is isolated (1 way to isolate A,C each. 6 ways to isolate each of B,D,F).

For removing 4 edges, we need some casework.

• There are 5 ways to isolate A, one of which also isolates B and another isolates D
• There are $\binom{6}{2}=15$ ways to isolate B. Of these, A,C,D and F are each isolated once.
• There are 5 ways to isolate C. One of these isolates B and another isolates F.
• There are $\binom{6}{2}=15$ ways to isolate D. Of these, A,F and B are each isolated once.
• There's one way to remove E. No other edge is isolated.
• There are $\binom{6}{2}=15$ ways to isolate F. Of these, C,D and B are each isolated once.

Putting these altogether, there are

$1+5\times 2 + 15\times 3 - \frac{1}{2}(2+4+2+3+0+3) = 49$

ways to isolate a point.

There are only 2 ways to remove 5 edges so that no vertices are isolated. The remaining edges are shown below:

(AB)(CF)(DE), (AD)(BC)(EF)

So, there are $\binom{8}{5}-2 = 54$ ways to isolate a node.

If more than 5 edges are removed, then at least one vertex will be isolated.

• There are $\binom{8}{6} = 28$ ways to remove 6 edges.
• There are $\binom{8}{7} = 8$ ways to remove 7 edges.
• There's only one way to remove all edges.

Let $q=1-p$. Then,

\begin{align} P(\text{at least one node isolated}) &= 3p^2q^6 + 20p^3q^5 + 49p^4q^4 + 54p^5q^3 + 28p^6q^2 + 8p^7q + p^8\\ P(\text{A is isolated}) &= p^3\\ P(\text{A isolated}|>0\text{ nodes isolated}) &= \frac{p}{3q^6 + 20pq^5 + 49p^2q^4 + 54p^3q^3 + 28p^4q^2 + 8p^5q + p^6}. \end{align}

Hope there were no mistakes. Make of that what you will.