The complete list of all free trees on 2,3,4 labeled vertices: 2^{2 − 2} = 1 tree with 2 vertices, 3^{3 − 2} = 3 trees with 3 vertices and 4^{4 − 2} = 16 trees with 4 vertices.

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 that of the number of vertices of the graph.^[1] The pioneers in this area of mathematics were Polya ^[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 with m edges is 2^{n(n − 1)/2}.^[6]
• The number of labeled n-vertex directed graphs with m edges is 2^n(n − 1).^[7]
• The number C_n of connected labeled 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_n are

1, 1, 4, 38, 728, 26704, 1866256, ...(sequence A001187 in OEIS)

• The number of labeled n-vertex free trees is n^n − 2 (Cayley's formula).

[edit] References

This combinatorics-related article is a stub. You can help Wikipedia by expanding it. v • d • e