Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije

Minicourse Graph Enumeration - Syllabus


How many graphs are there? Infinitely many, of course, but how many non-isomorphic graphs, for instance, of order n? How many of them are connected, how many are trees, how many are Eulerian?

In this short course, we will treat combinatorial, algebraic and analytic techniques to solve graph-theoretical counting problems:

  • Labelled enumeration: Labelled graphs and digraphs, trees, acyclic digraphs, ...
  • Unlabelled enumeration: Pólya's method, the number of unlabelled graphs and trees.
  • Analytic methods: asymptotic approximation, generating function techniques.

The classical reference on this topic is

F. Harary and E. M. Palmer, Graphical enumeration. Academic Press, New York, 1973.


Stephan Wagner (Stellenbosch University, South Africa)

Lecture notes: part 1, part 2, part 3.