Let
be a graph, and suppose each edge of is independently deleted with fixed probability . Then the probability that no connected component
of
is disconnected as a result, denoted is known as the reliability polynomial of .

The reliability polynomial is directly expressible in terms of the Tutte
polynomial of a given graph as

(1)

where
is the vertex count, the edge count, and the number of connected components (Godsil and Royle 2001,
p. 358; error corrected). This is equivalent to the definition

(2)

where
is the number of subgraphs of the original graph having exactly edges and for which every pair of nodes in is joined by a path of edges lying in subgraph (i.e., is connected and ), which is the definition due to Page and Perry (1994)
after making the change .

For example, the reliability polynomial of the Petersen
graph is given by

(3)

(Godsil and Royle 2001, p. 355).

The following table summarizes simple classes of graphs having closed-form reliability polynomials. Here, .

Brown, J. I. and Colbourn, C. J. "Roots of the Reliability Polynomial." SIAM J. Disc. Math.5, 571-585, 1992.Chari,
M. and Colbourn, C. "Reliability Polynomials: A Survey." J. Combin.
Inform. System Sci.22, 177-193, 1997.Colbourn, C. J.
The Combinatorics of Network Reliability. New York: Oxford University Press,
1987.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials
and Their Applications I: The Tutte Polynomial." 28 Jun 2008. http://arxiv.org/abs/0803.3079.Godsil,
C. and Royle, G. Algebraic
Graph Theory. New York: Springer-Verlag, pp. 354-358, 2001.Page,
L. B. and Perry, J. E. "Reliability Polynomials and Link Importance
in Networks." IEE Trans. Reliability43, 51-58, 1994.Royle,
G.; Alan, A. D.; and Sokal, D. "The Brown-Colbourn Conjecture on Zeros
of Reliability Polynomials Is False." J. Combin. Th., Ser. B91,
345-360, 2004.