viii. Counting Graphs and Trees

Counting labelled graphs (all, connected, acyclic directed, even), labelled trees and forests (Cayley, given degrees, rooted forests, functional graphs) and unlabelled trees (rooted and free, Otter). Spanning trees of a given graph are the Matrix-Tree Theorem; Prüfer codes and tree isomorphism are in Isomorphism and Prüfer; Comb/mint from Modular Arithmetic.

Objects on $n$ labelled vertices	Count	Values ($n=\mathrm{1..6}$)
graphs; tournaments	$2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$	1, 2, 8, 64, 1024, 32768
graphs with $m$ edges	$\left(\genfrac{}{}{0ex}{}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}{m}\right)$
connected graphs	$c_n=g_n-{\sum }_{k=1}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)c_k{g}_{n-k}$; EGF $C(x)=\ln G(x)$	1, 1, 4, 38, 728, 26704
graphs with all degrees even (Eulerian, not nec. connected)	$2^{\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)}$	1, 1, 2, 8, 64, 1024
DAGs (Robinson)	$a_n={\sum }_{k=1}^n(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{n}{k})2^{k(n-k)}{a}_{n-k}$	1, 3, 25, 543, 29281, 3781503
trees (Cayley)	$n^{n-2}$	1, 1, 3, 16, 125, 1296
trees with degrees $d_1..d_n$ ($\sum d_i=2n-2$)	$\frac{(n-2)!}{\prod (d_i-1)!}$
forests of $k$ trees rooted at $k$ given vertices	$k{n}^{n-k-1}$
all rooted forests	$(n+1{)}^{n-1}$	1, 3, 16, 125, 1296, 16807
spanning trees of $K_{a,b}$	$a^{b-1}{b}^{a-1}$
functional graphs $f:[n]\to [n]$	$n^n$
connected functional graphs (one cycle)	${\sum }_{k=1}^n\frac{n!}{(n-k)!}{n}^{n-k-1}$	1, 3, 17, 142, 1569, 21576

Unlabelled ($n=\mathrm{1..11}$)	Method	Values
rooted trees $r_n$	Euler transform: $r(x)=x{\prod }_k(1-x^k{)}^{-r_k}$	1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842
free trees $t_n$	Otter: $t(x)=r(x)-\frac{r(x{)}^2-r(x^2)}{2}$	1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235
graphs up to isomorphism	Pólya over cycle types (Burnside and Pólya)	1, 2, 4, 11, 34, 156, …

struct GraphCounting {                                     // tables for 0..n, prime modulus > n
    int n; Comb cb; vector<mint> graphs, connected, dags;
    GraphCounting(int N) : n(N), cb(N + 1), graphs(N + 1), connected(N + 1), dags(N + 1) {
        for (int i = 0; i <= n; i++) graphs[i] = mint(2).pow((ll)i * (i - 1) / 2);
        connected[0] = 0;
        for (int i = 1; i <= n; i++) {                     // fix vertex 1; its component has k vertices
            mint s = graphs[i];
            for (int k = 1; k < i; k++) s -= cb.C(i - 1, k - 1) * connected[k] * graphs[i - k];
            connected[i] = s;
        }
        dags[0] = 1;
        for (int i = 1; i <= n; i++) {                     // inclusion-exclusion over the set of sources
            mint s = 0;
            for (int k = 1; k <= i; k++) { mint t = cb.C(i, k) * mint(2).pow((ll)k * (i - k)) * dags[i - k]; s += k % 2 ? t : -t; }
            dags[i] = s;
        }
    }
    mint trees(int i) const { return i <= 1 ? mint(1) : mint(i).pow(i - 2); }
    mint rootedForests(int i, int k) const { if (k == i) return 1; if (k == 0) return i == 0; return mint(k) * mint(i).pow(i - k - 1); }
    mint allRootedForests(int i) const { return mint(i + 1).pow(max(i - 1, 0)); }
    mint evenGraphs(int i) const { return i == 0 ? mint(1) : mint(2).pow((ll)(i - 1) * (i - 2) / 2); }
    mint connectedFunctional(int i) const {
        mint s = 0;
        for (int k = 1; k <= i; k++) s += cb.f[i] * cb.fi[i - k] * (k == i ? mint(i).inv() : mint(i).pow(i - k - 1));
        return s;
    }
    mint treesWithDegrees(const vector<int>& d) const {    // labelled trees with deg(i) = d[i], n >= 2
        int m = sz(d); ll s = 0; for (int x : d) { if (x < 1) return 0; s += x; }
        if (s != 2LL * m - 2) return 0;
        mint r = cb.f[m - 2]; for (int x : d) r *= cb.fi[x - 1];
        return r;
    }
};
 
