# A General Computational Approach for Counting Labeled Graphs
## 3 Methods
Inthe application section (Section 5), we present results for the number of labeled graphs associated with particular degree distributions and degree mixing matrices using our presented approach. ### Number of Edges

Although there is a closed-form expression for calculating the number of labeled graphs of size \(n\) with \(m\) number of edges, we use Equation (1) for calculation of this graph property to illustrate our recursive approach for graph enumeration. #### 4.1.1 Example

To illustrate the use of the recursive formula, we provide a numerical example where we estimate the number of graphs of size \(n=1000\) with exactly \(m=10\) edges; that is, we calculate \(|c_{\phi_{1}}(m=10)|\). As discussed in Section 3.1, we set \(x_{0}=0,x_{1}=1,\ldots,x_{k}=10\). Therefore, based on Equation (1):

\[|c_{\phi_{1}}(x_{k}=10)|=r_{\phi_{1}}(x_{k}=10,x_{k-1}=9)\cdot|c_{\phi_{1}}(x_{ k-1}=9)|. \tag{17}\]

Based on Equation (3),

\[r_{\phi_{1}}(x_{k}=10,x_{k-1}=9)=\frac{(\frac{1000}{2})-9}{10}=49949.1. \tag{18}\]

Therefore,

\[|c_{\phi_{1}}(x_{k}=10)|=49949.1\cdot|c_{\phi_{1}}(x_{k-1}=9)|. \tag{19}\]

The next step in the procedure is the calculation of \(|c_{\phi_{1}}(x_{k-1}=9)|\) using the following:

\[|c_{\phi_{1}}(x_{k-1}=9)|=r_{\phi_{1}}(x_{k-1}=9,x_{k-2}=8)\cdot|c_{\phi_{1}}( x_{k-2}=8)|. \tag{20}\]

The procedure ends at \(x_{0}=0\). Therefore,

\[log(|c_{\phi_{1}}(x_{k}=10)|)=\sum_{i=1}^{i=10}log(r_{\phi_{1}}(x_{i},x_{i-1}) )+log(|c_{\phi_{1}}(x_{0}=0)|). \tag{21}\]

Table 1 provides the log values for \(r(x_{i},x_{i-1})\) for \(i=1\) to \(10\). Based on these values and noting that \(|c_{\phi_{1}}(x_{0}=0)|=1\), we calculate \(log(|c_{\phi_{1}}(x_{k}=10)|)=116.11\). \begin{table}
\begin{tabular}{c c c c} \hline \(x\) & \(log(r(x,x-1))\) & \(log(|c_{\phi_{1}}(x)|)\) & \(log(|c_{\phi_{1}}(x)|)\) \\  & & **[Equation (1)]** & **[Equation (22)]** \\ \hline
0 & – & 0 & 0 \\
1 & 13.12 & 13.12 & 13.12 \\
2 & 12.42 & 25.55 & 25.55 \\
3 & 12.02 & 37.57 & 37.57 \\
4 & 11.74 & 49.31 & 49.31 \\
5 & 11.51 & 60.82 & 60.82 \\
6 & 11.33 & 72.15 & 72.15 \\
7 & 11.18 & 83.32 & 83.32 \\
8 & 11.04 & 94.37 & 94.37 \\
9 & 10.92 & 105.29 & 105.29 \\
10 & 10.82 & 116.11 & 116.11 \\ \hline \end{tabular}
\end{table} 
Table 1: Comparison of methods to calculate number of edges. #### 4.1.2 Comparison

To illustrate the validity of the recursive formula in this setting, we compare the estimates of the number of graphs of size \(n\) with \(m\) edges, \(|c_{\phi_{1}}(m=x)|\), based on the proposed recursive formula to those based on the following existing formula [1]:

\[|c_{\phi_{1}}(x)|=\binom{\binom{n}{2}}{x}. \tag{22}\]

Our comparison considers values of \(x\) ranging from \(\{1,\ldots,10\}\) for graphs of size \(n=1000\). For each value of \(x\in\{1,\ldots,10\}\), Table 1 provides the log values for \(r(x,x-1)\) and \(|c_{\phi_{1}}(x)|\) based on Equations (1) and (22). The estimates obtained from the proposed recursive formula and the known formula are identical--an expected finding given that a closed-form equation for \(r_{\phi_{1}}(x,x-1)\) exists. Regarding complexity, computing the recursive formula for \(|c_{\phi_{1}}(x)|\) requires computing \(\binom{n}{2}\) as well as \(x\) number of subtractions and divisions. Therefore, the complexity of the recursive formula is \(O(x)\) where subtractions and divisions are \(O(1)\). ### Degree Sequence

This section illustrates the use of Equation (1) to estimate the number of graphs with a fixed degree sequence. #### 4.2.1 Example

To illustrate the use of the recursive formula, we provide a numerical example wherein we estimate the number of graphs with \(n=1000\) and fixed degree sequence. In particular, we estimate the number of 2-regular graphs of size \(n=1000\); a \(\delta\)-regular graph is one in which each vertex has exactly degree \(\delta\). Therefore, the degree sequence for a \(\delta\)-regular graph is \(d=\{\delta,\ldots,\delta\}\).