  In the field of computer science, the network reliability problem for
evaluating the network failure probability has been extensively investigated.
For a given undirected graph $G$, the network failure probability is the
probability that edge failures (i.e., edge erasures) make $G$ unconnected. Edge
failures are assumed to occur independently with the same probability. The main
contributions of the present paper are the upper and lower bounds on the
expected network failure probability. We herein assume a simple random graph
ensemble that is closely related to the Erd\H{o}s-R\'{e}nyi random graph
ensemble. These upper and lower bounds exhibit the typical behavior of the
network failure probability. The proof is based on the fact that the cut-set
space of $G$ is a linear space over $\Bbb F_2$ spanned by the incident matrix
of $G$. The present study shows a close relationship between the ensemble
analysis of the network failure probability and the ensemble analysis of the
error detection probability of LDGM codes with column weight 2.
