AbstractSuppose that every edge of a graph G (finite and undirected) is independently operational with probability . The all terminal reliability of G is the probability that all vertices can communicate. It was conjectured that among all graphs with n vertices and m edges there always exists a most optimal graph, that is, one whose all terminal reliability is at least as large as any other such graph, no matter what the value of p. For each , a single value of m was found for which the restriction of the conjecture to simple graphs failed, but it remained open as to whether most optimal graphs exist when multiple edges are allowed. We show that in fact for a given , there are several values of m for which a most optimal simple graph does not exist. Moreover, we prove that including multiple edges still does not introduce a most optimal graph, disproving for the first time the conjecture for general graphs. In contrast, it will be shown that for a given n and m, there always exists a least optimal graph. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 146–153 2014