Open access peer-reviewed chapter

Combinatorial Enumeration of Graphs

Written By

Carlos Rodríguez Lucatero

Submitted: May 16th, 2019 Reviewed: July 24th, 2019 Published: August 31st, 2019

DOI: 10.5772/intechopen.88805

Chapter metrics overview

720 Chapter Downloads

View Full Metrics


In this chapter, I will talk about some of the enumerative combinatorics problems that have interested researchers during the last decades. For some of those enumeration problems, it is possible to obtain closed mathematical expressions, and for some other it is possible to obtain an estimation by the use of asymptotic methods. Some of the methods used in both cases will be covered in this chapter as well as some application of graph enumeration in different fields. An overview about the enumeration of trees will be given as an example of combinatorial problem solved in a closed mathematical form. Similarly, the problem of enumeration of regular graphs will be discussed as an example of combinatorial enumeration for which it is hard to obtain a closed mathematical form solution and apply the asymptotic estimation method used frequently in analytic combinatorics for this end. An example of application of the enumerative combinatorics for obtaining a result of applicability criteria of selection nodes in a virus spreading control problem will be given as well.


  • combinatorial graph enumeration
  • generating functions
  • probability

1. Introduction

Enumerating a finite set of objects is one of the most basic tasks that can be done by any person. Anybody begins to do it at first while learning the basic arithmetic operations at school. In a very general setting, to enumerate a finite set of things is to put in bijective relation a finite subset of the natural numbers with the things to be counted. As simple as it can be at first sight, the enumeration of things can become a very interesting mathematical activity when we start to count, for instance, in how many ways can we dispose or can we select the nelements of set in kplaces without repeating them, sometimes allowing repetitions of all of them, or just some of them, etc. That is the starting point of the combinatorics subject. Combinatorics is the field of discrete mathematics that allows us, among other things, to calculate in how many ways some objects can be selected or arranged to comply with any given property.

Within the topic of combinatorial analysis, there is a subfield that is interested in accurately predicting large structured configurations under the analytical method approach and that uses the tool known as generating functions. The analytic combinatorics is devoted to the study of finite structures whose construction follows a certain finite number of given rules. On the other hand, the use of generating functions is a tool that allows to relate discrete analysis proper to discrete mathematics with continuous analysis.

One of the most beautiful and ingenious applications of combinatorial enumeration is the probabilistic method. The probabilistic method is intimately related to the important role that randomness plays in the field of theoretical computer science. The utility and beauty of the probabilistic method consists of being an indirect or nonconstructive proof method. This method has been used successfully during the last 60 years and constitutes one of the most important scientific contributions of the great Hungarian mathematician Erdös [1, 2]. Commonly, this method has been used to prove the existence of a certain mathematical object by showing that if we choose some object of a given class in a random way, the probability that this mathematical object complies with certain property is greater than zero.

The probabilistic method has been used with great success to obtain important results in fields as diverse as number theory, combinatorics, graph theory, linear algebra, computational sciences, or information theory.

One aim of combinatorial analysis is to count the different ways of arranging objects under given constraints. Sometimes the structures to be counted are finite and some other times they are infinite. To enumerate is very important in many scientific fields because it allows to evaluate and compare different solutions to a given problem. For example, in computer science, if I want to compare different algorithms that solve a given kind of information processing problem, it is necessary to enumerate the number of steps taken by each one of them in the worst case and to choose the one whose performance is the best. The task of enumerating things can evolve in complexity to some point that the elementary arithmetical operations are not enough to reach the goal. For that reason many enumeration problems have inspired the most talented mathematicians for developing very ingenious methods for solving them. Some of these techniques for solving combinatorics enumeration problems are going to be exposed in the next section. One very interesting subject of the discrete mathematics is the graph theory. It is in the graph theory where many of the most interesting enumerations of graphs arise that have some given structural property that require the utilization of mathematical tools that facilitate the discovery of closed mathematical forms for the calculation of the number of graphs that accomplish some topological property. In this context it can be important to enumerate how many labeled graphs can be constructed with nvertex or how many connected graphs with nvertex exist, etc. For some of these problems, clever methods have been devised for their calculation that lead to closed mathematical forms by the use of generating functions. For other problems, it is very hard to obtain a closed mathematical form solution, and in that case some asymptotic methods have been developed for estimating a bound when the number of vertex is very large by means of the Cauchy theorem. These mathematical tools are going to be covered in the following sections of the present chapter.


2. Body of the manuscript

The chapter will have the following structure. In Section 3, we will make a quick revision of some mathematical tools that are frequently used for solving combinatorial enumeration problems. The first tool described will be the ordinary generating functions as well as the exponential generating functions. These tools are used when a closed form solution for an enumeration problem can be obtained. The second tool that will be described in this section will be the analytic combinatorics method that is normally used for those enumeration problems whose closed mathematical form are hard to be calculated. The analytic combinatorics techniques allow to estimate an upper bound of that kind of enumeration problems. We take the enumeration of labeled trees as an example of combinatorial enumeration problem that can be solved in a closed mathematical form and make an overview of some different methods devised for that end in Section 4. In Section 5, we roughly describe how the generating functions can be used to solve graph enumeration problems. In Section 6, we take the problem of enumerating regular graphs as an example of a problem whose closed mathematical form is hard to obtain and apply the analytic combinatorics techniques for estimating an upper bound. In Section 7, I give an application of the combinatorial enumeration for proving the almost sure applicability of a node selecting criteria for controlling virus spreading in a complex network. Finally in Section 8, we make some comments about the possible future applications of the combinatorial enumeration methods.


