In combinatorics, graph enumeration is the branch that studies counting problems of graphs satisfying specific properties. Generating functions, Pólya's enumeration theorem, the symbolic method, and OEIS are the most important mathematical tools for solving such problems. Graph enumeration can be divided into labeled and unlabeled problems. In most cases¹, the labeled version is simpler than its unlabeled counterpart, so we will first examine the counting of labeled problems.

Labeled Trees

That is, Cayley's formula. Refer to the article on Prüfer sequences. We can also obtain this result using the Kirchhoff matrix tree theorem, generating functions, and Lagrange's theorem.

Exercises

Hihocoder 1047. Random Tree

Labeled Connected Graphs

Example Problem "POJ 1737" Connected Graph

Example 「POJ 1737」Connected Graph

Problem summary: Find the number of labeled connected graphs with $n$ vertices ($n \leq 50$).

This type of problem first appeared in the "Eight Problems for Men" series by Lou Jiao. Let $g_n$ be the number of labeled graphs with $n$ vertices, and $c_n$ be the sequence to be found. A graph with $n$ vertices has at most $\binom{n}{2}$ edges. Each edge has two states (present or absent), and each state is independent, so $g_n = 2^{\binom{n}{2}}$. We fix one vertex and enumerate the size of its connected component. Then we need to choose $i-1$ vertices from the remaining $n-1$ vertices to form a connected component. The vertices outside the connected component can be connected arbitrarily, leading to the following recurrence:

\[ \begin{align} \sum_{i=1}^{n} \binom{n-1}{i-1} c_i g_{n-i} &= g_n \\ c_n &= g_n - \sum_{i=1}^{n-1} \binom{n-1}{i-1} c_i g_{n-i} \end{align} \]

Rearranging gives an $O(n^2)$ recurrence formula for the $c_n$ sequence, which solves this problem.

Example Problem "2013 Training Team Assignment" Urban Planning

Example 「集训队作业 2013」城市规划

Problem summary: Find the number of labeled connected graphs with $n$ vertices ($n \leq 130000$).

For sequence problems with larger data ranges, we often need to construct generating functions for these sequences to use efficient polynomial algorithms.

Method 1: Divide-and-Conquer FFT

The above recurrence can be seen as a form of self-convolution, so it can be computed using divide-and-conquer FFT with complexity $O(n\log^2n)$.

Method 2: Polynomial Inverse

We expand the binomial coefficient in the recurrence and transform it:

\[ \begin{align} \sum_{i=1}^{n} \binom{n-1}{i-1} c_i g_{n-i} &= g_n \\ \sum_{i=1}^{n} \frac{c_i}{(i-1)!} \frac{g_{n-i}}{(n-i)!} &= \frac{g_n}{(n-1)!} \end{align} \]

Construct polynomials:

\[ \begin{align} C(x) &= \sum_{n=1} \frac{c_n}{(n-1)!} x^n \\ G(x) &= \sum_{n=0} \frac{g_n}{n!} x^n \\ H(x) &= \sum_{n=1} \frac{g_n}{(n-1)!} x^n \end{align} \]

Substituting into the above gives $CG = H$. Use polynomial inverse and then convolution to solve for $C(x)$.

Method 3: Polynomial exp

Another approach uses the combinatorial meaning of polynomial exp in EGF. Let the EGFs of labeled connected graphs and simple graphs be $C(x)$ and $G(x)$, respectively. Then they satisfy:

\[ \begin{align} \exp(C(x)) &= G(x) \\ C(x) &= \ln(G(x)) \end{align} \]

Use polynomial ln to solve for $C(x)$.

Labeled Eulerian Graphs, Bipartite Graphs

Example Problem "SPOJ KPGRAPHS" Counting Graphs

Example 「SPOJ KPGRAPHS」Counting Graphs

Problem summary: Find the number of labeled graphs with $n$ vertices satisfying the following properties ($n \leq 1000$).

Connected graphs A001187.
Eulerian graphs A033678.
Bipartite graphs A047864.

This problem has code length restrictions, so polynomial templates cannot be used directly, but generating functions can still help with analysis.

