
# The graphs command allows one to generate all unlabeled graphs on a fixed number of nodes
# Note: Sage gives the nodes labels but only generates one graph per automorphism class
list(graphs(2))

[Graph on 2 vertices, Graph on 2 vertices]


# Get list of graphs up to 8 vertices
# (No claim of efficiency -- this blows up quickly)
GRAPHS = [list(graphs(k)) for k in range(9)]


# A graph on 8 vertices
show(GRAPHS[8][10000])


# Generate the counting sequence for the number of graphs
count = [len(k) for k in GRAPHS]
count

[1, 1, 2, 4, 11, 34, 156, 1044, 12346]


# Search the Online Encyclopedia of Integer Sequences for sequences beginning with "count"
# (NOTE: From here down Sage requires an internet connection)
oe_seqs = oeis(count)
oe_seqs

0: A000088: Number of graphs on n unlabeled nodes.


# Only one sequence in the OEIS has this start, and indeed it is unlabeled graphs
# We can read additional terms in the counting sequence from the OEIS
seq = oe_seqs[0]
seq.first_terms()

(1,
 1,
 2,
 4,
 11,
 34,
 156,
 1044,
 12346,
 274668,
 12005168,
 1018997864,
 165091172592,
 50502031367952,
 29054155657235488,
 31426485969804308768,
 64001015704527557894928,
 245935864153532932683719776,
 1787577725145611700547878190848,
 24637809253125004524383007491432768)


# These terms already get close to the known asymptotic behaviour
def asm(n): return 2^binomial(n,2)/factorial(n)
def exact(n): return seq.first_terms()[n]
point([[n,asm(n)/exact(n)] for n in range(5,20)])


# A list of counting formulas from the OEIS
seq.formulas()

 0: a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - _Vladeta Jovovic_ and _Benoit Cloitre_, Feb 01 2003
 1: a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - _Keith Briggs_, Oct 24 2005
 2: From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
 3: a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
 4: a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
 5: ..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
 6: ..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
 7: ..ord(c) = lcm{i : c_i>0};
 8: ..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
 9: a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - _N. J. A. Sloane_, Nov 11 2013
10: For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - _N. J. A. Sloane_, Apr 08 2014
11: a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - _Leonid Bedratyuk_, May 02 2015
12: From _Keith Briggs_, Jun 24 2016: (Start)
13: a(n) = 2^binomial(n,2)/n!*(
14:    1+
15:    2^(  -n +  1)*n$2+
16:    2^(-2*n +  3)*n$3*(n-7/3)+
17:    2^(-3*n +  6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
18:    2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
19:    2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
20:    2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
21: where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
22: (End)
23: a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - _Andrey Zabolotskiy_, Aug 11 2020

Example 1.1 (Exact vs. Asymptotic Enumeration for Unlabeled Graphs)¶