pair<vector<ll>, vector<ll>> unlabeledTrees(int N) {        // r[n] rooted, t[n] free, exact up to n ~ 38
    vector<ll> r(N + 1, 0), t(N + 1, 0), s(N + 1, 0);       // s[k] = sum_{d | k} d r[d]
    if (N >= 1) r[1] = 1;
    for (int m = 1; m < N; m++) {                          // r[m+1] = (1/m) sum_{k=1}^m s[k] r[m-k+1]
        for (int d = 1; d <= m; d++) if (m % d == 0) s[m] += d * r[d];
        ll acc = 0; for (int k = 1; k <= m; k++) acc += s[k] * r[m - k + 1];
        r[m + 1] = acc / m;
    }
    for (int m = 1; m <= N; m++) {
        ll sq = 0; for (int i = 1; i < m; i++) sq += r[i] * r[m - i];
        if (m % 2 == 0) sq -= r[m / 2];
        t[m] = r[m] - sq / 2;
    }
    if (N >= 0) t[0] = 1;
    return {r, t};
}

Complexity: GraphCounting $O(n^2)$ (or $O(n\log n)$ with power-series $\ln$ for $c_n$, Counting with Power Series); unlabeledTrees $O(N^2)$. Variants solved the same way: connected graphs with $m$ edges (DP over vertices and edges with the same “component of vertex 1” split), labelled bipartite and strongly connected digraphs (inclusion–exclusion over a distinguished part, with EGFs).

Proof: the labelled counts

Connected. Fix vertex 1; its component has $k$ vertices, chosen in $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ ways, is connected ($c_k$), and the rest is an arbitrary graph ($g_{n-k}$); summing over $k$ gives $g_n$, solved for the $k=n$ term. As EGFs this says $G=\exp (C)$ (a graph is a set of connected components). Even graphs: choose any edge set on vertices $\mathrm{1..}n-1$; then each vertex $v<n$ is joined to $n$ iff its degree so far is odd; vertex $n$‘s degree is the number of odd-degree vertices of a graph, which is even. This is a bijection. DAGs: every DAG has a non-empty set of sources. For a non-empty set $S$ of $k$ vertices, the DAGs in which every vertex of $S$ is a source are: arbitrary edges from $S$ to the rest ($2^{k(n-k)}$), none into $S$, and a DAG on the rest ($a_{n-k}$). Inclusion–exclusion over $S\subseteq \mathrm{sources}$ counts each DAG ${\sum }_{\varnothing \ne S\subseteq \mathrm{src}}(-1{)}^{|S|+1}=1$ time.

