We suppose without loss of generality that G is connected. Consider all of the 2 to the (n choose 2) states of G'. Each state will have zero or more real edges operating, and zero or more of the virtual edges operating. Let's write m for the number of edges of G, and z for the number of virtual edges (= (n choose 2)-m). In the reliability of G', only those connected subgraphs of G' appear. Now collect together all of the states that have exactly i virtual edges operating, for i = 0, 1, ..., z. Then the reliability of G' can be written as sum from i=0 to z of epsilon^i * (1-epsilon)^{z-i} * A_i, where A_i is some rational quantity. Now when i=0, a connected state of G' is a connected state of G, so the all-terminal reliability of G is A_0.
Let's multiply the all-terminal reliability of G' by (1-epsilon)^z, and let e=epsilon/(1-epsilon). Then the expression given becomes sum from i=0 to z of e^i A_i.
Every edge of G had some rational probability a_i / b_i (i=1,...,m), and so we can see that each A_i is a rational number whose denominator is a divisor of the product b_1 * b_2 * ... * b_m. Let f be 1 over 2*b_1*b_2*...*b_m+1. So, if we choose e (i.e., choose epsilon) so that sum from i=1 to z of e^i A_i is less than f, we will be able to determine A_0 by rounding to the nearest fraction with the product of the b_i's as the denominator.
To do this, we observe that the number of states considered in the sum is less than 2 to the (n choose 2), and hence we need only ensure that 2 to the n choose 2 times e is less than f. To guarantee this, choose epsilon to be the rational number with numerator 1 and denominator 2*(2*b_1*b_2*...*b_m+1) * (2 to the (n choose 2)).
Since each b_i was of size polynomial in n, the product is of size polynomial in n, and the proof is complete.
Since bipartite graphs are a special case of the general problem, all-terminal reliability for bipartite graphs is no harder than for general graphs.
In the other direction, consider an arbitrary general graph. Replace each edge e={x,y} by adding a new vertex z_e, the edges {x,z_e} with probability one and {y,z_e} with probability the same as edge e, and removing the edge e. The resulting graph has the same reliability as does the original, and it is bipartite with classes consisting of the original and the new vertices.
The spanning trees of a connected graph G can be partitioned into two groups with respect to any edge e, namely those containing e and those not containing e. If e is neither a bridge nor a loop, both classes are nonempty. Moreover, spanning trees not containing e are exactly the spanning trees of G-e, and those containing e appear as spanning trees of G.e once the edge e is contracted.
In other words, #spanning-trees(G) = #spanning-trees(G-e) + #spanning-trees(G.e), and the result now follows by an easy induction.
Only a sketch of a solution is given, because this forms the basis of a question on Assignment Three. The idea is as follows. For the last rule, adding an edge to a pendant vertex does not change the reliability, and one can check that in this case N_i(L(n,m)) = N_{i-1}(L(n-1,m-1)). So we really only need to worry about the first two rules.
We handle them by generalizing the method discussed in class for complete graphs. Suppose that we have made L(n,m). Then let's let u be the only vertex of degree less than n-1 if L(n,m) is not complete, otherwise a vertex of degree n-1. Let v be a vertex of degree n-1 (other than u). And suppose that v and u are neighbours. Now consider a state of L(n,m), and look at the component containing v. It will have some number i of vertices; these may contain u or not; and some of the vertices in the same component of i will be neighbours of u. Suppose that j of them are. Now we need to determine how many ways there are to choose i vertices containing v, in which j are neighbours of u, and in which u does or does not appear. Since this accounts for all possible states, if we can figure out the probabilities of getting a picture of each type (i.e., for each i and j, and for u inside or outside) then we'll get an expression involving reliabilities of L(n,m) for smaller values of n and m.
In this way, one can get a recursive formula for the reliability of L(n,m). If you haven't done this yet, do it.
Not solved here, as it appears on Assignment Three. But here is a set of numbers for N_i that I believe to be correct, and may be helpful in your checking: The results are for L(6,12). N_0 = N_1 = N_2 = N_3 = N_4 = 0; N_5 = 300; N_6 = 605; N_7 = 644; N_8 = 447; N_9 = 210; N_10 = 65; N_11 = 12; N_12 = 1.
First, note that if there are (n-1)!-1 factoring steps, then there are (n-1)! graphs on which no further factoring is done. So we want to prove that, if we make a "factoring tree" for the complete graph, with internal nodes representing a graph which is factored, and leaves being graphs upon which no further factoring is needed, then it need not have more than (n-1)! leaves.
Since parallel reductions are permitted, let's suppress parallel edges the moment they arise. Make our factoring strategy be the following. Choose a vertex v, and factor on the n-1 edges incident with v in sequence. Once one of these edges operate, a contraction is performed and (once parallel edges are suppressed) the remaining graph is complete on n-1 vertices. So we will encounter this smaller complete graph whenever i edges fail and then the next operates for some i between 0 and n-2 (one edge incident with v must operate, and if the first n-2 all fail the last is a bridge and then is just contracted). So there are n-1 ways for the edges incident with v to lead to a complete graph of order n-1, and no other outcome is possible.
Now we have #leaves-in-factoring-tree(K_n) <= (n-1) * #leaves-in-factoring-tree(K_{n-1}) and the result follows since #leaves-in-factoring-tree(K_2) = 1.
Email me if you have tried to figure out what to do, but have questions that you need answered.