A proof of Boesch's conjecture

A well‐known model for network reliability studies consists of an undirected graph with perfectly reliable nodes and equal and independent edge failure probabilities. The measure of reliability is defined to be the probability that a graph is connected. A well‐defined synthesis problem is to find a graph that maximizes the probability given the number of nodes n , the number of edges e , and edge failure rate p . The problem of a uniformly optimally reliable graph is to find a graph that is optimal for all possible p . The graph studies are attracting more and more attention. Boesch et al. verified the existence of uniformly optimally reliable graphs when e = n, n + 1,n + 2 and given a conjecture for e = n + 3 . In this work, a proof of the conjecture is given and it is proved that any min‐m i graph is 2‐connected.