The connected graph problem was solved in the previous example. Consider Eulerian graphs. Note that the methods for counting connected graphs can be generalized to labeled connected graphs satisfying any property. For example, we can replace $g_n$ in the connected graph recurrence with graphs where all vertices have even degree, and the resulting $c_n$ will be Eulerian graphs.

We encapsulate the recurrence process from POJ 1737 into a connection function:

void ln(Int C[], Int G[]) {
  for (int i = 1; i <= n; ++i) {
    C[i] = G[i];
    for (int j = 1; j <= i - 1; ++j)
      C[i] -= binom[i - 1][j - 1] * C[j] * G[i - j];
  }
}

The first two questions can be easily solved:

for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i][2]);
ln(C, G);
for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i - 1][2]);
ln(E, G);

Note that the connection recurrence process here is equivalent to taking the polynomial ln of its EGF. Similarly, we can write an inverse connection function, which is equivalent to taking the polynomial exp of its EGF.

void exp(Int G[], Int C[]) {
  for (int i = 1; i <= n; ++i) {
    G[i] = C[i];
    for (int j = 1; j <= i - 1; ++j)
      G[i] += binom[i - 1][j - 1] * C[j] * G[i - j];
  }
}

Now discuss labeled bipartite graph counting.

Let $b_n$ be the number of bipartite graphs with n vertices, and $g_n$ be the number of graphs with $n$ vertices where vertices are 2-colored such that no edges exist between vertices of the same color. Enumerating the number of vertices of one color, we have²:

\[ g_n = \sum_{i=0}^{n} \binom{n}{i}2^{i(n-i)} \]

Next, we establish the relationship between $g_n$ and $b_n$ in two different ways.

Method 1: Double Counting

Let $c_{n, k}$ be the number of bipartite graphs with k connected components. Then we have:

\[ \begin{align} b_n &= \sum_{i=1}^{n} c_{n, i} \\ g_n &= \sum_{i=1}^{n} c_{n, i} 2^i \end{align} \]

Comparing the two expressions for $g_n$ and expanding:

\[ \begin{align} \sum_{i=0}^{n} \binom{n}{i}2^{i(n-i)} &= \sum_{i=1}^{n} c_{n, i} 2^i \\ c_{n, i} &= \sum_{i=0}{n-1} \binom{n-1}{i-1} c_{n, 1}c_{n-i,k-1} \end{align} \]

We can obtain a recurrence for $b_n$ with complexity $O(n^3)$. Further using the inclusion-exclusion principle, it can be optimized to $O(n^2)$ to pass this problem.

Method 2: Connection Recurrence

Methods 2 and 3 both use connected bipartite graphs $b1_n$ A001832 to bridge $g_n$ and $b_n$.

Note that for each connected bipartite graph, there are exactly two different coloring methods, corresponding to two different connected 2-colored graphs. Thus, applying the connection operation to $g_n$ yields a sequence exactly twice $b1_n$, and $b_n$ is obtained by applying the inverse connection operation to $b1_n$.

Therefore:

for (int i = 1; i <= n; ++i) {
  G[i] = 0;
  for (int j = 0; j < i + 1; ++j) G[i] += binom[i][j] * pow(2, j * (i - j));
}
ln(B1, G);
for (int i = 1; i <= n; ++i) B1[i] /= 2;
exp(B, B1);

Both recurrence processes have complexity $O(n^2)$ and can pass this problem.

Method 3: Polynomial exp

We can also understand the above recurrence using EGF.

Let $G(x)$ be the EGF of $g_n$, $B1(x)$ be the EGF of $b1_n$, and $B(x)$ be the EGF of $b_n$. Applying method 2, we have:

\[ \begin{align} G(x) &= \exp(2B1(x)) \\ B(x) &= \exp(B1(x)) \\ &= \exp(\frac{\ln{G(x)}}{2}) \\ &= \sqrt{G} \end{align} \]

We can differentiate both sides and compare coefficients to obtain a recurrence formula suitable for coding, solving this problem. Note that methods 2 and 3 are essentially the same, and method 3 generally yields better time complexity.

$$ \begin{align} B_n^2 &= G \ 2B_nB_n' &= G' \end{align} ```

Reference Code

```cpp

include

using namespace std;

