A simple model for a communication network is a probabilistic graph consisting of a set of nodes which is not fail and a set of edges which operates with a probability. One of the indicators which measure the performance of the network is all-terminal reliability, that is, probability that all nodes are connected with operational edges. Since to calculate its value precisely is NP-hard, it is important to obtain the bounds of the all-terminal reliability efficiently. In this paper, we propose the polynomial time algorithm that can derive the lower bound by transforming any graph to the grap...