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 graph in which the degree of all the nodes is more than two and by using of edge-packing. This algorithm can be applied to the probabilistic graph in which each edge operates with the different probability.