Summary: A graph \( G \) is stronger than a graph \( H \) if \( G \) has at least as many connected spanning subgraphs of size \( k\) as \( H \) for any positive integer \( k \). Counting the number of connected spanning subgraphs of fixed size allows us to compute the reliability of a graph. Formally, the reliability polynomial of a graph is the probability that the graph is connected when each edge is deleted independently with the same fixed probability. A graph \( G \) is uniformly more reliable than \( H \) if its reliability polynomial is greater than or equal to the reliability polynomial of \( H \) for all probabilities. As a direct consequence of the definition, a sufficient condition for \( G \) to be uniformly more reliable than \( H \) is for \( G \) to be stronger than \( H \). In this paper, we show that the sufficient condition is not necessary by providing an example of two infinite families of graphs, \( {G}_k \) and \( {H}_k \), such that \( {G}_k \) is uniformly more reliable than \( {H}_k \) but is not stronger than \( {H}_k \).
{© 2022 Wiley Periodicals LLC.}