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 probability distribution over isomorphism classes of graphs of order . At step , choose an integer uniformly from . Choose a graph in according to its probability, and add a new vertex joined to a uniformly chosen -element subset of its vertices. Merge any isomorphic graphs produced by this procedure by totaling their probabilities. The likelihood of a graph on vertices is the probability assigned to its isomorphism class 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).

The fact that every finite graph can be obtained, and therefore has positive likelihood, is a graph-theoretic analog of the infinite monkey theorem (Banerji et al. 2014).

, 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. Parameters start at 1 except for hypercube graphs (), triangular graphs (), antiprism graphs, barbell graphs, crown graphs, cycle graphs, Möbius ladders, prism graphs, and sun graphs (), and wheel graphs (). The star OEIS pair uses the shifted index and gives the numerator and denominator together for .

For positive integers , 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 with ,

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 for by

(Banerji et al. 2014).

For and , let be the disjoint graph union of copies of and isolated vertices. Its likelihood is

giving special cases

where is a harmonic number.

Values of for -node graphs are plotted above.

The minimizing graphs for are illustrated above. Computations by E. Weisstein (2013) determined the minima through . On this numerical evidence, Dervovic et al. (2018) conjectured that the balanced complete bipartite graph and its graph complement minimize graph likelihood for every . Severini and Weisstein (2026) determined all global minimizers through . The balanced complete bipartite graph and its graph complement are the only minimizers for except at , 15, and 17. Among complete bipartite graphs of any given graph order , the balanced member uniquely minimizes graph likelihood.

The following table gives the exact minima and all minimizing graphs, up to graph isomorphism. Here , , and denote a complete graph, a cycle graph, and a path graph, respectively, denotes the graph complement, and denotes a disjoint graph union, with .

For , the minimum is attained exactly by the graph blow-up of the cycle graph by independent sets of size 3 and by its graph complement, the Catlin graph. The blow-up is equivalently the circulant graph . These two graphs have 45 and 60 edges, respectively, and their automorphism groups both have order 77760. The minimum likelihood is , and its ratio to that of is

Thus is the first failure of the global conjecture. This counterexample is both a triangle-free graph and a vertex-transitive graph.

For , the unique minimizer is a self-complementary graph obtained from the cycle graph by replacing its vertices, in cyclic order, with , , , , and , where and are complete graphs and is an empty graph. Join cyclically consecutive parts completely and add no edges between nonconsecutive parts (Severini and Weisstein 2026).

Exact computation shows that, for , the minimum is attained, up to graph isomorphism, exactly by the complete bipartite graph and its graph complement (OEIS A234234 and A234235).

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).

Exact maxima are known through , with the maximizing graphs illustrated above. Neither threshold graphs nor split graphs contains maximizers for every graph order (Severini and Weisstein 2026). For , 2, ..., the maximum values are 1, 1/2, 1/3, 13/72, 307/4320, 1927/86400, ... (OEIS A234236 and A234237).