Trees. Prüfer codes are a bijection between labelled trees on $n\ge 2$ vertices and $[n{]}^{n-2}$, in which vertex $i$ appears $d_i-1$ times (Isomorphism and Prüfer): this gives $n^{n-2}$ and the multinomial $\frac{(n-2)!}{\prod (d_i-1)!}$. Rooted forests on $k$ given roots: add a new vertex 0 joined to the $k$ roots; this is a bijection with the trees on $\{\mathrm{0..}n\}$ in which 0 has exactly the neighbours $\mathrm{1..}k$. Trees on $n+1$ vertices in which 0 has degree $k$ number $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)n^{n-k}$ (0 occupies $k-1$ of the $n-1$ Prüfer positions, the others hold any of the $n$ other labels), and by relabelling all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ neighbour sets of size $k$ are equally frequent: $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)n^{n-k}/\left(\genfrac{}{}{0ex}{}{n}{k}\right)=k{n}^{n-k-1}$. All rooted forests: join a new vertex to every root: a bijection with labelled trees on $n+1$ vertices, $(n+1{)}^{n-1}$. $K_{a,b}$: the Laplacian has eigenvalue $a$ on vectors supported on the $b$-side summing to 0 (multiplicity $b-1$), $b$ symmetrically ($a-1$), $a+b$ on the vector equal to $b$ on the $a$-side and $-a$ on the $b$-side, and 0 on the constant vector; the Matrix-Tree Theorem gives $\frac{1}{a+b}{a}^{b-1}{b}^{a-1}(a+b)$. Connected functional graphs: the unique cycle has $k$ vertices ($\left(\genfrac{}{}{0ex}{}{n}{k}\right)(k-1)!$ cyclic orders), and the other vertices form a forest rooted at the cycle vertices with edges directed towards the roots ($k{n}^{n-k-1}$, or 1 if $k=n$); the product simplifies to $\frac{n!}{(n-k)!}{n}^{n-k-1}$.

All labelled counts were checked by brute force over all graphs, digraphs and functions for $n\le 5$ or 6.

Proof: unlabelled rooted and free trees (Euler transform, Otter)

Rooted. Removing the root leaves a multiset of rooted trees with total size $n-1$, so $r(x)=x{\prod }_{k\ge 1}(1-x^k{)}^{-r_k}$. Taking $x\frac{d}{dx}\ln$ of both sides: $\frac{x{r}^{\prime }(x)}{r(x)}=1+{\sum }_k{r}_k\frac{k{x}^k}{1-x^k}=1+{\sum }_m{s}_m{x}^m$ with $s_m={\sum }_{d\mid m}d{r}_d$. Multiplying by $r$ and comparing the coefficients of $x^{m+1}$: $(m+1)r_{m+1}=r_{m+1}+{\sum }_{k=1}^m{s}_k{r}_{m+1-k}$, i.e. $m{r}_{m+1}={\sum }_{k=1}^m{s}_k{r}_{m-k+1}$, an exact division.

Otter’s dissimilarity. For a tree $T$ with automorphism group $A$, let $v$, $e$ be the numbers of vertex and edge orbits, and $\delta =1$ if some automorphism swaps the ends of an edge. Then $v-e+\delta =1$. Every automorphism fixes the centre. If the centre is a vertex, or an edge whose ends are not swapped, root $T$ there: automorphisms preserve parents, so mapping each non-root vertex to the edge to its parent is a bijection between non-root vertex orbits and edge orbits, and $v-e=1$. If the centre edge $uv$ is flipped by some automorphism, map every other edge to its endpoint farther from the centre: this is a bijection between the edge orbits other than $\{uv\}$ and the vertex orbits other than $\{u,v\}$ (one orbit), so $v-e=0$ and $\delta =1$. Summing over all trees of size $n$: $t_n=\sum v-\sum e+\sum \delta$. The vertex orbits of all trees are the rooted trees ($r(x)$); edge orbits are trees rooted at an edge, i.e. unordered pairs of rooted trees ($\frac{r(x{)}^2+r(x^2)}{2}$); flippable centre edges are ordered-identical pairs ($r(x^2)$). Hence $t=r-\frac{r^2+r(x^2)}{2}+r(x^2)=r-\frac{r^2-r(x^2)}{2}$. Both sequences were checked against the known values above (OEIS A000081, A000055).

Related notes

• Matrix-Tree Theorem
• Isomorphism and Prüfer
• Generating Functions (EGF $\exp$ / $\ln$)