![Cayley's formula 2-4](https://upload.wikimedia.org/wikipedia/commons/e/ee/Cayley%27s_formula_2-4.svg)
In
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, an area of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, graph enumeration describes a class of
combinatorial enumeration
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infini ...
problems in which one must count
undirected
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
or
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s of certain types, typically as a function of the number of vertices of the graph. These problems may be solved either exactly (as an
algebraic enumeration problem) or
asymptotically.
The pioneers in this area of mathematics were
George Pólya
George Pólya (; hu, Pólya György, ; December 13, 1887 – September 7, 1985) was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental ...
,
Arthur Cayley and
J. Howard Redfield
John Howard Redfield (June 8, 1879 – April 17, 1944) was an American mathematician, best known for discovery of what is now called Pólya enumeration theorem (PET) in 1927, ten years ahead of similar but independent discovery made by George Póly ...
.
Labeled vs unlabeled problems
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, so the vertices are considered identical or ''unlabeled''. In general, labeled problems tend to be easier. As with combinatorial enumeration more generally, the
Pólya enumeration theorem
The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. ...
is an important tool for reducing unlabeled problems to labeled ones: each unlabeled class is considered as a symmetry class of labeled objects.
Exact enumeration formulas
Some important results in this area include the following.
*The number of labeled ''n''-vertex
simple undirected graphs is 2
''n''(''n'' −1)/2.
*The number of labeled ''n''-vertex
simple directed graphs is 2
''n''(''n'' −1).
*The number ''C
n'' of
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
labeled ''n''-vertex undirected graphs satisfies the
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
::
: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, ...
*The number of labeled ''n''-vertex
free trees is ''n''
''n''−2 (
Cayley's formula
In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^.
The formula equivalently counts the number of spanning tr ...
).
*The number of unlabeled ''n''-vertex
caterpillars
Caterpillars ( ) are the larval stage of members of the order Lepidoptera (the insect order comprising butterflies and moths).
As with most common names, the application of the word is arbitrary, since the larvae of sawflies (suborder Symp ...
is
[.]
::
Graph database
Various research groups have provided searchable database that lists graphs with certain properties of a small sizes. For example
The House of GraphsSmall Graph Database
References
{{reflist, 2
Enumerative combinatorics