Balanced complete-bipartite graph likelihood conjecture

Let $G$ be a finite simple undirected graph on $n$ vertices, and let $\mathcal{L}(G)$ denote the probability that the uniform sequential attachment process outputs a graph isomorphic to $G$ . The conjecture states that, for every $n$ and every graph $G$ on $n$ vertices, $\mathcal{L}(G)\geq \mathcal{L}\!\left(K_{\lfloor n/2\rfloor,\lceil n/2\rceil}\right)$ ; equivalently, the balanced complete bipartite graph uniquely minimises the graph likelihood among graphs of order $n$ .

References

Primary source

arXiv

Additional references

The minimum of the graph likelihood — arXiv — Severini, Simone, Weisstein, Eric W.

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A new preprint confirms the prediction for complete bipartite graphs but gives a $15$ -vertex counterexample among all graphs.

The conjecture predicts that the relevant graph-likelihood minimum is attained by a balanced complete bipartite graph. The new paper by Simone Severini and Eric W. Weisstein settles the restricted complete-bipartite case and overturns the unrestricted version.

August 2026 counterexample and asymptotic result

A $15$ -vertex blow-up of the five-cycle disproves the conjecture over all graphs. The paper also establishes the asymptotic scale of the failure and proves that this is the first finite counterexample; enumeration covers orders $6$ through $14$ , while the general minimum follows from structural and asymptotic arguments.

Current status (as of August 2026): The conjecture is resolved for complete bipartite graphs, disproved for general graphs by a $15$ -vertex example, and its asymptotic failure scale is established.

Sources

arxiv.org

No solutions have been posted yet.