3. Generating functions and analytic combinatorics overview

In this section of the chapter, we are going to make a revision of the basic mathematical tools that have been developed and that facilitate the solution of many combinatorial enumeration problems. We are going to start with some basic conceptual definitions that can be found in many textbooks about this topic. In order to be able to clearly expose the mathematical tools used, it will be necessary to make use of some basic concepts about them that can be consulted more widely in texts such as [3]. One of these basic notions that can be found in [3] is the concept of combinatorial classwhose definition is as follows:

Definition 1.1 A combinatorial class is a finite or denumerable set in which a size function is defined, satisfying the following conditions:

  1. The size of an element is a nonnegative integer.

  2. The number of elements of any given size is finite.

On the other hand, it is necessary to know if two combinatorial classesare related in any way which can be determined using the concept of isomorphismand that can be defined as follows:

Definition 1.2 The combinatorial classes Aand Bare said to be (combinatorially) isomorphic which is written ABif and only if their counting sequences are identical. This condition is equivalent to the existence of a bijection from Ato Bthat preserves size, and one also says that Aand Bare bijectively equivalent.

The notion of ordinary generating functions (OGF) as i=0aixiwhere the coefficients aiare elements of the sequence A=a0a1or combinatorial class A. This function is also the generating function of the numbers Anwhose sizes an=cardAnsuch that the OGF of class Aadmits the combinatorial form


This means that the variable xmarks size in the generating function. The OGF form (1) can be easily interpreted by observing that the term xnoccurs as many times as there are objects in Aof size n. A basic operation that can be defined is the one that allows to extract the coefficient of the term xnin the power series Ax=anxnas follows:


The concept of generating function can then be defined as:

Definition 1.3 Let be a0,a0,a succession of real numbers. The function


is the generating function of the given succession.

The idea comes from the development of Newton’s binomial that con be defined as:

Definition 1.4


which is the generating function of the succession


We can say, for example, that


is the generating function of the succession 1,1,1,,1,0,0,0,where the first n+1terms are equal to 1. The upper limit of the generating function 6 can be extended to which is known as geometric series. This series is known to be convergent if x<1and that case can be defined as


which is the geometric series of the succession 1,1,1,. One of the nice properties of the generating functions is that they can be easily manipulated due to the fact that they are infinite polynomials.

For instance, if we take the first derivative of the generating function 7, we get


then 11x2is the generating function of the succession 1,2,3,4,, while x1x2is the generating function of the succession 0,1,2,3,4,. Similarly if we take the first derivative of the generating function x1x2, we get


then x+11x3is the generating function of the succession 12,22,32,, and xx+11x3is the generating function of the succession 02,12,22,32,Other simple manipulations that can be done with the generating functions allow us to cancel some element of an associated succession. For example, if gx=11xand hx=gxx2=11xx2, then hxbecomes the generating function of the succession 1,1,0,1,1,1,. By the other side, if we know that xx+11x3is the generating function of the succession 02,12,22,32,and that x1x2is the generating function of the succession 0,1,2,3,4,, then if we add these two generating functions, we get


where 2x1x3becomes the generating function of the succession 0,2,6,12,20,30,42,whose nth element can be expressed as an=n2+n. If we use the coefficient extracting operator defined by 2, we can say that


As an example, let us take the sequence 0,1,1,2,3,5,8,13,21,34,55,know as Fibonacci numbers. This succession can be generated by applying the recurrence relation


The goal is to obtain nth element of the succession of numbers generated by 12 that is the coefficient of xnin the expansion of the function


as a power series about the origin. The roots of 1xx2are x1=1+52and x2=152. Given that the generating function of the Fibonacci succession is 13, we have that


and the nth term of the Fibonacci succession is expressed in closed form as


The calculation of the n-th term of the Fibonacci sequence by using power series allows us to obtain a mathematical closed formula. Because of that we can calculate the n-th term of the Fibonacci sequence in a more efficient way given that the computer program to do it will consist in the direct application of the closed mathematical expression obtained, which is much more efficient than using a computer program based on the application of the Fibonacci recurrence.

In [4] the problem of the various results that can be obtained using generating functions is addressed. The authors of [4] say that by using the tool of generating functions for obtaining the nth element of a succession, sometimes an exact formula can be obtained easily, and if it is not the case, a good estimation of the nth element can be obtained. It can happen also that we get a recurrence formula from where a generating function can be obtained, or it can happen that from the generating function a new recurrence is obtained giving us a deeper understanding about the succession. The use of generating functions provides statistical information about the succession. The authors of [4] also point out that when it is very difficult to mathematically obtain the n-th term of a given sequence as a closed mathematical expression, a good option is to use asymptotic methods to obtain an estimate of that term. For example, the nth prime number is approximately nlognwhen nis very big. The authors of [4] also also point out that using generating functions some properties of a succession such as unimodality or convexity can be proven. Another advantage of using generating functions is that some identities as, for example,


are easy to obtain. Finally, the authors of [4] pointed out that by using generating function, the relationship between problems that have similar generating functions can be discovered.

