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
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
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
(Godsil and Royle 2001, p. 355).
The following table summarizes simple classes of graphs having closed-form reliability polynomials. Here, .
The following table summarizes the recurrence relations for reliability polynomials for some simple classes of graphs.
Nonisomorphic graphs do not necessarily have distinct reliability polynomials. The following table summarizes some co-reliability graphs.