Problem 916: Graph Isomorphism Counting

Mathematical Analysis

Graph Isomorphism and Group Actions

Definition. Two simple graphs on vertex set $[n] = \{1, 2, \ldots, n\}$ are isomorphic if there exists a permutation $\pi \in S_n$ mapping edges to edges. The number of non-isomorphic graphs is the number of orbits of $S_n$ acting on the set of all graphs on $[n]$.

Burnside’s Lemma

Theorem (Burnside/Cauchy-Frobenius). Let a group $G$ act on a set $X$. The number of orbits is:

where $X^g = \{x \in X : g \cdot x = x\}$ is the set of elements fixed by $g$.

Proof. Count pairs $(g, x)$ with $g \cdot x = x$ in two ways:

using the orbit-stabilizer theorem $|G| = |\text{Orb}(x)| \cdot |\text{Stab}(x)|$. $\square$

Application to Graphs

Setup. The set $X$ is the collection of all $2^{\binom{n}{2}}$ simple graphs on $[n]$ (each of the $\binom{n}{2}$ possible edges is either present or absent). The group $G = S_n$ acts by permuting vertices.

Theorem. A permutation $\pi \in S_n$ fixes a graph $G$ iff $G$ is invariant under the induced permutation on edges. The number of fixed graphs is $2^{c(\pi)}$, where $c(\pi)$ is the number of orbits of $\pi$ acting on the edge set $\binom{[n]}{2}$.

Proof. The permutation $\pi$ acts on edges by $\pi(\{u,v\}) = \{\pi(u), \pi(v)\}$. A graph is fixed iff for every edge orbit under this action, either all edges in the orbit are present or all are absent. With $c(\pi)$ orbits, there are $2^{c(\pi)}$ choices. $\square$

Computing Edge Orbits from Cycle Type

Theorem. If $\pi$ has cycle type $(\lambda_1, \lambda_2, \ldots, \lambda_k)$ (cycle lengths), then the number of orbits of $\pi$ on $\binom{[n]}{2}$ is:

Proof. Edges come in two types:

1. Inter-cycle edges between cycles $C_i$ and $C_j$: the induced permutation on the $\lambda_i \cdot \lambda_j$ edges between them has orbits of size $\text{lcm}(\lambda_i, \lambda_j)$, giving $\lambda_i \lambda_j / \text{lcm}(\lambda_i, \lambda_j) = \gcd(\lambda_i, \lambda_j)$ orbits.
2. Intra-cycle edges within cycle $C_i$: edges $\{c_r, c_s\}$ within a cycle of length $\lambda_i$ form $\lfloor \lambda_i / 2 \rfloor$ orbits (edges at distance $d$ form one orbit for $1 \leq d \leq \lfloor \lambda_i/2 \rfloor$). $\square$

Polya Enumeration via Cycle Index

Definition. The cycle index of $S_n$ acting on pairs is:

For our problem, we substitute $s_j = 2$ (since each orbit has 2 colorings: edge present or absent):

Grouping by Conjugacy Classes

Theorem. Permutations with the same cycle type contribute equally to the Burnside sum. The number of permutations with cycle type $(\lambda_1^{a_1}, \lambda_2^{a_2}, \ldots)$ is $n! / \prod_i (\lambda_i^{a_i} \cdot a_i!)$.

For $n = 7$, the conjugacy classes (partitions of 7) are:

Total = $\frac{1}{5040}(\text{sum of contributions}) = 1044$.

Known Values (OEIS A000088)

Self-Complementary Graphs

Corollary. The number of self-complementary graphs on $n$ vertices (graphs isomorphic to their complement) can also be computed via Burnside’s lemma by restricting to involutions on the edge set.

Proof of Correctness

1. Burnside’s lemma is a standard result in combinatorics, reducing orbit counting to fixed-point counting.
2. Edge orbit formula correctly decomposes the edge action into inter-cycle and intra-cycle components.
3. Exhaustive verification: Direct computation for $n \leq 6$ matches known values.
4. Conjugacy class enumeration covers all $15$ partitions of $7$, accounting for all $7! = 5040$ permutations.

Complexity Analysis

• By conjugacy classes: $O(p(n) \cdot n)$ where $p(n)$ is the number of partitions (15 for $n=7$).
• By direct permutation: $O(n! \cdot n^2)$, feasible for $n \leq 10$.
• For large $n$: Polynomial-time algorithms exist using the cycle index formulation.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 916: Graph Isomorphism Counting
 *
 * Count non-isomorphic simple graphs on n=7 vertices.
 *
 * Approach: Burnside's lemma with S_n acting on graphs.
 *   count = (1/n!) * sum_{pi in S_n} 2^{c(pi)}
 * where c(pi) = number of edge orbits under pi.
 *
 * For a permutation with cycle type (l1, l2, ...):
 *   c = sum_{i<j} gcd(l_i, l_j) + sum_i floor(l_i / 2)
 *
 * We enumerate partitions of n, compute the contribution of each
 * conjugacy class, and sum.
 *
 * OEIS A000088: 1, 1, 2, 4, 11, 34, 156, 1044, 12346, ...
 */

typedef long long ll;
typedef vector<int> vi;