As was mentioned in the last paragraph, sometimes it is hard to obtain mathematically closed formulas when using generating functions, and in that case, a good alternative is to the use asymptotic formulas. The mathematical tools used for this purpose are part of the field known as analytic combinatorics, and a good reference of this topic is [3]. The main objective of analytic combinatorics is to estimate with a high level of precision the properties of large structured combinatorial configurations by the use of mathematical analysis tools [3].Under this approach, we begin with an exact enumerative description of the combinatorial structure using the generating functions. This description is considered as an algebraic object. The next step is to take the generating function as an analytical object which is a mapping from the complex plane to itself. The singularities found in such a mapping allow to obtain the coefficients of the function in its asymptotic form, resulting in an excellent estimate on the count of the sequences. With this purpose, the authors of [3] classify the analytic combinatorics in the next three topics:

  1. Symbolic methods that establish systematically relations of discrete mathematics constructions and operations on generating functions that encode counting sequences

  2. Complex asymptotics that allow for extracting asymptotic counting information from the generating functions by the mapping to the complex plane mentioned above

  3. Random structures concerning the probabilistic properties accomplished by large random structures

A large material concerning the subject of complex asymptotic analysis is addressed in [5]. A highly recommended text to consult because it covers the applications of the combinatorial tools enumerative to the analysis of algorithms is [6]. In this chapter, there will be a particular interest in the application of generating functions tool for the enumeration of graphs that have some given properties.

Let us start with the definition of a graph. A graph G=VEis a structure with a set of vertices V=v1v2vpwhose size V=pit is called the order of Gand a set of unordered pairs of adjacent vertices, called edges, E=vi1vj1vi2vj2viqvjqif Gis undirected or a set of ordered pairs of adjacent vertices E=vi1vj1vi2vj2viqvjq, if Gis a directed graph, whose edge set size is E=q, that has no loops and that has no loops multiple edges. A graph Gwith pvertices and qedges is called a pqgraph. In a labeled graph of order p, each vertex has a label that is an integer from 1 to p. Typical questions such as how many graphs can be constructed with nvertices, how many trees with nvertices can be obtained, and how many of these trees are binary can be answered using the generating functions, and a mathematically closed formula can be obtained. In the case that a closed mathematical formula is very hard to be obtained, an accurate asymptotic estimation formula can be a good option.

There are two commonly used generating functions: the first is the ordinary generating functions (OFG) and the other is the exponential generating functions (EGF).

An ordinary generating function is a mathematical function defined by the following expression:


where the coefficients are elements of the succession of numbers a0,a1,a2,. The ordinary generating functions are used for enumeration problems where the order of the objects is not important. An exponential generating function is a mathematical function defined by the following expression:


where the coefficients are elements of the succession of numbers b0,b1,b2,. The exponential generating function are used for enumeration problems where the order of the objects matter. Graphs, words, trees, or integer partitions are some of the kinds of objects with which combinatorics deals. Combinatorics deals with discrete objects as, for example, graphs, words, trees, and integer partitions. Counting such objects is one of the most interesting tasks. Enumeration of graphs that have some structural property is the main purpose of the present chapter.

The great mathematician George Pólya made huge contributions to the field of graph enumeration graphs. He obtained closed mathematical expressions for the enumeration of graphs with a given number of vertices and edges for many graph counting problems using group theory [7]. Pólya’s formulas greatly facilitated the enumeration of rooted graphs, connected graphs, etc. The enumeration of number of triangulations of certain plane polygons was one of the first problems of enumeration that attracted the attention of the great mathematician Leonhard Euler [8] in the eighteenth century. Some years later, Kirchhoff in [9] discovered a method for enumerating spanning trees in a connected graph. After that, Arthur Cayley obtained a closed mathematical formula that enumerates labeled trees, rooted trees, and ordinary trees in [10]. The Cayley discovery will be covered with more detail in Section 4. The brilliant and unknown mathematician John Howard Redfield [11] discovered many enumeration formulas anticipating some of Pólya’s contributions.

Some enumeration problems of objects that are not graphs (automata, Boolean functions, or chemical isomers) can be solved by cleverly transforming them to graphs. The generating functions are the tool used for enumerating graphs. There are two types of graphs associated with combinatorial graph enumeration problems:

  1. Labeled graph problems

  2. Unlabeled graph problems

Some enumeration problems of labeled graphs are normally addressed by applying the exponential generating functions tool. The enumeration problems of unlabeled graphs are normally addressed by applying the ordinary generating functions but require the application of Pólya’s theorem.

One of the first problems of enumerating labeled graphs that may arise is that of how many graphs with pvertices and qedges can be obtained.

To solve this enumeration problem, let Gpxbe the polynomial or ordinary generating function whose coefficient of the term xkrepresents the number of labeled graphs with pvertices and kedges. If Vis the set of vertices of cardinality p, there are q=p2pairs of these vertices. In every vertex set V, each pair is adjacent or not adjacent. The number of labeled graphs with kedges is therefore qk=p2k. Thus, the ordinary generating function Gpxfor labeled graphs with pvertices is given by


where m=p2. Then, the number of labeled graphs with pvertices is Gp1; so we have:


For example, if we want to know how many labeled graphs with p=3vertices can be obtained, we apply Formula (20), and we get:


If we want to know how many labeled graphs with p=4vertices and exactly q=5edges exist, before expression (19), we use the coefficient of the term x5


A question that arises naturally when working with labeled graphs is in how many ways can this be constructed from a certain number of vertices and edges. In order to give a possible answer, the number of symmetries or automorphisms must be taken into account. It is said that there is isomorphism between two graphs Gand G1 if there is a one-to-one map A:VGVG1between them that preserve adjacency. When G1=G, then the mapping Ais called automorphism of G. The set of all the automorphisms of G, represented by ΓG, is called the group of G. The elements of ΓGare permutations over V. Let sG=ΓGbe the order of the group or number of symmetries of G. Therefore, the number of ways in which a graph Gof order pcan be labeled is


