For a probabilistic graph (G =(V, E, s, t), p), where G is an undirected graph with specified source vertex s and sink vertex t (s not equal t) in which each edge has independent failure probability and each vertex is assumed to be failure-free, and p = (p(e(1)),..., p(e(\E\))) is a vector consisting of failure probabilities p(e(i))'s of all edges e(i)'s in E, we consider the problem of computing the expected maximum number Gamma((G,p)) of edge-disjoint s-t paths. It is known that this computing problem is NP-hard even if G is restricted to several classes like planar graphs, s-t out-in bitrees and s-t complete multi-stage graphs. In this paper, for a probabilistic graph (G = (V, E, s, t), p), we propose a lower bound of Gamma((G,p)) and show the necessary and sufficient conditions by which the lower bound coincides with Gamma((G,p)). Furthermore, we also give a method of computing the lower bound of Gamma((G,p)) for a probabilistic graph (G =(V, E, s, t), p).