ll factorial(int n) {
    ll r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

// Number of permutations with given cycle type
ll count_perms(int n, const vi& cycle_type) {
    map<int, int> freq;
    for (int l : cycle_type) freq[l]++;
    ll denom = 1;
    for (auto& [len, cnt] : freq) {
        for (int i = 0; i < cnt; i++) denom *= len;
        denom *= factorial(cnt);
    }
    return factorial(n) / denom;
}

// Number of edge orbits from cycle type
int edge_orbits(const vi& ct) {
    int c = 0;
    int k = ct.size();
    for (int i = 0; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            c += __gcd(ct[i], ct[j]);
        }
        c += ct[i] / 2;
    }
    return c;
}

// Generate all partitions of n
void gen_partitions(int n, int max_val, vi& current, vector<vi>& result) {
    if (n == 0) {
        result.push_back(current);
        return;
    }
    for (int v = min(n, max_val); v >= 1; v--) {
        current.push_back(v);
        gen_partitions(n - v, v, current, result);
        current.pop_back();
    }
}

ll count_graphs(int n) {
    vector<vi> parts;
    vi cur;
    gen_partitions(n, n, cur, parts);

    ll total = 0;
    for (auto& p : parts) {
        int c = edge_orbits(p);
        ll np = count_perms(n, p);
        total += np * (1LL << c);
    }
    return total / factorial(n);
}

int main() {
    int n = 7;
    ll answer = count_graphs(n);
    cout << answer << endl;

    // Verification against known values
    assert(count_graphs(1) == 1);
    assert(count_graphs(2) == 2);
    assert(count_graphs(3) == 4);
    assert(count_graphs(4) == 11);
    assert(count_graphs(5) == 34);
    assert(count_graphs(6) == 156);
    assert(count_graphs(7) == 1044);

    return 0;
}

"""
Problem 916: Graph Isomorphism Counting

Find the number of non-isomorphic simple graphs on 7 vertices.

Key ideas:
    - Burnside's lemma: orbit count = (1/|G|) * sum of fixed points.
    - G = S_n acts on graphs by permuting vertices.
    - A permutation pi fixes 2^{c(pi)} graphs, where c(pi) = number of
      orbits of pi on the edge set.
    - c(pi) depends only on the cycle type of pi.
    - For cycle type (l1, l2, ...):
        c = sum_{i<j} gcd(li, lj) + sum_i floor(li/2)

Methods:
    1. Direct Burnside: enumerate all n! permutations
    2. Cycle-type Burnside: group by conjugacy classes (partitions of n)
    3. Verification against OEIS A000088
"""

from itertools import permutations
from math import factorial, gcd
from collections import Counter

def count_graphs_direct(n: int) -> int:
    """Count non-isomorphic graphs on n vertices via direct Burnside."""
    edges = [(i, j) for i in range(n) for j in range(i + 1, n)]
    m = len(edges)
    edge_idx = {e: i for i, e in enumerate(edges)}

    total = 0
    for perm in permutations(range(n)):
        # Find orbits of perm acting on edges
        visited = [False] * m
        cycles = 0
        for i in range(m):
            if not visited[i]:
                cycles += 1
                j = i
                while not visited[j]:
                    visited[j] = True
                    u, v = edges[j]
                    pu, pv = perm[u], perm[v]
                    if pu > pv:
                        pu, pv = pv, pu
                    j = edge_idx[(pu, pv)]
        total += 2 ** cycles
    return total // factorial(n)

def partitions(n: int, max_val=None):
    """Generate all partitions of n (as sorted tuples, descending)."""
    if max_val is None:
        max_val = n
    if n == 0:
        yield ()
        return
    for first in range(min(n, max_val), 0, -1):
        for rest in partitions(n - first, first):
            yield (first,) + rest

def edge_orbits_from_cycle_type(cycle_type: tuple) -> int:
    """Number of edge orbits for a permutation with given cycle type.

    Formula: sum_{i<j} gcd(l_i, l_j) + sum_i floor(l_i / 2)
    """
    k = len(cycle_type)
    c = 0
    # Inter-cycle edges
    for i in range(k):
        for j in range(i + 1, k):
            c += gcd(cycle_type[i], cycle_type[j])
    # Intra-cycle edges
    for li in cycle_type:
        c += li // 2
    return c

def count_perms_with_cycle_type(n: int, cycle_type: tuple) -> int:
    """Number of permutations in S_n with given cycle type."""
    # n! / prod(l_i^a_i * a_i!) where a_i = multiplicity of cycle length l_i
    freq = Counter(cycle_type)
    denom = 1
    for length, count in freq.items():
        denom *= (length ** count) * factorial(count)
    return factorial(n) // denom

def count_graphs_cycle_type(n: int) -> int:
    """Count non-isomorphic graphs via cycle-type Burnside."""
    total = 0
    for part in partitions(n):
        c = edge_orbits_from_cycle_type(part)
        num_perms = count_perms_with_cycle_type(n, part)
        total += num_perms * (2 ** c)
    return total // factorial(n)

# Solve
answer = count_graphs_cycle_type(7)

# Verify with direct method for small n
for n in range(1, 7):
    assert count_graphs_direct(n) == count_graphs_cycle_type(n), \
        f"Mismatch at n={n}: {count_graphs_direct(n)} vs {count_graphs_cycle_type(n)}"

# OEIS A000088 verification
oeis = {0: 1, 1: 1, 2: 2, 3: 4, 4: 11, 5: 34, 6: 156, 7: 1044}
for n, expected in oeis.items():
    if n >= 1:
        assert count_graphs_cycle_type(n) == expected, f"n={n}: got {count_graphs_cycle_type(n)}"

print(answer)