Another example of graph enumeration problem is to count the number of differently labeled connected graphs. The notion of path of length nis defined as a sequence of vertices v0v1vnwhere the edges vivi+1for i=0,nthat belong to the path are distinct. It is said that a graph is connected if for any pair of vertices there is a path between them. To obtain the formula that counts all the connected graphs Cpof order p, it will be necessary to make use of the concept of subgraph. It is said that a His a subgraph of a graph Gif VHVGand EHEG. A subgraph that is maximally connected is called component. A rooted graph is a graph that has a distinguished vertex called root. When there exists an injective mapping f:VH1VH2between two rooted graphs H1and H2that preserves the adjacency among vertices as well as the roots, it is said that the two rooted graphs are isomorphic. Let us make the assumption that akfor k=1,2,3,represents the number of ways in which we can label all graphs of order that accomplish the property Paand whose exponential generating function is


Let us also assume that bkfor k=1,2,3,is the number of ways of labeling all graphs of order that accomplish the property Pband whose exponential generating function is


If we make the product of series (24) and (25), the coefficients of xkk!in axbxis the number of ordered pairs G1G2of two disjoint graphs, where G1meets the property Pa, G2fulfills the property Pb, kis the number of vertices in G1G2, and the labels from 1 to khave been distributed over G1G2. If Cxis the exponential generating function for labeled connected graphs


then CxCxbecomes the generating function that counts all the ordered pairs of connected graphs with labels. If you divide by 2, equation (26) that is, we divide it by 2, we get the generating function for labeled graphs that have exactly two components.

By applying this operation ntimes, the coefficient of xkk!that corresponds to the number of labeled graphs of order kis obtained with exact ncomponents


From (27), we obtain the following relation


Riordan in [12] obtained the relation Cp=Jp2, where Jpxenumerates the trees by inversions, and then deduced


From (29), it should be noted that if the exponential generating function for the graph class is known in advance, then the exponential generating function for the class of graphs will be the logarithm of the first series, just as in (28). It should also be mentioned that another equivalent recurrence function can be obtained for the enumeration of the connected graphs that have order tags p(p. 7 in [13]) and that can be expressed mathematically as


From (30), the following MATLAB code can be implemented for calculating the number of connected graphs Cpof orders going from p=1to p=20.

function y = CuentaGrafConnEtiq( p )

% recurrence satisfied by the number of connected graphs

% Harary Graph Enumeration pag. 7

% C_p= 2ˆ{combinations(p,2)}-1/p* \sum_{k=1}ˆ{p-1} k*

% combinations(p,k)*2ˆ{combinations(p-k,2)}*C_{k}



for k=2:p


for j=1:k

  acum = acum + j * combinaciones(k,j) * CuentaGrafEtiq(k-j) * C(1,j);


C(1,k) = CuentaGrafEtiq(k)-(1/k)*acum;