using LL = long long; constexpr int MOD = int(1e9) + 7;

// <<= '2. Number Theory .,//{ namespace NT { void INC(int& a, int b) { a += b; if (a >= MOD) a -= MOD; }

int sum(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; }

void DEC(int& a, int b) { a -= b; if (a < 0) a += MOD; }

int dff(int a, int b) { a -= b; if (a < 0) a += MOD; return a; }

void MUL(int& a, int b) { a = (LL)a * b % MOD; }

int pdt(int a, int b) { return (LL)a * b % MOD; }

int _I(int b) { int a = MOD, x1 = 0, x2 = 1, q; while (1) { q = a / b, a %= b; if (!a) return x2; DEC(x1, pdt(q, x2));

q = b / a, b %= a;
if (!b) return x1;
DEC(x2, pdt(q, x1));

} }

void DIV(int& a, int b) { MUL(a, _I(b)); }

int qtt(int a, int b) { return pdt(a, _I(b)); }

int pow(int a, LL b) { int c(1); while (b) { if (b & 1) MUL(c, a); MUL(a, a), b >>= 1; } return c; }

template T pow(T a, LL b) { T c(1); while (b) { if (b & 1) c = a; a = a, b >>= 1; } return c; }

template T pow(T a, int b) { return pow(a, (LL)b); }

struct Int { int val;

operator int() const { return val; }

Int(int _val = 0) : val(_val) { val %= MOD; if (val < 0) val += MOD; }

Int(LL _val) : val(_val) { _val %= MOD; if (_val < 0) _val += MOD; val = _val; }

Int& operator+=(const int& rhs) { INC(val, rhs); return *this; }

Int operator+(const int& rhs) const { return sum(val, rhs); }

Int& operator-=(const int& rhs) { DEC(val, rhs); return *this; }

Int operator-(const int& rhs) const { return dff(val, rhs); }

Int& operator=(const int& rhs) { MUL(val, rhs); return this; }

Int operator*(const int& rhs) const { return pdt(val, rhs); }

Int& operator/=(const int& rhs) { DIV(val, rhs); return *this; }

Int operator/(const int& rhs) const { return qtt(val, rhs); }

Int operator-() const { return MOD - *this; } };

} // namespace NT

using namespace NT;

constexpr int N = int(1e3) + 9; Int binom[N][N], C[N], E[N], B[N], B1[N], G[N]; int n;

void ln(Int C[], Int G[]) { for (int i = 1; i <= n; ++i) { C[i] = G[i]; for (int j = 1; j <= i - 1; ++j) C[i] -= binom[i - 1][j - 1] * C[j] * G[i - j]; } }

void exp(Int G[], Int C[]) { for (int i = 1; i <= n; ++i) { G[i] = C[i]; for (int j = 1; j <= i - 1; ++j) G[i] += binom[i - 1][j - 1] * C[j] * G[i - j]; } }

int main() { cin.tie(nullptr)->sync_with_stdio(false);

n = 1000; for (int i = 0; i < n + 1; ++i) { binom[i][0] = 1; for (int j = 0; j < i; ++j) binom[i][j + 1] = binom[i - 1][j] + binom[i - 1][j + 1]; }

for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i][2]); ln(C, G); for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i - 1][2]); ln(E, G); for (int i = 1; i <= n; ++i) { G[i] = 0; for (int j = 0; j < i + 1; ++j) G[i] += binom[i][j] * pow(2, j * (i - j)); } ln(B1, G); for (int i = 1; i <= n; ++i) B1[i] /= 2; exp(B, B1);

int T; cin >> T; while (T--) { cin >> n; cout << "Connected: " << C[n] << '\n' << "Eulerian: " << E[n] << '\n' << "Bipartite: " << B[n] << "\n\n"; } }

