Counting labeled graphs

Labeled graphs

Let the number of vertices in a graph be \(n\). We have to compute the number \(G_n\) of labeled graphs with \(n\) vertices (labeled means that the vertices are marked with the numbers from \(1\) to \(n\)). The edges of the graphs are considered undirected, and loops and multiple edges are forbidden.

We consider the set of all possible edges of the graph. For each edge \((i, j)\) we can assume that \(i < j\) (because the graph is undirected, and there are no loops). Therefore the set of all edges has the cardinality \(\binom{n}{2}\), i.e. \(\frac{n(n-1)}{2}\).

Since any labeled graph is uniquely determined by its edges, the number of labeled graphs with \(n\) vertices is equal to:

\[ G_n = 2^{\frac{n(n-1)}{2}} \]

Connected labeled graphs

Here, we additionally impose the restriction that the graph has to be connected.

Let's denote the required number of connected graphs with \(n\) vertices as \(C_n\).

We will first discuss how many disconnected graphs exists. Then the number of connected graphs will be \(G_n\) minus the number of disconnected graphs. Even more, we will count the number of disconnected, rooted graphs.A rooted graph is a graph, where we emphasize one vertex by labeling it as root. Obviously we have \(n\) possibilities to root a graph with \(n\) labeled vertices, therefore we will need to divide the number of disconnected rooted graphs by \(n\) at the end to get the number of disconnected graphs.

The root vertex will appear in a connected component of size \(1, \dots n-1\). There are \(k \binom{n}{k} C_k G_{n-k}\) graphs such that the root vertex is in a connected component with \(k\) vertices (there are \(\binom{n}{k}\) ways to choose \(k\) vertices for the component, these are connected in one of \(C_k\) ways, the root vertex can be any of the \(k\) vertices, and the remainder \(n-k\) vertices can be connected/disconnected in any way, which gives a factor of \(G_{n-k}\)). Therefore the number of disconnected graphs with \(n\) vertices is:

\[ \frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k} \]

And finally the number of connected graphs is:

\[ C_n = G_n - \frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k} \]

Labeled graphs with \(k\) connected components

Based on the formula from the previous section, we will learn how to count the number of labeled graphs with \(n\) vertices and \(k\) connected components.

This number can be computed using dynamic programming. We will compute \(D[i][j]\) - the number of labeled graphs with \(i\) vertices and \(j\) components - for each \(i \le n\) and \(j \le k\).

Let's discuss how to compute the next element \(D[n][k]\) if we already know the previous values. We use a common approach, we take the last vertex (index \(n\)). This vertex belongs to some component. If the size of this component be \(s\), then there are \(\binom{n-1}{s-1}\) ways to choose such a set of vertices, and \(C_s\) ways to connect them.After removing this component from the graph we have \(n-s\) remaining vertices with \(k-1\) connected components. Therefore we obtain the following recurrence relation:

\[ D[n][k] = \sum_{s=1}^{n} \binom{n-1}{s-1} C_s D[n-s][k-1] \]