# A General Computational Approach for Counting Labeled Graphs
## 3 Methods
As the number of distinct degree sequences for a degree distribution associated with a \(\delta\)-regular graph is one, Equation (8) simplifies to:

\[|c_{\phi_{2a}}(d)|=|c_{\phi_{2}}(D(d))|. \tag{23}\]

Using Algorithm 1, we generate a sequence of edges \(E\), where \(E\) specifies a 2-regular graph of size \(n\). The edge list \(E\) contains 1000 edges. A partial list of the edges in \(E\), denoted as a pair consisting of Vertex 1 and Vertex \(2\in\{1,\ldots,1000\}\), are shown in Table 2. Using the edge list \(E\), we generate a series of graphs, \(G_{0},\ldots,G_{1000}\), where \(G_{i}\) is the graph that contains the first \(i\) edges in \(E\). Next, we generate a series of degree distributions \(\{x_{0},\ldots,x_{1000}\}\), where \(x_{i}=\phi_{2}(G_{i})\). Table 3 shows a partial list of the degree distribution sequences, i.e., \(x_{i}\). For each consecutive entry in the degree distribution sequences, we can use Equations (4)-(7) to estimate \(r_{\phi}(x_{i},x_{i-1})\). As \(x_{0}\) is only consistent with the empty graph, \(|c_{\phi_{2}}(x_{0})|=1\). We estimate the log number of 2-regular graphs as 5907.899; as we see in the next section an existing formula by [PERSON] et al. [9] estimates this as 5907.352. \begin{table}
\begin{tabular}{c c} \hline
**Vertex 1** & **Vertex 2** \\ \hline \(v_{1}\) & \(v_{2}\) \\ \(v_{1}\) & \(v_{3}\) \\ \(v_{4}\) & \(v_{5}\) \\ \(v_{4}\) & \(v_{6}\) \\ \(\cdots\) & \(\cdots\) \\ \(v_{14}\) & \(v_{15}\) \\ \(v_{11}\) & \(v_{12}\) \\ \(v_{8}\) & \(v_{9}\) \\ \(v_{5}\) & \(v_

#### 4.2.2 Comparison

As in the previous section, we illustrate the validity of the recursive formula in this setting by comparing the estimates of \(|c_{\phi_{2a}}(d)|\) based on the proposed recursive formula to those that result from an existing formula. In particular, we compare results of the proposed recursive approach to those resulting from the available formula for estimating the number of \(\delta\)-regular graphs of size \(n=1000\). [PERSON] et al. [9] proved the validity of a general asymptotic formula--conjectured in 1990--for the number of graphs with given degree sequence. They also provide a formula that converges to the number of \(\delta\)-regular graphs as \(n\to\infty\). This formula allows comparison of \(|c_{\phi_{2a}}(d)|\), where \(d\) is the degree sequence \(d=\{\delta,\ldots,\delta\}\), obtained from this asymptotic formula to those from the proposed recursive formula. Figure 1 shows log estimates for the number of \(\delta\)-regular graphs for \(\delta\) from 1 to 10 for the two approaches. The red bars depict estimates based on the recursive formula introduced in this paper; the blue bars are estimates based on [PERSON] et al. [9]. Each plot in Figure 1 shows log estimates for graphs of size 1000, 5000, and 10,000. The log estimates differ by less than 0.01%. To calculate the number of graphs with a given degree sequence based on the recursive formula, we first make use of the Havel-Hakimi algorithm, which has a complexity of \(O(n^{2})\)[18]. Next, the ratio presented in Equation (4) must be computed \((\sum_{i=1}^{n}d)/2\) times, where each calculation of the ratio is \(O(1)\). Finally, we calculate the number of degree sequences that are associated with a degree distribution, which has complexity \(O(n)\). Therefore, the complexity of the recursive formula for calculating the number of graphs of size \(n\) with a degree sequence \(d\) is \(O(n^{2})+O((\sum_{i=1}^{n}d)/2)\). \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Degree 0** & **Degree 1** & **Degree 2** & **Degree 3** & \\ \hline \(x_{0}\) & 1000 & 0 & 0 & 0 \\ \(x_{1}\) & 998 & 2 & 0 & 0 \\ \(x_{2}\) & 997 & 2 & 1 & 0 \\ \(x_{3}\) & 995 & 4 & 1 & 0 \\ \(x_{4}\) & 994 & 4 & 2 & 0 \\ \(\ldots\) & \(\ldots\) & \(\ldots\) & \(\ldots\) & \(\ldots\) \\ \(x_{996}\) & 0 & 8 & 992 & 0 \\ \(x_{997}\) & 0 & 6 & 994 & 0 \\ \(x_{998}\) & 0 & 4 & 996 & 0 \\ \(x_{999}\) & 0 & 2 & 998 & 0 \\ \(x_{1000}\) & 0 & 0 & 1000 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: A partial list of the degree distribution sequences.