```

Exercises

Riddell's Formula

The above usage of exp in EGF is sometimes called Riddell's formula for labeled graphs. The Euler transform of generating functions is sometimes called Riddell's formula for unlabeled graphs. The latter first appeared in Euler's study of partition numbers and also appears in the unbounded knapsack problem.

For a given sequence $a_i$ and its corresponding OGF $A(x)$, define the Euler transform of $A(x)$ as:

\[ \begin{align} \mathcal{E}(A(x)) &= \prod_{i} (1-x^i)^{-a_i} \\ &= \exp (\sum_{i} \frac{A(x^i)}{i}) \end{align} \]

Let the coefficients of $\mathcal{E}(A(x))$ be $b_i$, and define an auxiliary array $c_i = \sum_{d|n} d a_d$. Then we have the recurrence formula:

\[ n b_n = c_n + \sum_{i=1}^{n-1} c_i b_{n-i} \]

Unlabeled Trees

Example Problem "SPOJ PT07D" Let us count 1 2 3

Example 「SPOJ PT07D」Let us count 1 2 3

Problem summary: Find the number of trees with n vertices satisfying the following properties.

Labeled rooted trees A000169.
Labeled unrooted trees A000272.
Unlabeled rooted trees A000081.
Unlabeled unrooted trees A000055.

Rooted Trees

The labeled case has been solved earlier. Now consider unlabeled rooted trees. Let their OGF be $F(x)$. Applying the Euler transform, we get:

\[ F(x) = x\mathcal{E}(F(x)) \]

Extract the coefficients.

Unrooted Trees

Consider inclusion-exclusion. We subtract from the rooted tree count those where the root is not the center of gravity, and discuss parity of $n$.

When $n$ is odd:

There must exist a subtree of size $\geq \left\lceil \frac{n}{2}\right\rceil$. Enumerating the size of this subtree:

\[ g_n = f_n - \sum_{i=\left\lceil\frac{n}{2}\right\rceil}^{n-1} f_i f_{n-i} \]

When $n$ is even:

Note that when there are two centers of gravity, the above process subtracts only once, so we need to further subtract:

\[ g_n = f_n - \sum_{i=\left\lceil\frac{n}{2}\right\rceil}^{n-1} f_i f_{n-i} - \binom{f_{\frac{n}{2}}}{2} \]

Example Problem "Luogu P5900" Unlabeled Unrooted Tree Counting

Example 「Luogu P5900」无标号无根树计数

Problem summary: Find the number of unlabeled unrooted trees with n vertices ($n \leq 200000$).

For larger data ranges, the approach is similar: apply the Euler transform and use polynomial templates.

Unlabeled Simple Graphs

Example Problem "SGU 282. Isomorphism" Isomorphism

Example 「SGU 282. Isomorphism」Isomorphism

Problem summary: Find the number of ways to m-color the edges of an unlabeled complete graph with n vertices.

Note that when m = 2, the object is unlabeled simple graphs A000088. Apply Pólya's enumeration theorem:

\[ \frac{1}{|G|}\sum_{g\in G} m^{c(g)} \]

Here, the permutation group $G$ is the edge permutation group generated by the symmetric group on n vertices. However, the brute-force enumeration is $O(n!)$, which cannot pass.

Consider classifying permutations by their cycle structure. Each cycle structure corresponds to an integer partition. We generate partitions using dfs(). The problem then reduces to finding for each partition $p$ the number of corresponding permutations $w(p)$ and the number of cycles $c(p)$ in each class of permutations. The answer is:

\[ \frac{1}{|G|} \sum_{p \in P} w(p) m^{c(p)} \]

Consider $w(p)$. Each partition corresponds to a cyclic arrangement, and partitions of the same size are unordered. Thus:

\[ w(p) = \frac{n!}{\prod_{i}(p_i)\prod_{i}(q_i!)} \]

Here $q_i$ denotes the number of times a partition of size $i$ appears in $p$.

Consider $c(p)$. The cycles on the vertex set affected by $p$ are $|p|$, but the problem involves edge coloring, so we also need to consider the edge permutation generated by the vertex permutation.

If an edge connects vertices in the same cycle of size $p_i$, then the number of cycles generated by the edge is exactly $\left\lfloor \frac{p_i}{2} \right\rfloor$.

If an edge connects vertices in two different cycles of sizes $p_i$ and $p_j$, the length of each cycle is $\operatorname{lcm}(p_i,p_j)$, so the number of cycles generated by the edge is exactly $\frac{p_i p_j}{\operatorname{lcm}(p_i,p_j)} = \gcd(p_i, p_j)$.