Brown–Colbourn conjecture on all-terminal reliability roots

Jason Brown and Charles Colbourn formulated the conjecture in 1992. It asserted that all-terminal reliability roots lie in the unit disk; this assertion is now known to fail for general graphs.

Known results

• Wagner proved the conjecture for series-parallel graphs.
• Royle and Sokal reported both univariate and multivariate counterexamples; the smallest cited example comes from $K_4$ with two opposite edges replaced by bundles of six edges, producing a root of modulus approximately $1.0017$.
• Brown and collaborators later found simple-graph roots with larger modulus.
• Buys proved in 2026 that reliability roots of connected simple graphs are dense in the unit disk, while boundedness for connected multigraphs remains open.

2004 counterexamples; 2017 quantitative strengthening

Royle and Sokal's paper, revised April 2, 2004, established that the original conjecture is false. The 2017 paper On the roots of all-terminal reliability polynomials reported a stronger upper-bound framework and examples whose root modulus was nearly three times farther outside the unit disk than previously known examples.

Current status (as of September 2026): The conjecture for general connected graphs is disproved, and the series-parallel case is settled positively; related questions, including boundedness for connected multigraphs, remain open.