Preface

How many ways are there to connect ten cities by roads so that no road is wasted? How many different molecules can be built from six carbon atoms? How many friendship networks on twenty people contain no three mutual friends, and what is the largest number of friendships such a network can have? Each of these is a question about graphs, and each asks for a number. This book is about such questions and about the many different things that can count as their answers.

Graph theory began with a counting flavour. Euler’s solution of the Königsberg bridges problem in 1736 is a parity argument, which is counting modulo \(2\). Cayley’s work on trees in the nineteenth century was motivated by counting molecules. Pólya’s theorem of 1937 turned the counting of objects up to symmetry into an algebraic machine. Since then the subject has grown in two directions at once: towards deep exact formulas, and towards estimates and bounds for numbers that have no formula at all.

The classical reference on counting graphs, Harary and Palmer’s Graphical Enumeration, appeared in 1973 and concentrates on Pólya’s method. Many of the ideas that a student meets today, such as the Matrix-Tree Theorem in its modern forms, the exponential formula, random graphs and the probabilistic method, and the extremal theorems of Turán and Ramsey, are scattered among books on combinatorics, algebraic graph theory and probability. We wanted one book in which they meet, and in which the reader can watch the same question receive different kinds of answers.

What counts as an answer?

Herbert Wilf once asked what it means to answer a counting question. A closed formula such as \(n^{n-2}\) is the answer everyone hopes for, but it is rare. A recurrence may be just as useful if it lets us compute the numbers quickly. A generating function packs an infinite sequence into one equation. An asymptotic formula tells us how fast the numbers grow when no exact formula is known. And sometimes the right question is not “how many?” but “how many at most?”, and the answer is an inequality that cannot be improved.

This observation decides the order of our chapters. Chapter 1 sets up the language. Chapters 2 and 3 look for explicit formulas, first with elementary tools and then with linear algebra and group actions. Chapter 4 looks for recurrences, Chapter 5 for generating functions, Chapter 6 for estimates, and Chapter 7 for extremal values. Two problems, the counting of trees and the counting of connected graphs, travel through every chapter, so that the reader can see one question answered in five ways.

Who this book is for

The book is written for undergraduate and graduate students of mathematics and computer science, for students preparing for mathematical and informatics olympiads, and for young researchers who want to find a problem of their own. We assume only what a first course in discrete mathematics provides: sets, functions, induction and a little linear algebra. Everything else, including the facts about groups, probability and power series that we use, is explained when it is needed or collected in the appendices.

A book with two editions

This book is published as an e-book in two editions built from one source. The web edition, at mbooks.arith.land, is interactive: every key term shows its definition when you point at it, every program can be run, many sections contain small laboratories in which you can change a number and watch the answer change, and some theorems come with a short recorded comment by one of the authors. The PDF edition is laid out for a tablet held sideways, with history and quotations in a wide margin, as in our earlier e-books. Both editions contain the same mathematics.

Every chapter ends with exercises of several kinds, marked by tags: purely mathematical exercises, problems from mathematical and informatics olympiads, algorithmic and programming tasks, and research projects divided into small steps. Many exercises have hints that can be opened one at a time and an answer that can be checked without being revealed. The Research threads scattered through the text describe open problems, with their status at the time of writing and a concrete first step. We hope that some readers will take one of these steps and keep walking.

Some sections describe results from our own papers. Those that have not yet been accepted for publication are cited as preprints, and the citations will be updated as the refereeing process ends.

Acknowledgements

[To be written by the authors.]

Our books change with the comments of their readers, and every later version owes much to the readers of the earlier one. We look forward to your corrections and suggestions, always.

Madjid Mirzavaziri, Ferdowsi University of Mashhad Daniel Yaqubi, University of Torbat-e Jam 2026

How to use this book

This short section explains how the book is organised and how its parts are marked. A reader who prefers to start at once can go straight to Chapter 1 and come back here when a symbol or a box needs explaining.

The map of the book

Numbered blocks

Definitions, theorems, lemmas, propositions, corollaries, examples and remarks share one counter in each section, as in our earlier books: Definition 1.2.1 may be followed by Theorem 1.2.2 and Example 1.2.3. This makes every numbered block easy to find. Definitions end with the mark \(\clubsuit\), examples with \(\spadesuit\), remarks with \(\diamondsuit\), and proofs with \(\blacksquare\).

What sits in the margin

The margin holds three kinds of notes, always next to the paragraph they belong to: a short portrait of a mathematician when his or her name first appears, a historical note, and a quotation. Nothing in the margin is needed to follow the mathematics, but we hope it shows that every theorem was found by a person, at a time, for a reason.

Boxes in the text

• One number, many proofs connects a count to its other appearances in the book. These boxes follow the two running problems: trees and connected graphs.
• Research thread describes a problem that is open or only partly solved, gives its status with a date, and suggests a first step.
• From the authors’ research explains where one of our own papers fits, and says whether it is a preprint or published.
• Lab marks an interactive laboratory of the web edition. In the PDF edition the box tells you what the laboratory does.

Exercises

Each exercise carries one or more tags:

Hints are numbered and, in the web edition, open one at a time; try the problem again after each hint. When an exercise has a numerical answer, the web edition lets you check your number without seeing the answer. The PDF edition collects hints and answers at the end of each chapter.

Code

Programs are written in plain Python 3 so that they run anywhere: in the web edition, in SageMathCell, or on your own computer. We prefer short, transparent programs to fast ones; the exercises tagged Algorithm ask you to make them fast. Appendix C collects every program in the book.

Paths through the book

• A one-semester undergraduate course: Chapters 1–4 and Sections 7.1–7.4.
• A graduate course: a quick review of Chapter 1, then Chapters 3–7.
• Olympiad training: Chapters 1 and 2, Section 4.2 and Chapter 7, with the exercises tagged Math Olympiad and Informatics Olympiad.
• Towards research: any chapter, followed by its research threads and the exercises tagged Research Project.

Notation

The symbols below are used throughout the book. Each is defined again where it first appears; this page is for quick reference.

A path \(P_n\) has \(n\) vertices and \(n-1\) edges, and a cycle \(C_n\) has \(n\) vertices and \(n\) edges. (The 2014 Persian edition wrote \(P_{n+1}\) for the path of length \(n\); we now index paths by their order, as most recent books do.) Logarithms without a base are natural logarithms.

Chapter 1 · Prerequisites: Graphs and Counting

1.1 Graphs, digraphs and multigraphs

Many problems in mathematics are easier to think about once we draw a picture. In geometry the picture keeps lengths and angles; in a Venn diagram it keeps only which sets contain which elements. There are problems where neither is enough, because what matters is a relation between objects: which people in a group are friends, which cities are joined by a direct flight, which atoms in a molecule are bonded, which web pages link to which. For such problems we draw a dot for each object and a line between two dots whenever the two objects are related. How long the line is, whether it is straight or curved, and where the dots are placed do not matter at all.

This simple idea is the idea of a graph. In this section we turn it into a definition precise enough to count with.

Because \(E\) is a multiset, two vertices may be joined by several edges, called parallel edges; and because an edge may have one element, a vertex may be joined to itself by a loop. A graph without loops and parallel edges is called simple. Throughout this book graphs are finite and simple unless we say otherwise. Vertices are also called nodes and edges lines.

The first graph problem on record is the problem of the seven bridges of Königsberg, solved by Euler in 1736. The four land masses of the town become four vertices and the seven bridges become seven edges, two pairs of them parallel. Euler asked whether one can walk across every bridge exactly once. We will answer the question in Section 2.8; for the moment notice that it already needs multigraphs.

Some relations have a direction: \(a\) is a parent of \(b\), \(a\) beat \(b\) in a match, page \(a\) links to page \(b\). For these we use arrows instead of lines.

Our first theorem is the oldest counting argument in graph theory. It counts one set in two ways, a technique called double counting that we will use again and again.

A first count

How many simple graphs are there on the vertex set \([n]=\{1,2,\ldots,n\}\)? A simple graph is decided by choosing, for each of the \(\binom n2\) pairs of vertices, whether the pair is an edge. These choices are independent, so the product rule gives the answer.

For \(n=1,2,\ldots,6\) the first number is \(1, 2, 8, 64, 1024, 32768\). These graphs are different as pairs \((V,E)\), but many of them have the same drawing up to renaming the vertices: of the \(8\) graphs on \([3]\), three are a single edge and three are a path. Section 1.3 makes this distinction precise; it is the most important distinction in the book.

from itertools import combinations
from collections import Counter

def all_graphs(n):
    """Every simple graph on 1..n, as a list of edges."""
    pairs = list(combinations(range(1, n + 1), 2))
    for mask in range(1 << len(pairs)):
        yield [pairs[i] for i in range(len(pairs)) if mask >> i & 1]

def degrees(n, edges):
    d = {v: 0 for v in range(1, n + 1)}
    for u, v in edges:
        d[u] += 1; d[v] += 1
    return d

