# A General Computational Approach for Counting Labeled Graphs
## 3 Methods
\(S_{f}=i\); for\(m\gets 1\)to\(T_{k}\)do \(S_{c}[v]\gets S_{c}[v]+1\); \(S_{c}[w_{m}]\gets S_{c}[w_{m}]+1\); \(E\leftarrow\text{Union}(E,(v,w_{m}))\); return\(E\);
```  
**Algorithm 2**Degree Mixing  
``` Part 2: Compute the number of labeled graphs with degree mixing \(DMM\); for\(j\gets 0\)to\(n-1\)do \(D_{j}\leftarrow(\sum_{i=0}^{n}DMM_{i,j}+DMM_{j,j})/j\); \(S_{c}\leftarrow\text{Rep}(0,n)\); \(S_{f}\leftarrow\emptyset\); for\(j\gets 0\)to\(n\)do \(S_{f}\leftarrow\text{Union}(S_{f},\text{Rep}(\text{j},D_{j}))\); \(S_{f}\leftarrow\text{Union}(



**Theorem 4**: _Let \(E\) denote the collection of edges output from Algorithm 2 with a graphical degree mixing matrix \(DMM\) as input. Let \(G_{i}\) denote the graph formed with the first \(i\) edges from \(E\), i.e., contains edges \(\{e_{1},\ldots,e_{i}\}\). Let \(x_{i}=\phi_{4}(G_{i})\). Each consecutive pair in the collection of graphs \(G_{0},\ldots,G_{x}\) satisfies \(s1-s3\) for \(\phi_{4}\)._

Proof. : The edges in \(E\) are distinct. Therefore, by design, the conditions are satisfied. Based on the definition of \(x_{0}\) in Theorem 4, \(|c_{\phi_{4}}(x_{0})|=1\). Let \((v_{l},v_{j})\) be the single edge that differs between \(G_{i}\) and \(G_{i-1}\). Based on results from [PERSON] et al. [13]:

\[r_{\phi_{4}}(x_{i},x_{i-1})=\frac{[\gamma_{1}(G_{i-1})-\alpha_{2}(G_{i-1})] \times\beta^{0}_{(l,j)}(G_{i-1})}{DMM_{d_{j}(G_{i}),d_{j}(G_{i})}(G_{i})\times \beta^{1}_{(l,j)}(G_{i})}, \tag{12}\]

where

\[\alpha_{2}(G)=DMM_{d_{i}(G),d_{j}(G)}(G); \tag{13}\]

\[\gamma_{1}(G)= \begin{cases}D_{d_{i}(G)}(G)D_{d_{j}(G)}(G)\text{ if }d_{i}(G) \
eq d_{j}(G)\\ \begin{pmatrix}D_{d_{i}(G)}(G)\\ 2\end{pmatrix}\text{ else};\end{cases}  \tag{14}\]

and based on concepts from [PERSON] [16], if \(d_{i}(z)\
eq d_{j}(z)\),

\[\beta^{s}_{(l,j)}(G)\approx\frac{\Pi_{z}(\begin{smallmatrix}DMM^{\prime}_{d_{ j}(G),z}(G)-I_{\{d_{j}(G)=z\}}s\\ n_{1}^{z}+n_{2}^{z}-2I_{\{d_{j}(G)=z\}}s\\ \begin{smallmatrix}\sum_{i}DMM^{\prime}_{d_{j}(G),z}(G)-I_{\{d_{j}(G)=z\}}s \\ d_{i}(G)-s\end{smallmatrix} }\times\frac{n_{j}^{z}-1\{d_{j}(G)=z\}s}{ \begin{smallmatrix} \sum_{i}DMM^{\prime}_{d_{j}(G),z}(G)-I_{\{d_{j}(G)=z\}}s\\ d_{j}(G)-s\end{smallmatrix} }\end{cases} \tag{15}\]

else,

\[\beta^{s}_{(l,j)}(G)\approx\frac{\Pi_{z}(\begin{smallmatrix}DMM^{\prime}_{d_{ j}(G),z}(G)-I_{\{d_{j}(G)=z\}}s\\ n_{1}^{z}+n_{2}^{z}-2I_{\{d_{j}(G)=z\}}s\\ \begin{smallmatrix}\sum_{i}DMM^{\prime}_{d_{j}(G),z}(G)-I_{\{d_{j}(G)=z\}}s \\ d_{i}(G)+d_{j}(G)-2s\end{smallmatrix} }. \tag{16}\]

where \(DMM^{\prime}_{a,b}(G)=DMM_{a,b}(G)\) if \(a\
eq b\) and \(DMM^{\prime}_{a,b}(G)=2*DMM_{a,b}(G)\) if \(a=b\) and \(n_{1}^{z}\) and \(n_{2}^{z}\) denote the number of vertices that are neighbors of \(i\) and \(j\) and equal to \(z\). Using Equation (12) along with the specification of \(x_{0},\ldots,x_{k}=DMM\) as defined above and \(|c_{\phi_{4}}(x_{0})|=1\), it is possible to calculate \(|c_{\phi_{4}}(DMM)|\). ### Additional Graph Properties and Bipartite Graphs

The recursive formula and associated framework we propose can be used to calculate the number of labeled graphs for many additional graph properties. In particular, [PERSON] et al. [13] provide equations for \(r_{\phi}(x_{k},x_{k-1})\) for number of triangles (controlling for degree mixing) as well as jointly specifying classification mixing matrix and degree distribution. In addition, [PERSON] et al. [17] enables extending the calculation of \(r_{\phi}(x_{k},x_{k-1})\) to the setting of bipartite graphs. ## 4 Results

In this section, we present numerical examples--including validation results for estimating the number of labeled graphs--for two graph properties: number of edges (Section 4.1) and degree sequence (Section 4.2). To the author's knowledge, our paper is the first to provide formulas for estimating the number of labeled graphs consistent with values for several graph properties (e.g., degree mixing matrix) described in Section 3; hence, for these properties, we are not able to compare our approach to any existing approach.