# Graph enumeration

In combinatorics, an area of mathematics, **graph enumeration** describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph.^{[1]} The pioneers in this area of mathematics were Pólya,^{[2]} Cayley ^{[3]} and Redfield.^{[4]}

In some graphical enumeration problems, the vertices of the graph are considered to be *labeled* in such a way as to be distinguishable from each other, while in other problems any permutation of the vertices is considered to form the same graph. In general, labeled problems tend to be easier to solve than unlabeled problems.^{[5]} As with combinatorial enumeration more generally, the Pólya enumeration theorem is an important tool for dealing with symmetries such as this.

Some important results in this area include the following.

- The number of labeled
*n*-vertex undirected graphs is 2^{n(n − 1)/2}.^{[6]} - The number of labeled
*n*-vertex directed graphs is 2^{n(n − 1)}.^{[7]} - The number
*C*of connected labeled_{n}*n*-vertex undirected graphs satisfies the recurrence relation^{[8]}

- from which one may easily calculate, for
*n*= 1, 2, 3, ..., that the values for*C*are_{n}

- The number of labeled
*n*-vertex free trees is*n*^{n − 2}(Cayley's formula). - The number of unlabeled
*n*-vertex caterpillars is^{[9]}

## Enumerating Graphs on A Degree Sequence

Given a degree sequence * d* one can enumerate all the graphs with degree sequence

*using an algorithm. One such algorithm given by Blitzstein and Diaconis*

**d**^{[10]}is as follows;

INPUT: a graphical sequence * d*=(

*d*

_{1},

*d*

_{2}, ...,

*d*

_{n}).

- Let E be an empty list of edges.
- If
= 0, terminate with output E.**d** - Choose the least i with di a minimal positive entry.
- Compute the candidate list J={j≠i : {i,j} ∉ E and (
*d*_{1},*d*_{2}, ...,*d*_{i}− 1,...,*d*_{j}− 1, ...,*d*_{n}) is graphical.} - Pick j ∈ J with probability proportional to its degree in
*d*. - Add edge {i,j} to E and update
to (**d***d*_{1},*d*_{2}, ...,*d*_{i}− 1,...,*d*_{j}− 1, ...,*d*_{n}) - Repeat steps 4-6 until the degree of i is 0.
- Return to step 2.

OUTPUT: E

This algorithm generates a random graph with the given degree sequence. Running the algorithm repeatedly will generate all graphs with degree sequence * d*.

## References

- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254
- ↑ Template:Acad
- ↑ The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
- ↑ Harary and Palmer, p. 1.
- ↑ Harary and Palmer, p. 3.
- ↑ Harary and Palmer, p. 5.
- ↑ Harary and Palmer, p. 7.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ http://www.people.fas.harvard.edu/~blitz/BlitzsteinDiaconisGraphAlgorithm.pdf