  In the present paper, we derive an upper bound of the average network
breakdown probability of packet networks with unreliable relay nodes. We here
assume that relay nodes get independently broken with a given node breakdown
probability. A survivor graph is the induced subgraph obtained by removing the
broken relay nodes and their connecting edges from the original graph. If the
survivor network is disconnected, we consider a network breakdown happens. The
primal contribution of the paper is to derive an upper bound of the average
network breakdown probability, where the expectation is taken over a regular
graph ensemble. The proof of the bound is based on a natural one-to-one
correspondence between a regular graph and a regular bipartite graph, and also
on enumeration of bipartite graphs satisfying certain conditions. This proof
argument is inspired by the analysis of weight distribution for low-density
parity-check codes. Compared with estimates of the average network breakdown
probability obtained by computer experiments, it is observed that the upper
bound provides the values which are not only upper bounds but also precise
estimates of the network breakdown probability when the node breakdown
probability is small.