for n in range(1, 6):
    by_size = Counter()
    for E in all_graphs(n):
        assert sum(degrees(n, E).values()) == 2 * len(E)   # the handshake lemma
        by_size[len(E)] += 1
    print(n, sum(by_size.values()), [by_size[m] for m in range(n * (n - 1) // 2 + 1)])

The program lists all graphs on \([n]\) for \(n\leqslant5\), checks the handshake lemma for each of them, and prints how many there are of each size. For \(n=4\) the row is \(1, 6, 15, 20, 15, 6, 1\), the binomial coefficients \(\binom 6m\), as Proposition 1.1.8 predicts.

Exercises

1.2 Walks, paths and connectivity

Once we have a graph we want to move around in it: from a city to another city along roads, from a person to a stranger through a chain of friends. This section makes such movement precise and introduces the first measurements of a graph: distance, radius and diameter.

Every path is a trail, because a repeated edge would bring its ends twice. The converse fails: the trail \(1,2,3,4,2,5\) in a graph made of a triangle \(234\) with two pendant edges \(12\) and \(25\) visits \(2\) twice.

Bridges and bipartite graphs

from collections import deque

def bfs(adj, s):
    """Distances from s to every vertex reachable from s."""
    dist = {s: 0}
    q = deque([s])
    while q:
        v = q.popleft()
        for u in adj[v]:
            if u not in dist:
                dist[u] = dist[v] + 1
                q.append(u)
    return dist

def measures(adj):
    ecc = {v: max(bfs(adj, v).values()) for v in adj}
    r, d = min(ecc.values()), max(ecc.values())
    return r, d, sorted(v for v in adj if ecc[v] == r)

def bipartition(adj):
    """Return the two sides, or None if there is an odd cycle (connected graphs)."""
    dist = bfs(adj, next(iter(adj)))
    if any((dist[u] - dist[v]) % 2 == 0 for v in adj for u in adj[v]):
        return None
    return [v for v in adj if dist[v] % 2 == 0], [v for v in adj if dist[v] % 2]

def path(n): return {v: [u for u in (v - 1, v + 1) if 1 <= u <= n] for v in range(1, n + 1)}

petersen = {i: [] for i in range(10)}
for i in range(5):
    for a, b in ((i, (i + 1) % 5), (i, i + 5), (i + 5, (i + 2) % 5 + 5)):
        petersen[a].append(b); petersen[b].append(a)

print("P6:", measures(path(6)), bipartition(path(6)))
print("P7:", measures(path(7)))
print("Petersen:", measures(petersen)[:2], "bipartite:", bipartition(petersen) is not None)

The program computes distances by breadth-first search, the standard method for unweighted graphs, and prints radius, diameter and centre. It confirms Example 1.2.9 for \(P_6\) and \(P_7\) and finds that the Petersen graph of Section 1.5 has radius and diameter \(2\) and is not bipartite.

Exercises

1.3 Labeled and unlabeled

Draw a path on three vertices and label its middle vertex \(1\); then draw it again with the label \(2\) in the middle. As pairs \((V,E)\) the two graphs are different: one has the edge \(\{1,3\}\) and the other does not. As shapes they are the same. Counting problems come in two kinds according to which of these two points of view we take, and mixing them is the most common mistake in enumeration.

An isomorphism preserves adjacency and non-adjacency. A bijective homomorphism need not be an isomorphism: the identity map from the empty graph on \([2]\) to \(K_2\) is a bijective homomorphism.

The classes of this relation are called unlabeled graphs or isomorphism types. When we speak of “the graphs on \(n\) vertices” without naming the vertices, we mean the types; when the vertex set is a fixed set such as \([n]\), we mean the labeled graphs on that set. The counts behave very differently:

The second row has no closed formula; Pólya’s theorem in Chapter 3 gives a method to compute it. The bridge between the rows is the following theorem.

The bound of Corollary 1.3.5 is far from sharp for small \(n\) but correct in the limit: Erdős and Rényi showed that almost all graphs are asymmetric, that is, \(|\mathrm{Aut}(G)|=1\), and as a consequence \(g_n\sim2^{\binom n2}/n!\). We prove this in Chapter 6. The smallest asymmetric graphs have \(6\) vertices, and there are eight of them (Exercise 1.3.3).

from itertools import combinations, permutations
from math import factorial

def canon(n, edges, perms):
    """The lexicographically smallest relabeling: equal for isomorphic graphs."""
    return min(tuple(sorted(tuple(sorted((p[u], p[v]))) for u, v in edges)) for p in perms)

def automorphisms(n, edges, perms):
    E = {frozenset(e) for e in edges}
    return sum(all(frozenset((p[u], p[v])) in E for u, v in edges) for p in perms)

for n in range(1, 6):
    perms = list(permutations(range(n)))
    pairs = list(combinations(range(n), 2))
    types = {}
    for mask in range(1 << len(pairs)):
        E = [pairs[i] for i in range(len(pairs)) if mask >> i & 1]
        types.setdefault(canon(n, E, perms), E)
    total = sum(factorial(n) // automorphisms(n, E, perms) for E in types.values())
    print(f"n={n}: {len(types)} unlabeled graphs; sum of n!/|Aut| = {total} = 2^C(n,2) = {2 ** len(pairs)}")

The program finds one representative of every isomorphism type for \(n\leqslant5\) by computing a canonical form, the smallest edge list over all relabelings, and then checks Theorem 1.3.3 by adding \(n!/|\mathrm{Aut}(G)|\) over the types. Trying all \(n!\) relabelings is hopeless beyond \(n\approx10\); Exercise 1.3.5 asks why, and Chapter 3 counts the types without listing them.

Exercises

1.4 Subgraphs and operations

A set has subsets; a graph has subgraphs. Because a graph has two kinds of elements, vertices and edges, there are several natural ways to take a part of it, and each gives its own counting problem.

The counts are immediate: \(G\) has \(2^{|E|}\) spanning subgraphs, one for each set of edges, and \(2^{|V|}\) induced subgraphs, one for each set of vertices. Counting the subgraphs that have a given property, for example the connected spanning subgraphs or the spanning trees, is where the real work begins.

Thus a triangle-free graph has no triangle at all, since a triangle in a graph is always induced. A square-free graph in this induced sense may contain a \(4\)-cycle, but every \(4\)-cycle in it has a chord. In extremal graph theory (Chapter 7) “\(H\)-free” often means “no subgraph isomorphic to \(H\)”; we will say so when we use that meaning.

For example \(K_{m,n}=\overline{K_m}+\overline{K_n}\), the wheel is \(W_n=C_n+K_1\), the grid is \(P_m\,\square\,P_n\), and the hypercube satisfies \(Q_n=Q_{n-1}\,\square\,K_2\). Many counting problems become easier for graphs built from smaller ones by these operations; the number of spanning trees of a product is a famous example (Chapter 3).

Can a graph be counted from its parts?

Give someone the \(n\) vertex-deleted subgraphs \(G-v\) of a graph \(G\), as unlabeled graphs, without saying which vertex was deleted from which. This multiset is the deck of \(G\) and its members are the cards. Does the deck determine \(G\)? The following lemma of Kelly shows that it determines a great deal, and its proof is pure double counting.

from itertools import combinations
import random

def triangles(V, E):
    return sum(1 for a, b, c in combinations(sorted(V), 3) if {(a, b), (a, c), (b, c)} <= E)

random.seed(1)
n = 9
V = set(range(n))
E = {(a, b) for a, b in combinations(range(n), 2) if random.random() < 0.5}

deck_sum = 0
for v in V:                                   # the card G - v
    Vv = V - {v}
    Ev = {e for e in E if v not in e}
    deck_sum += triangles(Vv, Ev)

print("triangles in G:", triangles(V, E))
print("from the deck: ", deck_sum / (n - 3))  # Kelly's lemma with H = K3

The program builds a random graph on \(9\) vertices and recovers its number of triangles from its nine cards, as Lemma 1.4.7 with \(H=K_3\) promises.

Exercises

1.5 A gallery of graphs

Before counting anything in general it pays to know a collection of well-understood graphs by heart. They test our definitions, suggest conjectures and supply counterexamples. This section is a small gallery; for each graph we give its order, size and number of automorphisms, which by Theorem 1.3.3 determines how many labeled copies it has.

With \(n=n_1+\cdots+n_r\), a vertex in the \(i\)-th class has degree \(n-n_i\), so by the handshake lemma \(K_{n_1,\ldots,n_r}\) has \(\frac12\sum_i n_i(n-n_i)=\sum_{i<j}n_in_j\) edges.

A cycle through every vertex of a graph is called a Hamiltonian cycle after Hamilton’s game. The cycle constructed in Theorem 1.5.5 is the reflected binary Gray code, used in engineering to list binary words so that consecutive words differ in one digit.

The table collects the data of the gallery. The last column is the number of labeled copies on a fixed vertex set, computed with Theorem 1.3.3.

from itertools import combinations

def automorphism_count(adj):
    """Count automorphisms by extending a partial map one vertex at a time."""
    V = sorted(adj)
    nbr = {v: set(adj[v]) for v in V}
    def extend(i, f, used):
        if i == len(V):
            return 1
        v, total = V[i], 0
        for w in V:
            if w in used or len(nbr[w]) != len(nbr[v]):
                continue
            if all((u in nbr[v]) == (f[u] in nbr[w]) for u in V[:i]):
                f[v] = w; used.add(w)
                total += extend(i + 1, f, used)
                del f[v]; used.discard(w)
        return total
    return extend(0, {}, set())

def from_edges(V, E):
    adj = {v: [] for v in V}
    for a, b in E:
        adj[a].append(b); adj[b].append(a)
    return adj

pairs = [frozenset(p) for p in combinations(range(1, 6), 2)]
gallery = {
    "K5": from_edges(range(5), combinations(range(5), 2)),
    "C6": from_edges(range(6), [(i, (i + 1) % 6) for i in range(6)]),
    "W5": from_edges(range(6), [(i, (i + 1) % 5) for i in range(5)] + [(i, 5) for i in range(5)]),
    "Q3": from_edges(range(8), [(x, x ^ (1 << k)) for x in range(8) for k in range(3) if x < x ^ (1 << k)]),
    "Petersen": from_edges(pairs, [(p, q) for p, q in combinations(pairs, 2) if not p & q]),
}
for name, adj in gallery.items():
    n = len(adj); m = sum(map(len, adj.values())) // 2
    print(f"{name:9} order {n:2}  size {m:2}  |Aut| = {automorphism_count(adj)}")

The program counts automorphisms by building them vertex by vertex and abandoning a partial map as soon as it breaks an adjacency. It confirms the table for \(K_5\), \(C_6\), \(W_5\), \(Q_3\) and the Petersen graph in a fraction of a second, although the Petersen graph has \(10!=3\,628\,800\) permutations.

Exercises

1.6 Trees and forests

Trees are the simplest connected graphs and the most counted ones. Two of the running problems of this book are about trees, so we collect their basic properties carefully.

Here are the first counts. Labeled trees on \([n]\) are counted by Cayley’s formula \(n^{n-2}\), proved in Section 2.4. Unlabeled trees have no closed formula; their numbers are found by Otter’s recursion in Chapter 4.

def canonical(adj, root, parent=None):
    """AHU code of the subtree at root: equal codes mean isomorphic rooted trees."""
    return "(" + "".join(sorted(canonical(adj, c, root) for c in adj[root] if c != parent)) + ")"

def centre(adj):
    layer = [v for v in adj if len(adj[v]) <= 1]
    deg = {v: len(adj[v]) for v in adj}
    left = len(adj)
    while left > 2:
        nxt = []
        for v in layer:
            left -= 1
            for u in adj[v]:
                deg[u] -= 1
                if deg[u] == 1:
                    nxt.append(u)
        layer = nxt
    return layer

def tree_code(adj):
    """Canonical form of an unrooted tree: root it at its centre (Jordan's theorem)."""
    return min(canonical(adj, c) for c in centre(adj))

def trees_from_pruefer(n):
    """Decode every Pruefer word (Section 2.4) to get every labeled tree on 1..n."""
    from itertools import product
    for word in product(range(1, n + 1), repeat=n - 2):
        word = list(word)
        degree = {v: 1 for v in range(1, n + 1)}
        for a in word:
            degree[a] += 1
        adj = {v: [] for v in range(1, n + 1)}
        for a in word:
            leaf = min(v for v in degree if degree[v] == 1)
            adj[leaf].append(a); adj[a].append(leaf)
            degree[leaf] = 0; degree[a] -= 1
        u, v = [x for x in degree if degree[x] == 1]
        adj[u].append(v); adj[v].append(u)
        yield adj

for n in range(3, 9):
    codes = {tree_code(adj) for adj in trees_from_pruefer(n)}
    print(n, "labeled:", n ** (n - 2), " unlabeled:", len(codes))

The program generates all labeled trees for \(n\leqslant8\) and sorts them into isomorphism types. To decide when two trees are isomorphic it roots each tree at its centre, which is legitimate by Theorem 1.6.5, and computes the AHU code of Aho, Hopcroft and Ullman: a leaf is “()”, and a vertex is its children’s codes, sorted and wrapped in brackets. The output reproduces the second row of the table up to \(n=8\).

Exercises

1.7 The objects we count

A graph is a stage on which many kinds of structures live: sets of edges that do not touch, sets of vertices that do not see each other, ways of colouring, ways of walking. Almost every counting question in this book asks how many structures of one of these kinds a graph carries. This section introduces them and computes the answer for the simplest graphs; the rest of the book is about the harder graphs.

That \(P(G,k)\) is a polynomial in \(k\) is not obvious; Chapter 2 proves it with inclusion–exclusion and Chapter 4 with deletion–contraction. For simple graphs we can compute it directly.

The complete graph \(K_n\) has \((n-1)!/2\) Hamiltonian cycles, by Example 1.3.4, and every graph with \(m\) edges has \(2^m\) orientations. Here are the counts for three small graphs, computed by the program below. Each row of the table is a separate problem that the later chapters solve in general.

from itertools import combinations

def graph(V, E):
    adj = {v: set() for v in V}
    for a, b in E:
        adj[a].add(b); adj[b].add(a)
    return adj

def perfect_matchings(adj, left=None):
    left = set(adj) if left is None else left
    if not left:
        return 1
    v = min(left)
    return sum(perfect_matchings(adj, left - {v, u}) for u in adj[v] & left)

def independent_sets(adj, left=None):
    left = sorted(adj) if left is None else left
    if not left:
        return 1
    v, rest = left[0], left[1:]
    return independent_sets(adj, rest) + independent_sets(adj, [u for u in rest if u not in adj[v]])

def colourings(adj, k):
    V, colour = sorted(adj), {}
    def go(i):
        if i == len(V):
            return 1
        total = 0
        for c in range(k):
            if all(colour.get(u) != c for u in adj[V[i]]):
                colour[V[i]] = c; total += go(i + 1); del colour[V[i]]
        return total
    return go(0)

def spanning_trees(adj):
    V = sorted(adj); E = [(a, b) for a in V for b in adj[a] if a < b]
    count = 0
    for S in combinations(E, len(V) - 1):
        parent = {v: v for v in V}
        def find(x):
            while parent[x] != x:
                x = parent[x]
            return x
        ok = True
        for a, b in S:
            ra, rb = find(a), find(b)
            if ra == rb:
                ok = False; break
            parent[ra] = rb
        count += ok
    return count

def hamiltonian_cycles(adj):
    V = sorted(adj); s = V[0]; found = 0
    def go(v, seen):
        nonlocal found
        if len(seen) == len(V):
            found += s in adj[v]; return
        for u in adj[v] - seen:
            go(u, seen | {u})
    go(s, {s})
    return found // 2

def acyclic_orientations(adj):
    # Stanley's theorem (Exercise 1.7.7): |P(G, -1)|, computed here by deletion-contraction.
    def chrom(V, E, k):
        if not E:
            return k ** len(V)
        (a, b), rest = E[0], E[1:]
        merged = {tuple(sorted((a if x == b else x, a if y == b else y))) for x, y in rest}
        merged = sorted(e for e in merged if e[0] != e[1])
        return chrom(V, rest, k) - chrom(V - {b}, merged, k)
    E = sorted((a, b) for a in adj for b in adj[a] if a < b)
    return abs(chrom(set(adj), E, -1))

C6 = graph(range(6), [(i, (i + 1) % 6) for i in range(6)])
Q3 = graph(range(8), [(x, x ^ (1 << k)) for x in range(8) for k in range(3) if x < x ^ (1 << k)])
P = graph(range(10), [(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
          + [(i + 5, (i + 2) % 5 + 5) for i in range(5)])
for name, G in (("C6", C6), ("Q3", Q3), ("Petersen", P)):
    print(f"{name:9}", perfect_matchings(G), independent_sets(G), colourings(G, 3),
          spanning_trees(G), hamiltonian_cycles(G), acyclic_orientations(G))

Every function in the program is a brute-force search, and each would take astronomically long on a graph with a few hundred vertices. Some of these counts have fast algorithms (spanning trees, through the Matrix-Tree Theorem of Chapter 3) and some almost certainly do not (perfect matchings in general graphs and Hamiltonian cycles, Chapter 6). Telling the two kinds apart is part of what it means to answer a counting question.

Exercises

1.8 The counting toolkit

This section collects the elementary counting principles that we use without comment in the rest of the book. Most readers have met them; we state them in the language of graphs so that the examples are already of the right kind.

The handshake lemma (Theorem 1.1.5) is double counting with \(A=V\), \(B=E\) and \(R\) the incidence relation; the count of labeled copies (Theorem 1.3.3) is the product rule applied to permutations; and Exercise 1.1.1 is the pigeonhole principle. Here is one more example of double counting, which has a graph in disguise.

Words, sets and multisets

The twelvefold way

Place \(k\) balls into \(n\) boxes. The balls may be distinguishable (labeled) or not, the boxes may be distinguishable or not, and we may require nothing, at most one ball per box (injective), or at least one ball per box (surjective). The twelve answers are:

Here \(S(k,n)\) is the Stirling number of the second kind, the number of partitions of a \(k\)-set into \(n\) non-empty blocks (Section 1.9); \(p_i(k)\) is the number of partitions of \(k\) into exactly \(i\) parts; and \([k\leqslant n]\) is \(1\) if \(k\leqslant n\) and \(0\) otherwise. The labeled/unlabeled distinction of Section 1.3 is visible in every column. Graph theory supplies a natural reading of each entry: for instance, colouring the vertices of \(\overline{K_k}\) with \(n\) colours, all of them used, is the top right entry.

from itertools import product
from math import comb, factorial
from functools import lru_cache

@lru_cache(None)
def S(k, n):           # Stirling numbers of the second kind
    if k == n: return 1
    if n == 0 or n > k: return 0
    return n * S(k - 1, n) + S(k - 1, n - 1)

@lru_cache(None)
def p_exact(k, i):     # partitions of k into exactly i parts
    if k == 0 and i == 0: return 1
    if k <= 0 or i <= 0: return 0
    return p_exact(k - 1, i - 1) + p_exact(k - i, i)

def formulas(k, n):
    fall = factorial(n) // factorial(n - k) if k <= n else 0
    return [n ** k, fall, factorial(n) * S(k, n),
            comb(n + k - 1, k), comb(n, k), comb(k - 1, n - 1) if k >= 1 else int(n == 0),
            sum(S(k, i) for i in range(n + 1)), int(k <= n), S(k, n),
            sum(p_exact(k, i) for i in range(n + 1)), int(k <= n), p_exact(k, n)]

def brute(k, n):
    maps = list(product(range(n), repeat=k))          # ball -> box
    inj = [f for f in maps if len(set(f)) == k]
    sur = [f for f in maps if len(set(f)) == n]
    def u_balls(fs): return {tuple(sorted(f)) for f in fs}                    # forget ball labels
    def u_boxes(fs):                                                         # forget box labels
        return {frozenset(frozenset(b for b in range(k) if f[b] == x) for x in range(n)) - {frozenset()} for f in fs}
    def u_both(fs): return {tuple(sorted(len(blk) for blk in part)) for part in u_boxes(fs)}
    out = []
    for kind in (lambda fs: fs, u_balls, u_boxes, u_both):
        out += [len(set(map(tuple, kind(fs))) if kind is not u_boxes else kind(fs)) for fs in (maps, inj, sur)]
    return out

for k in range(0, 5):
    for n in range(1, 5):
        assert formulas(k, n) == brute(k, n), (k, n)
print("all twelve formulas agree with brute force for k <= 4, n <= 4")
print("k=4, n=3:", formulas(4, 3))

Exercises

1.9 Classical numbers

A small number of sequences appear again and again when we count graphs. Each of them counts a family of graphs directly, and knowing these graph models is often the quickest way to recognise a sequence when it appears in a new problem. This section is a reference; the proofs are short, and many are left as exercises.

Binomial and multinomial coefficients

We have met \(\binom nk\) as the number of graphs on \([n]\) that are a clique on \(k\) vertices plus isolated vertices, and \(\binom{\binom n2}{m}\) as the number of graphs with \(m\) edges. The basic identities are Pascal’s rule \(\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}\), the binomial theorem \((x+y)^n=\sum_k\binom nkx^ky^{n-k}\) and Vandermonde’s identity \(\binom{m+n}{k}=\sum_i\binom mi\binom n{k-i}\). Vandermonde’s identity counts \(k\)-subsets of the vertices of the disjoint union \(\overline{K_m}\cup\overline{K_n}\) according to how many vertices they take from each part.

Stirling numbers and Bell numbers

Graph models. A partition of \([n]\) is the same thing as a cluster graph on \([n]\), a disjoint union of cliques: the blocks are the cliques. So \(B_n\) counts the cluster graphs on \([n]\) and \(S(n,k)\) those with \(k\) components, and \(p(n)\) counts the cluster graphs on \(n\) vertices up to isomorphism. A permutation \(\sigma\) of \([n]\) is the same as its functional digraph, with an arc \(i\to\sigma(i)\) for every \(i\); this digraph is a disjoint union of directed cycles, and \(c(n,k)\) counts those with \(k\) cycles.

Catalan, Fibonacci, Eulerian and derangement numbers

The Catalan numbers \(\mathrm{Cat}_n=\frac1{n+1}\binom{2n}{n}\) count binary plane trees with \(n\) internal vertices (each internal vertex has an ordered left and right child), plane trees with \(n+1\) vertices, and triangulations of a convex \((n+2)\)-gon, which are maximal sets of non-crossing diagonals. They satisfy \(\mathrm{Cat}_{n+1}=\sum_{i=0}^{n}\mathrm{Cat}_i\,\mathrm{Cat}_{n-i}\): split a binary plane tree at its root.

The Fibonacci numbers \(F_1=F_2=1\), \(F_{n}=F_{n-1}+F_{n-2}\) count the independent sets of the path \(P_{n-2}\) (Exercise 1.7.3) and the perfect matchings of the ladder \(P_2\,\square\,P_{n-1}\).

The Eulerian number \(A(n,k)\) counts permutations of \([n]\) with exactly \(k\) descents, positions \(i\) with \(\sigma(i)>\sigma(i+1)\). In graph language: label the vertices of the path \(P_n\), taken in their natural order, by \(1,\ldots,n\) in some order, and orient every edge towards its larger label; \(A(n,k)\) counts the labelings in which exactly \(k\) edges point backwards. They satisfy \(A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)\).

A derangement is a permutation with no fixed point; in graph language, a functional digraph with no loop, or a covering of the vertices of \(K_n\) by disjoint directed cycles of length at least \(2\). Their number is \(D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}\), which we prove by inclusion–exclusion in Chapter 2, and it satisfies \(D_n=(n-1)(D_{n-1}+D_{n-2})\).

from math import comb, factorial
from itertools import combinations

def table(rows, rule):
    T = [[1]]
    for n in range(1, rows):
        prev = T[-1] + [0]
        T.append([rule(n, k, prev) for k in range(n + 1)])
    return T

S = table(9, lambda n, k, p: (k * p[k] if k < len(p) else 0) + (p[k - 1] if k else 0))
c = table(9, lambda n, k, p: ((n - 1) * p[k] if k < len(p) else 0) + (p[k - 1] if k else 0))
bell = [sum(row) for row in S]
catalan = [comb(2 * n, n) // (n + 1) for n in range(9)]
derange = [round(factorial(n) * sum((-1) ** i / factorial(i) for i in range(n + 1))) for n in range(9)]

def partitions(n, largest=None):
    largest = n if largest is None else largest
    if n == 0: return 1
    return sum(partitions(n - j, j) for j in range(1, min(n, largest) + 1))

print("Bell        ", bell)
print("Catalan     ", catalan)
print("derangements", derange)
print("partitions  ", [partitions(n) for n in range(9)])
print("S(n,k) row 5", S[5], "  c(n,k) row 5", c[5])

# graph models: cluster graphs on [n] are counted by Bell numbers
def is_cluster(n, E):
    adj = {v: {v} for v in range(n)}
    for a, b in E:
        adj[a].add(b); adj[b].add(a)
    return all(adj[a] == adj[b] for a, b in E)   # an edge joins two vertices with equal closed neighbourhoods
for n in range(1, 6):
    pairs = list(combinations(range(n), 2))
    count = sum(is_cluster(n, [pairs[i] for i in range(len(pairs)) if m >> i & 1]) for m in range(1 << len(pairs)))
    print(f"cluster graphs on [{n}]: {count} = B_{n} = {bell[n]}")

Exercises

1.10 What is an answer?

We end the chapter by stepping back. Suppose we want the number \(\mathcal C_n\) of connected graphs on \([n]\). What would count as an answer? The question is less innocent than it looks, because \(\mathcal C_n\) has no formula of the kind \(n^{n-2}\), yet we can say a great deal about it. Five kinds of answers are possible, and they are the five chapters that follow.

Wilf’s criterion is simple. Listing all objects takes time at least proportional to their number, which usually grows exponentially. A formula is a good answer if it computes the number much faster than listing, ideally in time polynomial in \(n\). By this criterion a sum with exponentially many terms is not much of an answer, however explicit it looks, while a simple recurrence may be an excellent one.

Five answers for connected graphs

1. An explicit sum (Chapter 2). Inclusion–exclusion over the partitions of \([n]\) gives \[\mathcal C_n=\sum_{\pi}(-1)^{|\pi|-1}(|\pi|-1)!\;2^{\sum_{B\in\pi}\binom{|B|}2},\] where \(\pi\) runs over all partitions of \([n]\) and \(|\pi|\) is the number of blocks. The formula is explicit, but it has \(B_n\) terms, so by Wilf’s criterion it is a poor answer.

2. A recurrence (Chapter 4). Choose the component of vertex \(1\); if it has \(k\) vertices, it is a connected graph on \(1\) and \(k-1\) other vertices, and the rest is any graph. So \[2^{\binom n2}=\sum_{k=1}^{n}\binom{n-1}{k-1}\,\mathcal C_k\,2^{\binom{n-k}2},\] which computes \(\mathcal C_n\) from \(\mathcal C_1,\ldots,\mathcal C_{n-1}\) with \(O(n^2)\) arithmetic operations. This is an excellent answer.

3. A generating function (Chapter 5). With \(G(x)=\sum_{n\geqslant0}2^{\binom n2}\frac{x^n}{n!}\) and \(C(x)=\sum_{n\geqslant1}\mathcal C_n\frac{x^n}{n!}\), \[C(x)=\log G(x).\] The power series \(G(x)\) converges nowhere except at \(0\), yet the identity holds as an identity of formal power series, and the recurrence above is what one gets by differentiating it.

4. An estimate (Chapter 6). Almost all graphs are connected: \(\mathcal C_n/2^{\binom n2}\to1\). More precisely, the proportion of disconnected graphs is asymptotic to \(n\,2^{1-n}\), the proportion of graphs with an isolated vertex.

5. A bound (Chapter 7). A connected graph on \(n\) vertices has at least \(n-1\) edges, with equality exactly for trees; and every graph with more than \(\binom{n-1}2\) edges is connected (Exercise 1.2.2). Both bounds are sharp.

from math import comb, factorial, log

N = 10
# 2. the recurrence
C = [0, 1]
for n in range(2, N + 1):
    C.append(2 ** comb(n, 2) - sum(comb(n - 1, k - 1) * C[k] * 2 ** comb(n - k, 2) for k in range(1, n)))

# 1. the explicit sum over set partitions (slow on purpose)
def set_partitions(s):
    if not s:
        yield []; return
    first, rest = s[0], s[1:]
    for p in set_partitions(rest):
        yield [[first]] + p
        for i in range(len(p)):
            yield p[:i] + [[first] + p[i]] + p[i + 1:]
def explicit(n):
    return sum((-1) ** (len(p) - 1) * factorial(len(p) - 1) * 2 ** sum(comb(len(b), 2) for b in p)
               for p in set_partitions(list(range(n))))

# 3. coefficients of log G(x) as formal power series, with exact fractions
from fractions import Fraction
g = [Fraction(2 ** comb(n, 2), factorial(n)) for n in range(N + 1)]
c = [Fraction(0)] * (N + 1)          # log G: n c_n = n g_n - sum_{k<n} k c_k g_{n-k}
for n in range(1, N + 1):
    c[n] = (n * g[n] - sum(k * c[k] * g[n - k] for k in range(1, n))) / n
from_log = [int(c[n] * factorial(n)) for n in range(N + 1)]

for n in range(1, N + 1):
    ex = explicit(n) if n <= 8 else "(skipped)"
    print(f"n={n:2}  recurrence {C[n]:>15}  log G {from_log[n]:>15}  explicit {ex}"
          f"  disconnected {1 - C[n] / 2 ** comb(n, 2):.4f}  n*2^(1-n) {n * 2 ** (1 - n):.4f}")

The program computes \(\mathcal C_n\) in three of the five ways, by the recurrence, by the logarithm of a power series and by the explicit sum, and compares the proportion of disconnected graphs with \(n2^{1-n}\). The explicit sum is stopped at \(n=8\), where it already adds \(4140\) terms; the recurrence would reach \(n=1000\) in seconds.

Exercises

Chapter 2 · Elementary Explicit Answers

2.1 Counting labeled graphs

This chapter collects the counting problems in graph theory that have a closed answer obtainable by elementary means: the sum and product rules, bijections, double counting, inclusion–exclusion and Möbius inversion. We start with the simplest family of all, the graphs on a fixed vertex set.

We already know from Proposition 1.1.8 that there are \(2^{\binom n2}\) graphs on \([n]\) and \(\binom{\binom n2}m\) of them with \(m\) edges. A small change in the question often keeps the answer simple, provided we find the right bijection. Here is the first example.

Even graphs are the graphs whose every component has an Eulerian circuit (Section 2.8). They are also the elements of the cycle space of \(K_n\), a vector space over the field with two elements, and Theorem 2.1.1 says that this space has dimension \(\binom{n-1}2\). A count that is a power of \(2\) often hides a vector space.

Prescribed degrees and bipartitions

Fixing the degree of every vertex is much harder: there is no simple formula for the number of graphs with a given degree sequence, and Chapter 6 gives an asymptotic answer. Fixing a bipartition, on the other hand, is easy.

The sequence \(b_n\) begins \(2, 6, 26, 162, 1442\). It is not the number of bipartite graphs, because a bipartite graph with \(c\) components has \(2^c\) proper red–blue colourings. Separating these two counts needs the exponential formula of Chapter 5; it is a good example of a problem whose elementary answer is one step away from the answer we want.

Directed graphs and tournaments

from itertools import combinations
from math import comb

def graphs(n):
    pairs = list(combinations(range(n), 2))
    for mask in range(1 << len(pairs)):
        yield [pairs[i] for i in range(len(pairs)) if mask >> i & 1]

def degrees(n, E):
    d = [0] * n
    for a, b in E:
        d[a] += 1; d[b] += 1
    return d

for n in range(1, 7):
    even = odd = 0
    for E in graphs(n):
        d = degrees(n, E)
        even += all(x % 2 == 0 for x in d)
        odd += all(x % 2 == 1 for x in d)
    bic = sum(comb(n, k) * 2 ** (k * (n - k)) for k in range(n + 1))
    print(f"n={n}: all even {even:5} = 2^C(n-1,2) = {2 ** comb(n - 1, 2):5};  all odd {odd:5};  bicoloured {bic}")

Exercises

2.2 Double counting

Double counting means counting one set in two different ways. Applied to graphs, it usually counts small configurations, such as edges at a vertex, paths of length two or triangles, once by their vertices and once by their edges. The resulting identities are among the most useful tools of the subject.

Triangles in a graph and its complement

The statement for \(K_6\) is a strengthening of the first case of Ramsey’s theorem, \(R(3,3)=6\), which Chapter 7 treats in general. Notice the mechanism: an identity produced by double counting, followed by a single inequality. This pattern turns exact counts into extremal results again and again.

Connected graphs, counted twice

The following identity is the main theorem on connected graphs in the 2014 Persian edition of this book. It determines the number \(\mathcal C_n\) of connected graphs on \([n]\) from the numbers \(2^{\binom n2}\), and it is a model of a double-counting argument with a carefully chosen marking.

from itertools import combinations
from math import comb
import random

def triangles(n, E):
    E = {frozenset(e) for e in E}
    return sum(1 for a, b, c in combinations(range(n), 3)
               if {frozenset((a, b)), frozenset((a, c)), frozenset((b, c))} <= E)

random.seed(7)
n = 10
E = [e for e in combinations(range(n), 2) if random.random() < 0.4]
Ebar = [e for e in combinations(range(n), 2) if e not in set(E)]
deg = [sum(v in e for e in E) for v in range(n)]
print("t(G) + t(complement) =", triangles(n, E) + triangles(n, Ebar))
print("Goodman's formula    =", comb(n, 3) - sum(d * (n - 1 - d) for d in deg) // 2)

# connected graphs from the identity of the 2014 edition
C = {}
for m in range(1, 11):
    rest = sum(k * comb(m, k) * C[k] * 2 ** comb(m - k, 2) for k in range(1, m))
    C[m] = (m * 2 ** comb(m, 2) - rest) // m
print([C[m] for m in range(1, 11)])

Exercises

2.3 Bijective proofs

Two finite sets have the same size if and only if there is a bijection between them. A bijective proof of an identity \(|A|=|B|\) exhibits such a bijection explicitly. It is often the most illuminating proof, because it explains why the numbers agree rather than only showing that they do. In this section we collect bijections that turn graph problems into problems about words and functions.

Involutions and matchings

The numbers \(1, 1, 2, 4, 10, 26, 76, 232\) are sometimes called telephone numbers: they count the ways in which \(n\) subscribers can be connected in pairs for calls, with some subscribers idle.

Functions and their digraphs

So there are \(n^n\) functional digraphs on \([n]\). Their shape is simple: each component contains exactly one directed cycle, possibly a loop, and the rest of the component consists of trees hanging from the cycle with all arcs pointing towards it. A permutation is a functional digraph whose components are just cycles; this is the graph model of \(c(n,k)\) from Section 1.9.

The values are \(1, 3, 10, 41, 196\) for \(n=1,\ldots,5\). In Section 2.4 a cleverer bijection between functions and trees with two marked vertices, due to André Joyal, gives our third proof of Cayley’s formula.

Compositions and spanning subgraphs of paths

This tiny example shows the typical structure of a bijective proof: a graph-theoretic object (a spanning subgraph), a combinatorial word that encodes it (a composition), and an inverse map that rebuilds the object. The Prüfer code of the next section has exactly this structure, with a much less obvious encoding.

from itertools import permutations, product, combinations

def involutions(n):
    return sum(all(p[p[i]] == i for i in range(n)) for p in permutations(range(n)))

def matchings(n):
    # matchings of K_n by the recurrence of vertex n
    I = [1, 1]
    for k in range(2, n + 1):
        I.append(I[-1] + (k - 1) * I[-2])
    return I[n]

def idempotents(n):
    return sum(all(f[f[i]] == f[i] for i in range(n)) for f in product(range(n), repeat=n))

for n in range(1, 8):
    line = f"n={n}: involutions {involutions(n):4}  matchings of K_n {matchings(n):4}"
    if n <= 5:
        line += f"  idempotent maps {idempotents(n)}"
    print(line)

Exercises

2.4 Cayley’s formula

How many ways are there to connect \(n\) cities by roads so that every city can reach every other one and not a single road is wasted? Suppose the cities are named \(1,2,\ldots,n\) and a road joins two cities directly. “Not wasting a road” means that removing any road cuts some city off, that is, every edge is a bridge. By Lemma 1.2.11 and Theorem 1.6.3 these are exactly the trees on \([n]\).

The question is older than our cities. In the 1870s Cayley was counting the possible molecules of the alkanes \(C_nH_{2n+2}\), whose carbon atoms form a tree, and his method went through counting trees with named vertices first. The answer he found is one of the most quotable formulas in combinatorics.

Two labeled trees are equal only when they have the same edges, so the path \(1-2-3\) and the path \(2-1-3\) are different labeled trees although they are isomorphic. This is exactly the distinction of Section 1.3.

Small cases first

For \(n=1,2\) there is one tree, and for \(n=3\) a tree is a path decided by its middle vertex, so \(t_3=3\). For \(n=4\) there are two shapes, the path \(P_4\) and the star \(K_{1,3}\); by Example 1.3.4 there are \(4!/2=12\) labeled paths and \(4\) labeled stars, so \(t_4=16\).

For \(n=5\) there are three shapes: the path \(P_5\) with \(5!/2=60\) labeled copies; the star \(K_{1,4}\) with \(5\); and the fork, a vertex of degree \(3\) with one branch extended by an edge, whose automorphism group has order \(2\), giving \(5!/2=60\) copies. So \(t_5=60+5+60=125\).

Anyone who has stared at \(16=4^2\) and \(125=5^3\) will make the same guess, and \(3=3^1\) agrees: \(t_n=n^{n-2}\).

The right-hand side counts the words of length \(n-2\) over the alphabet \([n]\). So the theorem invites a bijection between trees and words, and our first proof builds one.

First proof: the Prüfer code

Throughout, \(T\) is a labeled tree on \([n]\) with \(n\geqslant3\). By Lemma 1.6.2 it has at least two leaves, and deleting a leaf from a tree leaves a tree.

In the example the vertices \(5\) and \(6\) have degree \(3\) and appear twice, \(7\) has degree \(2\) and appears once, and the leaves never appear. This is no accident.

from itertools import combinations, product

def prufer(n, edges):
    nbr = {v: set() for v in range(1, n + 1)}
    for u, v in edges:
        nbr[u].add(v); nbr[v].add(u)
    word = []
    for _ in range(n - 2):
        leaf = min(v for v in nbr if len(nbr[v]) == 1)
        (p,) = nbr[leaf]
        word.append(p)
        nbr[p].discard(leaf); del nbr[leaf]
    return word

def decode(n, word):
    left = {v: word.count(v) for v in range(1, n + 1)}
    alive, edges = set(range(1, n + 1)), []
    for a in word:
        leaf = min(v for v in alive if left[v] == 0)
        edges.append((leaf, a)); alive.remove(leaf); left[a] -= 1
    edges.append(tuple(sorted(alive)))
    return edges

def is_tree(n, edges):
    parent = list(range(n + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False
        parent[ru] = rv
    return True

print("P(T) =", prufer(7, [(1, 6), (2, 5), (3, 5), (4, 6), (5, 7), (6, 7)]))
for n in range(2, 8):
    t = sum(is_tree(n, S) for S in combinations(list(combinations(range(1, n + 1), 2)), n - 1))
    ok = all(prufer(n, decode(n, list(w))) == list(w) for w in product(range(1, n + 1), repeat=n - 2))
    print(f"n={n}: brute force {t:>6}   n^(n-2) = {n ** (n - 2):>6}   round trip ok: {ok}")

Second proof: counting twice

Third proof: vertebrates and functions

Exercises

2.5 Trees with constraints

The Prüfer code does more than count trees. Because it records the degree of every vertex (Lemma 2.4.9), it counts trees with prescribed degrees, with a prescribed number of leaves, and, with one more idea, forests with prescribed roots.

Forests with prescribed roots

Spanning trees of complete multipartite graphs

The complete graph is the most symmetric host for spanning trees. The next most symmetric hosts are the complete bipartite and multipartite graphs, and for them the answer is again a product of powers.

The bipartite case was found by H. I. Scoins in 1962 and the multipartite case by T. L. Austin in 1960. For \(r=n\) and all \(n_i=1\) the formula is Cayley’s. We prove it in Chapter 3 with the Matrix-Tree Theorem; finding a Prüfer-type proof is the research project of this section.

from itertools import combinations, product
from math import comb, factorial
from functools import lru_cache

def is_tree(n, E):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for a, b in E:
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        parent[ra] = rb
    return True

def spanning_trees(n, E):
    return [S for S in combinations(E, n - 1) if is_tree(n, S)]

@lru_cache(None)
def S2(m, j):
    if m == j: return 1
    if j == 0 or j > m: return 0
    return j * S2(m - 1, j) + S2(m - 1, j - 1)

n = 6
T = spanning_trees(n, list(combinations(range(n), 2)))
leaves = [sum(sum(v in e for e in t) == 1 for v in range(n)) for t in T]
for k in range(2, n):
    print(f"trees on [6] with {k} leaves: {leaves.count(k):4}   formula {factorial(n) // factorial(k) * S2(n - 2, n - k)}")

def multipartite(parts):
    V, E, start = [], [], 0
    blocks = []
    for p in parts:
        blocks.append(range(start, start + p)); start += p
    for i, j in combinations(range(len(parts)), 2):
        E += list(product(blocks[i], blocks[j]))
    return start, E

for parts in [(2, 3), (3, 3), (1, 2, 3), (2, 2, 2)]:
    n, E = multipartite(parts)
    formula = n ** (len(parts) - 2)
    for p in parts:
        formula *= (n - p) ** (p - 1)
    print(parts, "brute force", len(spanning_trees(n, E)), " formula", formula)

Exercises

2.6 Inclusion–exclusion

Many counting problems ask for objects that avoid a list of bad properties: graphs with no isolated vertex, colourings with no monochromatic edge, permutations with no fixed point. Counting the objects that have a given set of bad properties is often easy. The principle of inclusion and exclusion turns these easy counts into the answer.

In graph language, \(D_n\) counts the ways to cover the vertices of the complete digraph by disjoint directed cycles of length at least \(2\), and \(D_n/n!\to1/e\): about \(37\%\) of all permutations are derangements.

The values for \(n=1,\ldots,6\) are \(0, 1, 4, 41, 768, 27449\). Compare them with the numbers \(1,1,4,38,728,26704\) of connected graphs: every connected graph with at least two vertices has no isolated vertex, and for large \(n\) the two counts are close, a first hint of Chapter 6.

The chromatic polynomial

Permanents and Hamiltonian cycles

A perfect matching of a bipartite graph with sides \(\{u_1,\ldots,u_n\}\) and \(\{w_1,\ldots,w_n\}\) is a permutation \(\sigma\) with \(u_iw_{\sigma(i)}\) an edge for every \(i\). If \(A=(a_{ij})\) is the \(0/1\) matrix with \(a_{ij}=1\) when \(u_iw_j\) is an edge, the number of perfect matchings is the permanent \[\mathrm{per}(A)=\sum_{\sigma}\prod_{i=1}^na_{i\sigma(i)},\] the determinant without signs. It has \(n!\) terms, but inclusion–exclusion gives a formula with only \(2^n\).

The same idea counts Hamiltonian cycles: a closed walk of length \(n\) that visits every vertex is a Hamiltonian cycle, and inclusion–exclusion over the set of avoided vertices counts such walks with \(2^n\) matrix powers (Exercise 2.6.6). These are the fastest known exact methods of their kind, and they are still exponential; Chapter 6 explains why nobody expects much better.

from itertools import permutations, combinations
from math import comb, prod

def per_brute(A):
    n = len(A)
    return sum(prod(A[i][p[i]] for i in range(n)) for p in permutations(range(n)))

def per_ryser(A):
    n = len(A)
    total = 0
    for k in range(n + 1):
        for S in combinations(range(n), k):
            total += (-1) ** (n - k) * prod(sum(A[i][j] for j in S) for i in range(n))
    return total

# Q3 is bipartite: even-weight words against odd-weight words
even = [x for x in range(8) if bin(x).count("1") % 2 == 0]
odd = [x for x in range(8) if bin(x).count("1") % 2 == 1]
A = [[int(bin(u ^ w).count("1") == 1) for w in odd] for u in even]
print("perfect matchings of Q3:", per_brute(A), per_ryser(A))

no_isolated = [sum((-1) ** i * comb(n, i) * 2 ** comb(n - i, 2) for i in range(n + 1)) for n in range(1, 8)]
print("graphs with no isolated vertex:", no_isolated)

def chromatic_whitney(n, E, k):
    total = 0
    for r in range(len(E) + 1):
        for S in combinations(E, r):
            parent = list(range(n))
            def find(x):
                while parent[x] != x: x = parent[x]
                return x
            for a, b in S:
                parent[find(a)] = find(b)
            total += (-1) ** r * k ** len({find(v) for v in range(n)})
    return total

C5 = [(i, (i + 1) % 5) for i in range(5)]
print("P(C5, k) for k = 0..5:", [chromatic_whitney(5, C5, k) for k in range(6)])

Exercises

2.7 Möbius inversion

Inclusion–exclusion runs over the subsets of a set. Many counting problems have a different natural structure, for example the partitions of a set, ordered by refinement. Möbius inversion, due in this generality to Gian-Carlo Rota, does for every finite partially ordered set what inclusion–exclusion does for subsets. It gives the explicit formula for connected graphs announced in Section 1.10.

The partition lattice

Connected graphs, explicitly

The same argument works for any property of graphs that is decided component by component. Replacing \(2^{\binom{|B|}2}\) by the number \(2^{\binom{|B|-1}2}\) of even graphs on \(B\) (Theorem 2.1.1) counts the connected even graphs, which are the Eulerian graphs of the next section.

from math import comb, factorial

def set_partitions(items):
    if not items:
        yield []; return
    first, rest = items[0], items[1:]
    for p in set_partitions(rest):
        yield [[first]] + p
        for i in range(len(p)):
            yield p[:i] + [[first] + p[i]] + p[i + 1:]

def count_connected(n, per_block):
    """Moebius inversion on the partition lattice for a property decided block by block."""
    total = 0
    for p in set_partitions(list(range(n))):
        k = len(p)
        term = (-1) ** (k - 1) * factorial(k - 1)
        for B in p:
            term *= per_block(len(B))
        total += term
    return total

all_graphs = lambda b: 2 ** comb(b, 2)
even_graphs = lambda b: 2 ** comb(b - 1, 2)
print("connected graphs: ", [count_connected(n, all_graphs) for n in range(1, 9)])
print("connected even:   ", [count_connected(n, even_graphs) for n in range(1, 9)])

Exercises

2.8 Eulerian structures

We return to the problem with which graph theory began. Can one walk across each of the seven bridges of Königsberg exactly once? In our language: does the multigraph of the four land masses and seven bridges have an Eulerian trail, a trail that uses every edge exactly once?

The proof is also an algorithm: Hierholzer’s algorithm finds an Eulerian circuit in time proportional to the number of edges by splicing cycles as above. The directed version is proved the same way: a weakly connected digraph has a directed Eulerian circuit if and only if \(d^+(v)=d^-(v)\) for every vertex.

Counting Eulerian graphs

De Bruijn sequences

For \(n=3\), the cyclic sequence \(00010111\) contains \(000,001,010,101,011,111,110,100\), each once. Such sequences exist for every \(n\): in the de Bruijn digraph whose vertices are the words of length \(n-1\), draw an arc from \(a_1\cdots a_{n-1}\) to \(a_2\cdots a_n\) labeled \(a_1\cdots a_n\). Every vertex has in-degree and out-degree \(2\), and the digraph is strongly connected, so it has a directed Eulerian circuit, and the circuit spells a de Bruijn sequence. Counting the circuits is harder; Chapter 3 proves with the BEST theorem that there are exactly \(2^{2^{n-1}-n}\) binary de Bruijn sequences of order \(n\).

from itertools import combinations, product

def hierholzer(adj, start):
    """Eulerian circuit of a digraph given as {v: [w, ...]} (each list is consumed)."""
    stack, circuit = [start], []
    while stack:
        v = stack[-1]
        if adj[v]:
            stack.append(adj[v].pop())
        else:
            circuit.append(stack.pop())
    return circuit[::-1]

def de_bruijn(n):
    words = ["".join(w) for w in product("01", repeat=n - 1)]
    adj = {w: [w[1:] + "1", w[1:] + "0"] for w in words}
    circuit = hierholzer(adj, "0" * (n - 1))
    return "".join(v[-1] for v in circuit[1:])

for n in range(2, 6):
    s = de_bruijn(n)
    windows = {(s + s)[i:i + n] for i in range(len(s))}
    print(n, s, "all words present:", len(windows) == 2 ** n)

# count de Bruijn sequences of order 4 by brute force over cyclic sequences
n, L = 4, 16
seqs = set()
for bits in product("01", repeat=L):
    s = "".join(bits)
    if len({(s + s)[i:i + n] for i in range(L)}) == L:
        seqs.add(min(s[i:] + s[:i] for i in range(L)))   # one representative per rotation class
print("de Bruijn sequences of order 4:", len(seqs), " formula 2^(2^(n-1)-n) =", 2 ** (2 ** (n - 1) - n))

Exercises

Chapter 3 · Advanced Explicit Answers

3.1 Matrices of a graph

Part A of this chapter rests on one observation: a graph on \([n]\) is an \(n\times n\) matrix of zeros and ones. Once the graph is a matrix, a whole toolbox becomes available. Matrix products count walks, determinants count trees and matchings, and eigenvalues compress all of this into a handful of numbers. In this section we set up the matrices and learn to count walks; the next four sections build on them.

\(A\) is symmetric with zero diagonal, and its row sums are the degrees. The Laplacian has row sums \(0\), so \(L\mathbf 1=0\), where \(\mathbf 1\) is the all-ones vector.

Walks

Eigenvalues

Because \(A\) is real and symmetric, it has \(n\) real eigenvalues \(\lambda_1\geqslant\cdots\geqslant\lambda_n\), the spectrum of \(G\), and an orthonormal basis of eigenvectors \(x_1,\ldots,x_n\). Then \(A=\sum_i\lambda_ix_ix_i^{\mathsf T}\) and \(A^k=\sum_i\lambda_i^kx_ix_i^{\mathsf T}\).

So the spectrum alone tells us the number of edges and the number of triangles; for a regular graph it also gives the number of spanning trees, as we shall see in Section 3.2. Here are the spectra of the families of Chapter 1.

The Laplacian

Fix an orientation of each edge and let \(B\) be the \(n\times|E|\) incidence matrix: the column of the edge \(e\) oriented from \(u\) to \(v\) has \(+1\) in row \(u\), \(-1\) in row \(v\) and zeros elsewhere. Then \((BB^{\mathsf T})_{uu}=\deg(u)\) and \((BB^{\mathsf T})_{uv}=-a_{uv}\) for \(u\neq v\), so \[L=BB^{\mathsf T}\qquad\text{and}\qquad x^{\mathsf T}Lx=\sum_{uv\in E}(x_u-x_v)^2.\] The orientation does not matter. The quadratic form shows that \(L\) is positive semidefinite, with eigenvalues \(0=\mu_1\leqslant\mu_2\leqslant\cdots\leqslant\mu_n\).

For a \(d\)-regular graph \(L=dI-A\), so the Laplacian eigenvalues are \(d-\lambda_i\). For example \(K_n\) has Laplacian eigenvalues \(0\) and \(n\) (\(n-1\) times), \(Q_n\) has \(2j\) with multiplicity \(\binom nj\), and the Petersen graph has \(0\), \(2\) (five times) and \(5\) (four times).

import numpy as np
import networkx as nx

def closed_walks(G, k):
    lam = np.linalg.eigvalsh(nx.to_numpy_array(G))
    return round(sum(lam ** k))

P = nx.petersen_graph()
print("Petersen spectrum:", np.round(sorted(np.linalg.eigvalsh(nx.to_numpy_array(P))), 6))
print("closed walks of length 3, 4, 5:", [closed_walks(P, k) for k in (3, 4, 5)])
print("five-cycles:", closed_walks(P, 5) // 10)

# walks of length k between two vertices of K_5, by matrix power and by formula
A = np.ones((5, 5), dtype=int) - np.eye(5, dtype=int)
for k in range(1, 7):
    print(k, np.linalg.matrix_power(A, k)[0, 1], (4 ** k - (-1) ** k) // 5)

# Laplacian eigenvalues of Q_4: 2j with multiplicity C(4, j)
L = nx.laplacian_matrix(nx.hypercube_graph(4)).toarray()
print(np.round(sorted(np.linalg.eigvalsh(L)), 6))

Exercises

3.2 The Matrix-Tree Theorem

In Chapter 2 we counted the spanning trees of \(K_n\) three ways, and every proof used the symmetry of \(K_n\). Kirchhoff’s theorem counts the spanning trees of any graph, and the answer is a determinant: something a computer evaluates in polynomial time even when the number itself is astronomically large.

The proof needs one fact from linear algebra.

Families

For \(Q_3\) formula (c) gives \(2^4\cdot1^3\cdot2^3\cdot3=384\), and for \(Q_4\) it gives \(42\,467\,328\). No proof of (c) by a bijection is known, and finding one is the research thread of this section.

Since \(Q_n=Q_{n-1}\,\square\,K_2\), this gives the spectrum of \(Q_n\) again. It also handles grids \(P_m\,\square\,P_n\), whose path factors have Laplacian eigenvalues \(2-2\cos(\pi j/n)\), \(j=0,\ldots,n-1\); the \(3\times3\) grid has \(192\) spanning trees and the \(4\times4\) grid has \(100\,352\).

from fractions import Fraction
import networkx as nx

def det(M):
    # exact determinant by Gaussian elimination over the rationals
    M = [[Fraction(x) for x in row] for row in M]
    n, d = len(M), Fraction(1)
    for c in range(n):
        p = next((r for r in range(c, n) if M[r][c] != 0), None)
        if p is None:
            return 0
        if p != c:
            M[c], M[p] = M[p], M[c]; d = -d
        d *= M[c][c]
        for r in range(c + 1, n):
            f = M[r][c] / M[c][c]
            M[r] = [a - f * b for a, b in zip(M[r], M[c])]
    return int(d)

def tau(G):
    L = nx.laplacian_matrix(G, nodelist=list(G)).toarray().tolist()
    return det([row[1:] for row in L[1:]])

print("K_n:  ", [tau(nx.complete_graph(n)) for n in range(2, 9)])
print("Q_n:  ", [tau(nx.hypercube_graph(n)) for n in range(1, 5)])
print("K_3,4:", tau(nx.complete_bipartite_graph(3, 4)), "= 3^3 * 4^2 =", 3**3 * 4**2)
print("Petersen:", tau(nx.petersen_graph()))
print("grids:", tau(nx.grid_2d_graph(3, 3)), tau(nx.grid_2d_graph(4, 4)))
print("wheels W_n:", [tau(nx.wheel_graph(n + 1)) for n in range(3, 9)])
print("ladders P_2 x P_n:", [tau(nx.grid_2d_graph(2, n)) for n in range(1, 9)])

Exercises

3.3 Arborescences and the BEST theorem

Kirchhoff’s theorem has a directed version, and the directed version counts something that looks unrelated: Eulerian circuits. This section proves both and then counts de Bruijn sequences, completing the story begun in Section 2.8.

Let \(L^{+}=D^{+}-A\), where \(D^{+}\) is the diagonal matrix of out-degrees and \(a_{uv}\) is the number of arcs from \(u\) to \(v\) (loops are ignored). Its row sums are \(0\).

For a graph, replacing each edge by two opposite arcs gives \(L^{+}=L\), and an arborescence converging to \(r\) is just a spanning tree. So Theorem 3.3.2 contains Theorem 3.2.2.

The BEST theorem

An Eulerian circuit of a digraph is a closed walk that uses every arc exactly once; we regard two circuits as the same when one is a cyclic shift of the other. A connected digraph has one exactly when \(d^{+}(v)=d^{-}(v)\) for every \(v\), by the directed version of Theorem 2.8.3.

De Bruijn sequences

We extend Definition 2.8.6 to any alphabet: a de Bruijn sequence of order \(n\) over an alphabet of size \(k\) is a cyclic word of length \(k^n\) in which every word of length \(n\) appears exactly once as a block of consecutive letters. Such a sequence is the same thing as an Eulerian circuit of the de Bruijn digraph \(B(k,n-1)\), whose vertices are the \(k^{n-1}\) words of length \(n-1\) and which has an arc \(a_1\cdots a_{n-1}\to a_2\cdots a_n\) for each word \(a_1\cdots a_n\).

For \(k=2\) and \(n=4\) there are \(2^{8-4}=16\) sequences, the number found by brute force in Section 2.8; for \(k=3\) and \(n=2\) there are \(6^3/9=24\).

import itertools as it
from fractions import Fraction
from math import factorial

def det(M):
    M = [[Fraction(x) for x in row] for row in M]
    n, d = len(M), Fraction(1)
    for c in range(n):
        p = next((r for r in range(c, n) if M[r][c] != 0), None)
        if p is None: return 0
        if p != c: M[c], M[p] = M[p], M[c]; d = -d
        d *= M[c][c]
        for r in range(c + 1, n):
            f = M[r][c] / M[c][c]
            M[r] = [a - f * b for a, b in zip(M[r], M[c])]
    return int(d)

def debruijn_count(k, n):
    verts = ["".join(w) for w in it.product("0123456789"[:k], repeat=n - 1)]
    idx = {v: i for i, v in enumerate(verts)}
    N = len(verts)
    L = [[0] * N for _ in range(N)]
    for v in verts:
        for a in "0123456789"[:k]:
            w = (v + a)[1:]
            if w != v:                       # loops do not matter
                L[idx[v]][idx[v]] += 1
                L[idx[v]][idx[w]] -= 1
    t = det([row[1:] for row in L[1:]])      # arborescences converging to 00...0
    return t * factorial(k - 1) ** N         # BEST theorem

for k, n in [(2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (4, 2)]:
    print(k, n, debruijn_count(k, n), "formula", factorial(k) ** (k ** (n - 1)) // k ** n)

Exercises

3.4 Non-intersecting paths

A determinant is a signed sum over permutations, and a count is an unsigned sum. The Matrix-Tree Theorem worked because all the signs turned out to be squares. In this section the signs cancel in pairs instead: the determinant of a matrix of path counts counts families of paths that never meet.

The typical application is to lattice paths in the plane, with unit steps east and north. If the sources lie on a line running from top-left to bottom-right and the sinks lie on another such line, in the same order, then a path from \(A_1\) to \(B_2\) and a path from \(A_2\) to \(B_1\) must cross. So only \(\sigma=\mathrm{id}\) survives.

Plane partitions

For the \(2\times2\times2\) box the determinant is \(\binom42^2-\binom41\binom43=20\); for \(2\times3\times3\) it is \(175\); for the \(3\times3\times3\) box it is \(980\). A plane partition in a box, seen from the corner, is a tiling of a hexagon with sides \(a,b,c,a,b,c\) by rhombi, so the same numbers count lozenge tilings.

from math import comb, prod
from fractions import Fraction
import itertools as it
import sympy as sp

def lgv_box(a, b, c):
    return sp.Matrix(a, a, lambda i, j: comb(b + c, b - i + j)).det()

def macmahon(a, b, c):
    num = prod(i + j + k - 1 for i in range(1, a + 1) for j in range(1, b + 1) for k in range(1, c + 1))
    den = prod(i + j + k - 2 for i in range(1, a + 1) for j in range(1, b + 1) for k in range(1, c + 1))
    return Fraction(num, den)

def brute(a, b, c):
    # count a x b arrays with entries 0..c, decreasing along rows and columns
    cnt = 0
    for vals in it.product(range(c + 1), repeat=a * b):
        M = [vals[r * b:(r + 1) * b] for r in range(a)]
        if all(M[r][s] >= M[r][s + 1] for r in range(a) for s in range(b - 1)) and \
           all(M[r][s] >= M[r + 1][s] for r in range(a - 1) for s in range(b)):
            cnt += 1
    return cnt

for box in [(1, 2, 3), (2, 2, 2), (2, 3, 3), (3, 3, 3)]:
    print(box, lgv_box(*box), macmahon(*box), brute(*box))

Exercises

3.5 Perfect matchings

In Section 2.6 we met the permanent: the number of perfect matchings of a bipartite graph is \(\mathrm{per}(A)\), a determinant without signs, and Ryser’s formula computes it with about \(2^n\) terms instead of \(n!\). No essentially better method is expected. Yet for planar graphs, a clever choice of signs turns the count into a determinant. This is how physicists counted the domino tilings of a chessboard in 1961.

So counting perfect matchings of bipartite graphs is as hard as any counting problem whose objects can be checked quickly. Determinants, by contrast, cost \(O(n^3)\). The question is when a permanent can be disguised as a determinant.

Pfaffians

For \(2n=4\), \(\operatorname{Pf}(M)=m_{12}m_{34}-m_{13}m_{24}+m_{14}m_{23}\). The fundamental fact, due to Cayley, is that \(\operatorname{Pf}(M)^2=\det M\); so a Pfaffian can be computed as fast as a determinant, up to its sign.

Now orient the edges of a graph \(G\) on \([2n]\), and let \(M\) have \(m_{ij}=1\) and \(m_{ji}=-1\) when the edge \(ij\) is oriented from \(i\) to \(j\), and \(0\) when \(ij\) is not an edge. The nonzero terms of \(\operatorname{Pf}(M)\) are then the perfect matchings of \(G\), each with a sign \(\pm1\). If all the signs agree, the orientation is called Pfaffian, and then \[\#\{\text{perfect matchings of }G\}=|\operatorname{Pf}(M)|=\sqrt{\det M}.\]

Domino tilings

A tiling of an \(m\times n\) rectangle by \(1\times2\) dominoes is a perfect matching of the grid \(P_m\,\square\,P_n\): each domino covers two adjacent squares.

The formula gives \(F_{n+1}\) for a \(2\times n\) strip, \(36\) for the \(4\times4\) square (the exercise of Section 2.6), \(6728\) for \(6\times6\), and \(12\,988\,816\) for the chessboard. The number of tilings of an \(n\times n\) square grows like \(e^{(G/\pi)n^2}\approx1.3385^{n^2}\), where \(G=1-\frac19+\frac1{25}-\cdots\) is Catalan’s constant; this is the kind of answer studied in Chapter 6.

import numpy as np
import networkx as nx
from math import cos, pi, prod

def tilings_formula(m, n):
    r = 1.0
    for j in range(1, m + 1):
        for k in range(1, n + 1):
            r *= 4 * cos(pi * j / (m + 1)) ** 2 + 4 * cos(pi * k / (n + 1)) ** 2
    return round(r ** 0.25)

def tilings_kasteleyn(m, n):
    # bipartite Kasteleyn matrix: weight 1 on horizontal edges, i on vertical edges
    black = [(x, y) for x in range(n) for y in range(m) if (x + y) % 2 == 0]
    white = [(x, y) for x in range(n) for y in range(m) if (x + y) % 2 == 1]
    if len(black) != len(white):
        return 0
    w = {c: i for i, c in enumerate(white)}
    K = np.zeros((len(black), len(white)), dtype=complex)
    for i, (x, y) in enumerate(black):
        for dx, dy, wt in ((1, 0, 1), (-1, 0, 1), (0, 1, 1j), (0, -1, 1j)):
            if (x + dx, y + dy) in w:
                K[i, w[(x + dx, y + dy)]] = wt
    return round(abs(np.linalg.det(K)))

def tilings_brute(m, n):
    G = nx.grid_2d_graph(m, n)
    def rec(free):
        if not free: return 1
        v = min(free)
        return sum(rec(free - {v, u}) for u in G[v] if u in free)
    return rec(frozenset(G))

for m, n in [(2, 8), (3, 4), (4, 4), (5, 6), (6, 6), (8, 8)]:
    b = tilings_brute(m, n) if m * n <= 36 else "-"
    print(f"{m}x{n}: formula {tilings_formula(m, n)}, Kasteleyn {tilings_kasteleyn(m, n)}, brute {b}")

Exercises

3.6 Group actions on graphs

Part B is about counting up to symmetry. How many graphs on \(5\) vertices are there if we do not care about the names of the vertices? How many ways are there to colour the corners of a cube, if two colourings that differ by a rotation count as one? Both questions ask for the number of orbits of a group acting on a finite set, and this section sets up the language.

Two elements are in the same orbit if one is carried to the other by some \(\gamma\); this is an equivalence relation, so the orbits partition \(X\).

Three actions

1. The symmetric group \(S_n\) acts on the \(2^{\binom n2}\) graphs on \([n]\): \(\sigma\) sends \(G\) to the graph with edges \(\sigma(u)\sigma(v)\). The orbits are the isomorphism classes, the unlabeled graphs, and the stabiliser of \(G\) is \(\mathrm{Aut}(G)\). So Theorem 3.6.2 is Theorem 1.3.3: \(G\) has \(n!/|\mathrm{Aut}(G)|\) labeled copies.

2. \(\mathrm{Aut}(G)\) acts on \(V(G)\), on \(E(G)\), and on the colourings \(c:V(G)\to[k]\) by \((\gamma c)(v)=c(\gamma^{-1}v)\). Its orbits on colourings are the colourings up to symmetry.

3. The cyclic group \(\mathbb Z_n\) of rotations, or the dihedral group \(D_n\) of rotations and reflections, acts on the words of length \(n\) written around a circle. The orbits are necklaces and bracelets.

Automorphism groups

A graph with \(|\mathrm{Aut}(G)|=1\) is called asymmetric. Small graphs are rarely asymmetric: there are none on \(2\) to \(5\) vertices, \(8\) on \(6\) vertices and \(152\) on \(7\). Large graphs almost always are: Erdős and Rényi proved in 1963 that the proportion of asymmetric graphs on \([n]\) tends to \(1\). We return to this in Chapter 6 and to asymmetric colourings in Section 3.10.

import itertools as it
import networkx as nx
from networkx.algorithms.isomorphism import GraphMatcher
from math import factorial, comb

def aut_order(G):
    return sum(1 for _ in GraphMatcher(G, G).isomorphisms_iter())

for name, G in [("K_5", nx.complete_graph(5)), ("C_7", nx.cycle_graph(7)), ("K_3,3", nx.complete_bipartite_graph(3, 3)),
                ("Q_3", nx.hypercube_graph(3)), ("Q_4", nx.hypercube_graph(4)), ("Petersen", nx.petersen_graph())]:
    a = aut_order(G); n = G.number_of_nodes()
    print(f"{name:9s} |Aut| = {a:5d}   labeled copies = {factorial(n) // a}")

# the orbit-counting check of Chapter 1: sum over unlabeled graphs of n!/|Aut| = 2^C(n,2)
from networkx.generators.atlas import graph_atlas_g
for n in range(1, 7):
    types = [G for G in graph_atlas_g() if G.number_of_nodes() == n]
    total = sum(factorial(n) // aut_order(G) for G in types)
    asym = sum(1 for G in types if aut_order(G) == 1)
    print(n, len(types), "types,", total, "= 2^C(n,2) =", 2 ** comb(n, 2), "; asymmetric:", asym)

Exercises

3.7 Burnside’s lemma

To count orbits we could list them, but listing is exactly what we want to avoid. The lemma of this section counts orbits by counting fixed points, which is usually easy.

Necklaces

A necklace of length \(n\) with \(k\) colours is an orbit of the rotation group \(\mathbb Z_n\) on the \(k^n\) words; a bracelet is an orbit of the dihedral group \(D_n\), which also allows turning the necklace over.

For \(k=2\) the necklaces of lengths \(1,\ldots,8\) number \(2,3,4,6,8,14,20,36\) and the bracelets \(2,3,4,6,8,13,18,30\). In Figure 3.7.2 the six necklaces of length \(4\) are also the six bracelets: turning over a necklace of length \(4\) never gives anything new.

Colourings of a graph up to symmetry

The same method counts proper colourings up to symmetry, but now \(\mathrm{Fix}(\gamma)\) is the set of proper colourings that are constant on the cycles of \(\gamma\); it is empty as soon as some cycle of \(\gamma\) contains both ends of an edge. For \(C_5\) with \(3\) colours, only the identity fixes a proper colouring, so the \(P(C_5,3)=30\) proper colourings fall into \(30/10=3\) classes.

import itertools as it
import networkx as nx
from networkx.algorithms.isomorphism import GraphMatcher
from math import gcd

def automorphisms(G):
    return list(GraphMatcher(G, G).isomorphisms_iter())

def n_cycles(perm):
    seen, c = set(), 0
    for v in perm:
        if v not in seen:
            c += 1
            while v not in seen:
                seen.add(v); v = perm[v]
    return c

def colourings_up_to_symmetry(G, k):
    A = automorphisms(G)
    return sum(k ** n_cycles(a) for a in A) // len(A)

def proper_up_to_symmetry(G, k):
    A, V = automorphisms(G), list(G)
    total = 0
    for a in A:
        for col in it.product(range(k), repeat=len(V)):
            c = dict(zip(V, col))
            if all(c[u] != c[v] for u, v in G.edges()) and all(c[a[v]] == c[v] for v in V):
                total += 1
    return total // len(A)

def necklaces(n, k):
    return sum(k ** gcd(n, j) for j in range(n)) // n

print("necklaces, k = 2:", [necklaces(n, 2) for n in range(1, 11)])
for name, G in [("C_6", nx.cycle_graph(6)), ("Q_3", nx.hypercube_graph(3)), ("Petersen", nx.petersen_graph())]:
    print(name, [colourings_up_to_symmetry(G, k) for k in (2, 3, 4)])
print("proper 3-colourings up to symmetry: C_5", proper_up_to_symmetry(nx.cycle_graph(5), 3),
      " Petersen", proper_up_to_symmetry(nx.petersen_graph(), 3))

Exercises

3.8 Pólya’s theorem

Burnside’s lemma counts all the orbits at once. Often we want more: how many unlabeled graphs on \(6\) vertices have exactly \(7\) edges? Pólya’s theorem keeps track of such weights by replacing the number \(k^{c(\gamma)}\) with a polynomial that remembers the lengths of the cycles.

Counting unlabeled graphs

An unlabeled graph on \(n\) vertices is an orbit of \(S_n\) acting on the red-blue colourings of the \(\binom n2\) pairs, where red means edge. So we need the cycle index of the pair group \(S_n^{(2)}\): the action of \(S_n\) on pairs.

Since \(Z\) depends on \(\sigma\) only through its cycle type, the sum runs over the partitions of \(n\), weighted by the class sizes \(n!/\prod_ii^{m_i}m_i!\). For \(n=10\) that is \(42\) terms instead of \(10!\). The same method counts multigraphs with edge multiplicities at most \(k\) (substitute \(x_i=k+1\)), digraphs (use the action of \(S_n\) on ordered pairs: \(1,3,16,218,9608\) for \(n\leqslant5\)), and graphs with any other kind of decoration on the pairs.

from math import factorial, gcd, prod
from sympy import symbols, expand, Poly
from sympy.utilities.iterables import partitions

def pair_cycle_lengths(lens):
    out = []
    for i, a in enumerate(lens):
        out += [a] * ((a - 1) // 2) + ([a // 2] if a % 2 == 0 else [])
        for b in lens[i + 1:]:
            out += [a * b // gcd(a, b)] * gcd(a, b)
    return out

def classes(n):
    for p in partitions(n):
        lens = [l for l, m in p.items() for _ in range(m)]
        yield lens, factorial(n) // prod(l ** m * factorial(m) for l, m in p.items())

def unlabeled_graphs(n):
    return sum(size * 2 ** len(pair_cycle_lengths(l)) for l, size in classes(n)) // factorial(n)

t = symbols("t")
def by_edges(n):
    Z = sum(size * prod(1 + t ** c for c in pair_cycle_lengths(l)) for l, size in classes(n))
    return Poly(expand(Z / factorial(n)), t).all_coeffs()[::-1]

print("g_n:", [unlabeled_graphs(n) for n in range(1, 13)])
print("n = 6 by edges:", by_edges(6))
print("multigraphs, multiplicity <= 2:", [sum(s * 3 ** len(pair_cycle_lengths(l)) for l, s in classes(n)) // factorial(n) for n in range(1, 7)])

Exercises