Graph Likelihood

The graph likelihood of a simple graph is defined by starting with the set . The following procedure is then iterated to produce a set of graphs of order . At step , randomly pick an integer from the set . Now randomly pick one of the graphs in (keeping the probability that it was constructed in step ) and add a new vertex joined to randomly selected vertices of that graph. Now merge any isomorphic graphs produced by this procedure by totalling their probabilities. The likelihood of a graph on vertices is then defined as the probability that appears in .

The more general sequential-growth process, with an arbitrary distribution of the vertex degree of each new vertex, was studied by Janson and Severini (2013). The graph likelihood arising from the discrete uniform distribution on the possible degrees was introduced by Banerji et al. (2014).

The th iteration of this procedure produces every possible graph on vertices. The results for graphs of orders to 4 are illustrated above. Likelihoods for all simple graphs of order up to 10 have been computed by E. Weisstein (Dec. 23, 2013).

, where is the graph complement of . and are therefore co-likely.

Since the values are probabilities, the sum of likelihoods over all -node graphs is 1 and individual likelihoods satisfy

with holding only for . also satisfies the stronger inequality

where is the order of the automorphism group of (Banerji et al. 2014).

An exact recurrence is obtained by defining

Then , and for a graph on vertices,

where denotes the vertex deletion of from . Equivalently,

Choosing any representative of the isomorphism class of with vertex set , the same exact recurrence gives a subset dynamic program

with and

Thus graph likelihood can be computed exactly either by recursive evaluation of the vertex-deletion recurrence or, after choosing such a representative, by the subset dynamic program above. The latter uses arithmetic operations and space (Severini and Weisstein 2026).

The following table summarizes the likelihoods for members of a number of special classes.

Classes with known closed form values include

Here is a complete graph, is an empty graph, is a star graph, is a factorial, and is a subfactorial.

For the ladder rung graph ,

Equivalently, its likelihood has the series-coefficient form

where denotes coefficient notation and is the inverse erf function. Since the cocktail party graph is the graph complement of and , both formulas also hold for it.

In addition, there is a relationship between for a cycle graph and for a path graph given by

(Banerji et al. 2014).

In general, a graph on vertices with isolated edges has likelihood

giving special cases

where is a harmonic number.

Values of for -node graphs are plotted above.

Computations by E. Weisstein in 2013 found that, for all except , 3, and 5, the minimum is attained by the balanced complete bipartite graph when and by when , together with their graph complements. For the three exceptional orders, the minima occur for , , and , respectively. Citing this numerical evidence, Dervovic et al. (2018) conjectured that these complete bipartite graphs and their graph complements give the minima for all .

Severini and Weisstein (2026) proved that, among complete bipartite graphs of a given order, the balanced one uniquely minimizes graph likelihood. Exact computations show that it also minimizes over all graphs for , apart from the known exception at . However, is the first failure of the global conjecture. The graph blow-up of the cycle graph by independent sets of size 3, equivalently the circulant graph , satisfies

This counterexample is both a triangle-free graph and a vertex-transitive graph.

More generally, Severini and Weisstein (2026) proved

as . Thus the ratio between the likelihood of the balanced complete bipartite graph and the minimum grows exponentially in , so the conjecture fails for every sufficiently large . They also showed that the Shannon entropy of the graph-likelihood distribution is bits. Consequently, the graph likelihood of the balanced complete bipartite graph is asymptotically greater than that of a typical graph generated by the uniform sequential-attachment process defining graph likelihood.

The minimum values of for , 2, ... are 1, 1/2, 1/6, 1/36, 1/270, 23/259200, ... (OEIS A234234 and A234235).

The situation for maximum as a function of is less clear, with maxima occurring for , 2, ... for , , , paw graph, dart graph, ... and their complements. The corresponding maximum values are 1, 1/2, 1/3, 13/72, 307/4320, 1927/86400, ... (OEIS A234236 and A234237).