sprintf(‘end function z=combinaciones(n,k) z= factorial(n)/(factorial(k)*factorial(n-k));


function z=combinaciones(n,k)

  z= factorial(n)/(factorial(k)*factorial(n-k));


%% calling the function from the matlab prompt for the calculation of the

%% evaluation from graphs of order 1 to 20

>> for i=1:20

  R(1,i)=CuentaGrafConnEtiq( i );


The calculations obtained by the execution of MATLAB code are shown in Table 1.


Table 1.

Order 1–20.

From the results of 1, it can be observed that the number of possible connected graphs Cpgrows very fast in terms of the number pof vertices. It should be mentioned that (29) and (30) are recurrence relations instead of a closed formula. The recurrences (29) or (30) can be used for the calculation of Cpwith a computer program. The generating functions can be used to solve recurrences and obtain a closed mathematical expression for the nth term of the succession associated with the recurrence. It can happen that calculation of the solution of some recurrences becomes very hard to be solved and in the worst cannot be solved at all. An alternative method for obtaining an approximate value for big values of pis to recur to the application of methods used in analytic combinatorics and calculate accurate approximations of the pth coefficient of the generating function. The generating functions algebraic structure allows to reflect the structure of combinatorial classes. The analytic combinatorics method consists in examining the generating functions from the point of view of the mathematical analysis by giving not only real value values to its variables but also values in the complex plane. When complex values are assigned to the variables of the generating functions, the function is converted in a geometric transformation of the complex plane. This kind of geometrical mapping is said to be regular (holomorphic) near the origin of the complex plane. When we move away from the origin of the complex plane, some singularities appear that are related with the absence of smoothness of the function and give a lot of information about the function coefficients and their asymptotic growth. It can happen that elementary real analysis is enough for estimating asymptotically enumerative successions. If this is not the case, the generating functions are still explicit, but its form does not allow the easy calculation of the coefficients of the series. The complex plane analysis however is a good option for asymptotic estimation of these coefficients. In order to give an example of the use of the notion of singularities, let us take the ordinary generating function of the Catalan numbers


Eq. (31) expresses in a compact way the power series of the form


The generating function (31) coefficients can be explicitly expressed as


Using the Stirling formula, we can get the asymptotic approximation of (33) that is expressed as


If the generating function is used as an analytic object, the approximation (34) can be obtained.

In order to do it, we substitute in the power series expansion of the generating function f(x) any real or complex value ρfwhose modulus is small enough, for example, ρf=4. The graph that we get by the use of (31) is smooth and differentiable in the real plane and tends to the limit 12as x14, but, if we calculate its derivative, we obtain the following function


and it can be noticed that the derivative (35) becomes infinite in ρf=14. The singularities will correspond to those points where the graph is not smooth.

It should be pointed out that that the region where function (31) is still being continuous can be extended. Let us take for example the value x=1


We can evaluate in the same manner (31) giving to xvalues in the complex plane whose modulus is less than the radius of convergence of the series defined by (31) and realize that the orthogonal and regular grid in it transforms the real plane in a grid on the complex plane that preserves the angles of the curves of the grid. This property corresponds to the complex differentiability property, which also is equivalent to the property of analyticity. Concerning the asymptotic behavior of the coefficients fnof the generating function, it should be observed that it has a general asymptotic pattern composed by an exponential growth factor Anand a subexponential factor θn.

For the case of the expression (34) A=4and θn14πn31, the exponential growth factor can be put in relation with the radius of convergence of the series by A=1ρfthat is the singularity that can be observed along the positive real axis of the complex plane that normally corresponds to the pole of the generating function, and the subexponential part θn=On32arises from the singularity of the square root type. This asymptotic behavior can be compactly expressed as


The exponential growth part of (37) is known as first principle of coefficient asymptotics and the subexponential growth part as second principle of coefficient asymptotics. By recalling to the results that can be found in the field complex variable theory, more general generating functions can be obtained. One of those results is the Cauchy residue theorem that relates global properties of a meromorphic function (its integral along closed curves) to purely local characteristics at the residues poles. An important application of the Cauchy residue theorem concerns a coefficient of analytic functions. This is stated in the following theorem [3]:

Theorem 1.5 (Cauchy’s coefficient formula). Let fzbe analytic in a region containing 0, and let λbe a simple loop around 0 that is positively oriented. Then, the coefficient znfzadmits the integral representation:


For more details about analytic combinatorics, we recommend to consult [3] as well as [5].


4. Enumeration of trees

A graph is a structure composed by a set of vertices V=v1v1vnand a set of pairs of connected vertices E=e1e2emcalled edges where EV×Vand each edge ekEis composed as pair of vertices ek=vivj. A tree is a special type of graph that do not have cycles. A tree have no loops or edges that connect a vertex with himself. The subject of combinatorial graph enumeration has been the center of interest of many mathematicians a long time ago. The enumeration of total possible labeled trees with nnodes being nn2was one of first results obtained by Cayley in [10]. Cayley’s formula for enumerating trees is one of the simple and elegant mathematical results in enumeration of graphs. He detected that from n+1vertices, the number of possible trees that can be built is equal to n+1n1. Cayley [10] gives an example for the case of four vertices 4=n+1then n=3, and the total number of possible trees calculated using his formula gives 42=16. In this same publication, Cayley gives another example having n+1=6vertices (he used the term knots in his publication) with labels a,b,c,d,e,fand related the concatenation of vertices given by the edges for obtaining sequences of labels representing a given tree. For instance, if the tree is a chain of vertices connected by edges starting with the vertex aand ending with the vertex fand having as connecting edges ab,bc,cd,de,ef, the corresponding label sequence is abcdefas shown in Figure 1. As another example of sequence of vertex labels, if the root of the tree is αand it is connected directly with the other five vertices, then the connecting edges will be ab,ac,ad,ae,af, and the corresponding sequence of vertex labels will be in that case a5bcdefas shown in Figure 2. As can be noticed, the exponent of ais 5 that represents the number of occurrences of this label in the set of connecting edges.

Figure 1.

Example of tree of one branch.

Figure 2.

Example of tree with more branches.

After that Cayley states the theorem for this particular case as follows:

Theorem 1.6 The total number of trees Tn+1that can be built with n+1=6vertices can be calculated as follows


This calculation relates the sum of the products of the coefficients of the multinomial a+b+c+d+e+f4with the number of terms of its corresponding type. Each term obtained by multiplying abcdefwith the vertex label inside a+b+c+d+e+f4corresponds to different trees.

At the end of [10], Cayley generalizes his theorem by recalling a result obtained by C.W. Borchardt in [14] that relates some particular kind of determinants that represent spanning trees and whose product represents the branches of those spanning trees. Given that the number of terms of these determinants is n+1n1, Cayley can conclude that the number of spanning trees is the same. Since these first results, many other methods have been proposed for obtaining the same result. One way to enumerate a collection of objects is to find a bijection between a set of objects whose enumeration is known and the set of objects that we want to enumerate. This was the method used by Prüfer in [15] for enumerating the set of possible spanning trees with nvertices. The set whose number was known beforehand was a sequence of length n2of numbers from 1 to n. For this end the autor of article [15] encoded the trees as Prüfer sequences. In [16] Moon generalized the result derived by Clarke in [17] by induction on dthe degree, making induction on n, and the number of vertices and obtains a new enumeration method for n-labeled ktrees.


5. Enumeration and generating functions

The field of combinatorial enumeration has aroused enormous interest among mathematicians who have worked in the area of discrete mathematics during the last decades [18, 19, 20, 21]. Combinatorial enumerative technique developed by these brilliant researchers have allowed us to count words, permutations, partitions, sequences, and graphs. As was mentioned in Section 3, the mathematical tool frequently used for this purpose is the generating functions or formal power series.

The generating functions allow to connect discrete mathematics and continuous analysis in a very special way with complex variable theory. The typical situation that someone faces when trying to solve an enumeration problem is that you want to know the mathematically closed form that has the nth term of a given sequence of numbers a0,a1,a2,For some sequences, we can do by inspection. For example, if the numerical sequence 1,3,5,7,9,, it is easy to see that it is a sequence of odd numbers whose nth element is an=2n1.

A more complicated sequence is the set of prime numbers 2,3,5,7,11,13,17,19,, whose anis the nth prime number. A closed mathematical formula for nth prime number is not known, and it seems impossible to obtain in general.

In many cases it is very hard to get a simple formula just by inspection. However it can be very useful to use the generating functions whose coefficients are the elements of that sequence transforming it as follows:


Eq. (40) defines an ordinary generating function. As mentioned in Section 3, since they are infinite polynomials, they can be algebraically manipulated easily.

In this chapter, the main interest will be the application of the generating functions tool as well as the analytic asymptotic methods for the enumeration of graphs accomplishing some given properties. Many questions about the number of graphs that have some specified property can be answered by the use of generating functions. Some typical questions about the number of graphs that fulfill a given property are, for example: How many different graphs can I build with nvertices? How many different connected graphs with nvertices exist? How many binary trees can be constructed with nvertices? [18, 19], etc. For some of these questions, the application of generating functions allows us to easily obtain a simple formula. For some other questions, the answer is an asymptotic estimation formula. The most commonly used generating functions are the ordinary generating functionsand the exponential generating functions. The generating functions are the tool used for enumerating graphs. From the point of view of the generating functions, there are two types of graph enumerating problems:

  1. Labeled graph problems

  2. Unlabeled graph problems

The labeled graph problems can be easily solved with the direct application of the exponential generating functions. The case of the unlabeled enumeration problems can be solved by using ordinary generating functions but require the use of more combinatorial theory and the application of Pólya’s theorem.


6. Enumerating regular graphs

As we mentioned in Section 6, some enumerating problems can be solved easily using generating tools for obtaining a closed formula. Some other problems are more hard to deal with for obtaining a closed mathematical expression, but we can resort in such a case to the asymptotic approximation of the coefficients of the power series [22, 23, 24, 25]. It was also mentioned in Section 6 that there are some graph enumerating problems where the nodes are labeled, and in such a case the use of the exponential generating functionsis well adapted for these kinds of problems. The other case of graph enumerating problems is when we are dealing with graphs whose nodes do not have an assigned label. Then, we can resort in such case to Pólya’s enumerating method [7, 13], and the best choice is to use ordinary generating functions. It should also be mentioned that the edges of the graphs to be enumerated can be directed or undirected.

One of the seminal articles of enumerating graphs is [26], where a fundamental theorem was proven in the theory of random graphs on nunlabeled nodes and with a given number qof edges.

In [26], the authors obtained a necessary and sufficient condition for relating asymptotically the number of unlabeled graphs with nnodes and qedges with the number of labeled graphs with nnodes and qedges. Let Tnqbe the number of different graphs with nnodes and qedges, Fnqthe corresponding to number of labeled graphs, N=nn12the possible edges, and Fnq=Nq=N!q!Nq!. The result obtained in [26] can be stated as the following theorem:

Theorem 1.7 The necessary and sufficient conditions that


as nis that


The formal result expressed in Theorem 1.7 for unlabeled graphs is a starting point on the enumeration of regular graphs because it allows for enumerating those unlabeled graphs that have some number of edges. In fact, the author of [26] proved that if a graph with E=Enedges, where nis the number of vertices or order of such a graph, has no isolated vertices or two vertices of degree n− 1, then the number of unlabeled graphs of order nand number of edges Edivided by the number unlabeled graphs is asymptotic to n!.

Another interesting article on asymptotic enumeration of labeled graphs having a given degree sequence was [27]. The authors of [27] obtained their asymptotic result for n×nsymmetric matrices subject to the following constraints:

  1. Each row sum is specified and bounded.

  2. The entries are bounded.

  3. A specified sparseset of entries must be zero.

The authors of [27] mentioned that their results can be interpreted in terms of incidence matrices for labeled graphs. The results of [27] can be stated as follows. Let Mnzbe the set of all n×nsymmetric 01matrices with at most zzeroes in each row, ra vector over d=01d, and GMrtthe number of n×nsymmetric matrices gijover t=01tsuch that

  1. gij=0if mij=0.

  2. jgij=ri.

Theorem 1.8 For given d,tand z,


Uniformly, for Mrn=1Mnz×0dnas f, where f=iri,ε=1ift=1and+1ift>1, for a=iri2f2+mijri2f,b=mij=0,i<jrirj+iri2f,δ=mij=0riand Tfδbeing the number of involutions on [1, f] such that no element in some specified set of size δis fixed.

Three years later, the article [28] appeared giving a different approach of [27] allowing for obtaining a more general asymptotic formula without reference to an exact formula. The asymptotic result obtained by Bela Bollobás in [28] for enumerating labeled regular graphs is proven by a probabilistic method. This result can be stated as follows. Let Δand nbe natural numbers such that Δn=2mis even and Δ2logn12, where nis the number of vertices and mis the number of edges of the graph G. Then, as n, the number of labeled Δ-regular graphs on nvertices is asymptotic to


where λ=Δ12.

The authors of [27] affirm that the asymptotic Formula (44) holds not only for Δconstant but also for Δgrowing slowly as nand summarized this in the following theorem.

Theorem 1.9 Let d1d2dnbe natural numbers with i=1ndi=2meven. Suppose Δ=d12logn121and mmaxεΔn1+εnfor some ε>0. Then, the number Ldof labeled graphs with degree sequence d=di1nsatisfies


where λ=12mi=1ndi2.

In the next year, the author on [27] extended this result to the case of unlabeled graphs in [29]. The result of Theorem 1.9 extended for the case of unlabeled graphs can be summarized in the following theorem.

Theorem 1.10 If Δ3and LΔ=eλλ22m!m!2mΔ!m, then


where m=Δn2.

For the details of the proof of Theorems 1. 9 and 1.10, see [28, 29], respectively.


7. Example of proof of a result on control using combinatorial enumeration

In [30] I used the combinatorial enumeration methods and probability for showing the applicability of the selection node criteria in a virus spreading control problem in complex networks. The main purpose of this section is to illustrate how the enumerative combinatorics in combination with probability theory can be used for demonstrating mathematically a result in an application field. We can mention that the case of homogeneity in the behavior of the nodes and their interaction cannot be discarded given what has been observed in the reaction of the agents in the context of social networks is that they try to minimize the conflict. Many successful models can, for example [30, 31, 32, 33], base their predicting effectiveness on the homogeneity of the behavior of the nodes and their interaction. By the other side, in [30] we have obtained a criteria for selecting the nodes to be controlled, but such criteria fail if we have homogeneity in the behavior of the nodes and, at the same time, the topology of the network is regular. Then, what we want to do here is to justify the applicability of node selection criteria, keeping the homogeneity of the nodes and trying to compare the number of regular graphs with nvertices with the total of graphs that can be constructed with nvertices. For this end, based on the results on combinatorial graph enumeration mentioned on Theorems 1.9 and 1.10, we can state our main result as follows. First of all, we suppose that our graph is labeled, G=VEis r-regular with r3constant and rn=2m, where n=Vcorresponds to the number of vertices and m=Ecorresponds to the number of edges. Let Lrthe number of labeled regular graphs of degree rwhose asymptotic value is [28]


Let Gnbe the number of all possible graphs with nvertices whose value is


Theorem 1.11 If r3and nr=2m, then


Proof of Theorem 1.11. If nr=2mand ris constant of value c1, then we can deduce that m=r2n=c12n, and this implies that m=Onso let us say that m=c2n; then,


applying the approximation Stirling formula n!2πnnen






applying the approximation Stirling formula




we get




given that r3, for which we assumed that ris a constant c1, and that nr=2m, then we have that c1=2c2, and replacing that, in (58), we can express it in terms of c1, which is the regular degree rassumed as fixed; then, we get


and, replacing c1 by rin (59), we get


Therefore, if the degree ris constant, the limnLrGn=0.

Now, our main result can be stated as a consequence of Theorem 1.11.

Theorem 1.12 If we assume that all graphs are uniformly distributed and that the nodes have homogeneous behavior, then the criteria for selecting nodes to be controlled are almost always applicable.

Proof of Theorem 1.11.As a consequence of Theorem 11, we know that the probability that a regular graph appears tends to zero as n. Then, the mentioned criteria are almost always applicable.


8. Conclusions

In the present chapter, some problems of combinatorial graph enumeration as well as some useful techniques for obtaining a closed mathematical expression were addressed. When it is not possible to obtain a closed expression, asymptotic estimations of the kind used in analytic combinatorics can be used. In Section 10 the use of these techniques for proving a result in the field of virus spreading control was illustrated [31, 32, 33, 34].

This allowed to explore the application of combinatorial techniques to control problems in networks and thus verify the goodness of said methods for network analysis and the control of virus propagation in them. This still needs to be studied by applying the combinatorial methods discussed above, if there are any other types of topologies that prevent the application of the selection criteria of nodes to be controlled under the hypothesis of behavior of partially heterogeneous nodes, that is, if in the network we have subsets of nodes with the same behavioral parameters. The selecting node criteria described in [30] are based on the combination of the parameter values of the selected nodes as well as their degrees. In many recent publications [35, 36, 37, 38, 39, 40, 41, 42], interesting and elaborated methods for detecting the influencer nodes in complex networks have been proposed that I will try to apply in combination with the mentioned criteria in the future in order to reduce the number of nodes to be controlled.


  1. 1. Erdös P. Graph theory and probability. Canadian Journal of Mathematics. 1959;11:34-38
  2. 2. Alon N, Spencer JH. The Probabilistic Method. 2nd ed. New York: Wiley-Interscience; 2000
  3. 3. Sedgewick R, Flajolet P. Analytic Combinatorics. 0th ed. Cambridge, UK: Cambridge University Press; 2005. Fifth printing
  4. 4. Wilf HS. Generating Functionology. 3rd ed. Wellesley, MA, USA: A K Peters Ltd.; 2006
  5. 5. Louis C. Advanced Combinatorics: The Art of Finite and Infinite Expansions. Dordrecht-Holland, The Netherlands; Boston, MA, USA: D. Reidel Publishing Company; 1974
  6. 6. Sedgewick R, Flajolet P. An Introduction to the Analysis of Algorithms; 2nd printing. Boston, MA, USA: Addison-Wesley; 2001
  7. 7. Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica. 1937;68:145-254
  8. 8. Euler L. Journal Novi Comment Acad. Sci. Imperialis Petropolitanae, Holding Institution: American Museum of Natural History Library, 1758–1759, 7, pp. 13–14. Available online:[Accessed: 21 March 2018]
  9. 9. Kirchhoff G. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme gefuhrt wird. Annals of Physical Chemistry. 1847;72:497-508
  10. 10. Cayley A. The collected mathematical papers of Arthur Cayley: A theorem on trees. Cambridge University Press. 1898;13:26-28
  11. 11. Redfield JH. The theory of group-reduced distributions. American Journal of Mathematics. 1927;49:433-455
  12. 12. Mallows CL, Riordan J. The inversion enumerator for labeled trees. Bulletin of the American Mathematical Society. 1968;74:92-94
  13. 13. Harary F, Palmer EM. Graph Enumeration. New York, NY, USA; London, UK: Academic Press; 1973
  14. 14. Borchardt CW. Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante. Journal für die reine und angewandte Mathematik. 1860;(57):111-121
  15. 15. Prüfer H. Neuer Beweis cines Satzesuber Permutationen. Archiv für Mathematik und Physik. 1918;27:142-144
  16. 16. Moon JW. The number of labeled k-trees. Journal of Combinatorial Theory. 1969;6:196-199
  17. 17. Clarke LE. On Cayley formula on counting trees. Journal of the London Mathematical Society. 1958;33:471-475
  18. 18. Graham RL, Knuth DE, Patashnik O. Concrete Mathematics; 6th Printing with Corrections. Boston, MA, USA: Addison-Wesley; 1990
  19. 19. Nijenhuis A, Wilf HS. The enumeration of connected graphs and linked diagrams. Journal of Combinatorial Theory. 1979;27:356-359
  20. 20. Courcelle B, Makowsky JA, Rotics U. On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic. Discrete Applied Mathematics. 2001;108:23-52
  21. 21. Read RC. Some unusual enumeration problems. Annals of the New York Academy of Sciences. 1970;175:314-326
  22. 22. Mackay Brendan D. Asymptotics for symmetric 0–1 matrices with prescribed row sums. Ars Combinatoria. 1985;19A:15-25
  23. 23. Mackay Brendan D, Wormald Nicholas C. Uniform generation of random regular graphs of moderate degree. Journal of Algorithms. 1990;11:52-67
  24. 24. Mackay Brendan D, Wormald Nicholas C. Asymptotic enumeration by degree sequence of graphs of high degree. European Journal of Combinatorics. 1990;11:565-580
  25. 25. Mackay Brendan D, Wormald Nicholas C. Asymptotic enumeration by degree sequence with degreesOn12. Combinatorica. 1991;11:369-382
  26. 26. Wright EM. Graphs on unlabelled nodes with a given number of edges. Acta Mathematica. 1971;126:1-9
  27. 27. Bender EA, Canfield ER. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory. 1978;24:296-307
  28. 28. Bollobás B. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics. 1980;1:311-316
  29. 29. Bollobás B. The asymptotic number of unlabelled regular graphs. Journal of the London Mathematical Society. 1981;1:201-206
  30. 30. Rodrguez-Lucatero C, Alarcón L. Use of enumerative combinatorics for proving the applicability of an asymptotic stability result on discrete-time SIS epidemics in complex networks. MDPI Mathematics Open Access Journal. 2019;7(1). DOI: 10.3390/math7010030
  31. 31. Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C. ACM Transactions on Information and System Security. 2008;10:1-26
  32. 32. Galam S. Rational group decision making: A random field Ising model at T = 0, arXiv:cond-mat/9702163v1; 1997
  33. 33. Axelrod R. The dissemination of culture: A model with local convergence and global polarization. Journal of Conflict Resolution. 1997;41(2):203-226
  34. 34. Gonzalez-Avella JC, Eguiluz VM, Cosenza MG, Klemm K, Herrera JL, San Miguel M. Nonequilibrium transition induced by mass media in a model for social influence. Physical Review E. 2005;72(6) 065102(1-4)
  35. 35. Pei S, Morone F, Makse HA. Theories for influencer identification in complex networks. arXiv 2018. arXiv:physics.soc-ph/1707.01594v2
  36. 36. Cha M, Haddadi H, Benevenuto F, Gummandi PK. Measuring user influence in twitter: The million follower fallacy. In: Proceedings of the 4th International AAAI Conference on Weblogs and Social Media, Washington, DC, USA, 23–26 May 2010; Vol. 10. 2010. pp. 10-17
  37. 37. Watts DJ, Dodds PS. Influential networks and public opinion formation. Journal of Consumer Research. 2007;34:441-458
  38. 38. Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, et al. Identification of influential spreaders in complex networks. Nature Physics. 2010;6:888-893
  39. 39. Pei S, Makse HA. Spreading dynamics in complex networks. Journal of Statistical Mechanics: Theory and Experiment. 2013;2013:P12002
  40. 40. Min B, Morone F, Makse HA. Searching for influencers in big-data complex networks. In: Bunde A, Caro J, Karger J, Vogl G, editors. Diffusive Spreading in Nature, Technology and Society. Berlin, Germany: Springer; 2016
  41. 41. Leskovec J, Adamic LA, Huberman BA. The dynamics of viral marketing. ACM Transactions on the Web. 2007;1:5
  42. 42. Rogers EM. Diffusion of Innovations. New York, NY, USA: Simon and Schuster; 2010

Written By

Carlos Rodríguez Lucatero

Submitted: May 16th, 2019 Reviewed: July 24th, 2019 Published: August 31st, 2019