# Enumeration and structure of inhomogeneous graphs

Élie de Panafieu †

Research Institute for Symbolic Computation (RISC),
J. Kepler University Linz, Austria

**Abstract.** We analyze a general model of weighted graphs, introduced by de Panafieu and Ravelomanana (2014) and similar to the *inhomogeneous graph model* of Söderberg (2002). We investigate the sum of the weights of those graphs and their structure. Those results allow us to give a new proof in a more general setting of a theorem of Wright (1972) on the enumeration of properly colored graphs. We also discuss applications related to social networks.

**Résumé.** Nous étudions un modèle de graphes pondérés, introduits par de Panafieu et Ravelomanana (2014) et proche des graphes inhomogènes de Söderberg (2002). Nous analysons la somme des poids de ces graphes et leur structure. Ces résultats nous permettent d'obtenir une nouvelle preuve d'un théorème de Wright (1972) sur l'énumération des graphes bien colorés, ainsi que sur un modèle lié aux réseaux sociaux.

**Keywords:** generating functions, analytic combinatorics, multivariate Laplace method, inhomogeneous graphs

The success of graphs relies on two contradictory properties. They are simple enough to appear naturally in many applications, but at the same time rich enough to enjoy non-trivial mathematical properties. Extensions such as hypergraphs and digraphs, and various notions of randomness on those objects have been proposed to address a wider range of applications. In this article, we focus on a model of inhomogeneous graphs introduced by de Panafieu and Ravelomanana [4] and similar to the *inhomogeneous graph model* of Söderberg [14]. Our main contributions are the computation of the total weight of inhomogeneous graphs with a given number of vertices and edges, and the analysis of their structure in the subcritical regime, without restriction on the weights matrix *R*. The emphasis is on the development of the theoretical basis of the model. Our tool is analytic combinatorics, and this work has been influenced by the articles of Flajolet, Knuth and Pittel [8] and Janson, Knuth, Łuczak and Pittel [12].

In Section 1, we present the model and two applications. Section 2 provides theorems for the enumeration of inhomogeneous graphs with a given number of vertices $n$ and edges $m$. The set of inhomogeneous graphs that contain no component with more than one cycle is analyzed in Section 3. We prove in Section 4 that when $m/n$ is small enough, almost all inhomogeneous graphs belong to this set, and derive more explicit results than in Section 2 on the global enumeration of inhomogeneous graphs. Section 5 extends the previous results to inhomogeneous graphs without loops nor multiple edges.

<footnote>†Email: depanafieuelie@gmail.com. This work was partially founded by the Austrian Science Fund (FWF) grant F5004, the Partenariats Hubert Curien (PHC) AMADEUS and the CNRS PEPS project HYDrATA</footnote>
# 1 Notations, models and applications

## 1.1 Notations

The row vector $(u_1, \dots, u_q)$ is denoted by $\tilde{u}$, and the column vector $(u_1, \dots, u_q)^\top$ by $\tilde{u}$. The diagonal matrix $\hat{u}$ has main diagonal $\tilde{u}$, and $\tilde{1}$ is the vector with all coefficients equal to 1. We adopt the notation $\tilde{u}^{\tilde{v}}$ for the product $\prod_i u_i^{v_i}$. The functions log and exp are applied coefficient-wise to the vectors, i.e. $\log(\tilde{u}) = (\log(u_1), \dots, \log(u_q))$. When $\sum_i n_i = n$, the multinomial notation $\binom{n}{\tilde{n}}$ denotes $n! / \prod_i n_i!$. The adjugate of a matrix $M$, equal to the transpose of the cofactor matrix, is $\mathrm{adj}(M)$. Open intervals, closed intervals and integer intervals are denoted by $]x, y[$, $[x, y]$ and $[a..b]$.

## 1.2 Models

The uniform graph model, also called multigraph process, has been studied using analytic combinatorics in [8] and [12]. This model produces a random vertex-labelled graph with $n$ vertices and $m$ edges by drawing $2m$ vertices $v_1w_1 \dots v_mw_m$ uniformly independently in $[1..n]$, and adding to the graph the edges $\overline{v_iw_i}$ for $i$ from 1 to $m$: edge$(G) = \{\overline{v_iw_i} | 1 \le i \le m\}$. The graph is simple if it contains neither loops nor multiple edges. If the output of the process is conditioned to be simple, the model reduces to the classic $G(n, m)$ graph model of Erdős and Rényi. The number of ordered sequences of vertices $v_1w_1 \dots v_mw_m$ that correspond to a graph $G$ is denoted by $\mathrm{seqv}(G)$

$$ \mathrm{seqv}(G) = |\{v_1w_1 \dots v_mw_m \mid \{\overline{v_iw_i} \mid 1 \le i \le m\} = \mathrm{edge}(G)\}|. $$

Observe that a graph $G$ with $m$ edges is simple if and only if its number of sequences of vertices $\mathrm{seqv}(G)$ is equal to $2^m m!$. For this reason, [12] introduced the compensation factor $\kappa(G) = \frac{\mathrm{seqv}(G)}{2^m m!}$. The total weight of graphs in a family is defined as the sum of their compensation factors. For example, the total weight of multigraphs with $n$ vertices and $m$ edges is $\frac{n^{2m}}{2^m m!}$.

The original inhomogeneous graph model was introduced in [14] as a generalization of the classic $G(n, p)$ random graph model, and extended by Bollobás, Janson and Riordan [3]. We consider in this paper a variant of this model, introduced in [4] and closer to the uniform graph model. Its parameters are an irreducible symmetric $q \times q$ matrix $R$ and a vector $\vec{r}$ of size $q$, both with non-negative coefficients. We call inhomogeneous graph, or $(R, \vec{r})$-graph, a labelled graph where

* each vertex $v$ has a type $t(v)$ which is an integer in $[1..q]$ and a weight $r_{t(v)}$,

* each edge $\overline{vw}$ receives a weight $R_{t(v),t(w)}$.

The weight $\omega(G)$ of an $(R, \vec{r})$-graph $G$ is the product of the compensation factor of the underlying graph (which is equal to 1 if the graph is simple), the weights of the vertices and the weights of the edges

$$ \omega(G) = \kappa(G) \prod_{u \in G} r_{t(u)} \prod_{\overline{vw} \in G} R_{t(v),t(w)}. $$

One can also think of the parameters $(r_i)$ and $(R_{i,j})$ as variables marking the vertices and the edges according to their types and the types of their ends. We define the total weight of $(R, \vec{r})$-graphs in a family as the sum of their weights. An $(n, m)$-$(R, \vec{r})$-graph is an $(R, \vec{r})$-graph with $n$ vertices and $m$
edges. Let $n(G)$ denote the number of vertices of a graph $G$ and $\mathcal{F}$ be a family of $(R, \vec{r})$-graphs, then the generating function $F(z)$ of $\mathcal{F}$ is defined by

$$F(z) = \sum_{G \in \mathcal{F}} \omega(G) \frac{z^{n(G)}}{n(G)!}.$$

We use this definition in Section 3. Observe that an $(R, \vec{r})$-graph that contains an edge of weight zero has weight zero, and thus does not contribute to the total weight of $(R, \vec{r})$-graphs.

**Lemma 1** Let $G_{R, \vec{r}}^*$ denote the set of $(R, \vec{r})$-graphs with non-zero weight. If the matrix $R$ is reducible, then there exist a non-trivial partition $T_1 \uplus \cdots \uplus T_k = [1..q]$ of the set of types, symmetric irreducible matrices $S_1, \dots, S_k$ and vectors $\vec{s}_1, \dots, \vec{s}_k$ such that $G_{R, \vec{r}}^*$ is in bijection with the Cartesian product $G_{S_1, \vec{s}_1}^* \times \cdots \times G_{S_k, \vec{s}_k}^*$. Specifically, for any graph $G$ in $G_{R, \vec{r}}^*$,

* for all $i \neq j$, there is no edge between a vertex of type in $T_i$ and one of type in $T_j$,

* for all $i$, the graph induced by $G$ on the vertices with types in $T_i$ is in $G_{S_i, \vec{s}_i}^*$.

**Proof:** Let $(\vec{e}_1, \dots, \vec{e}_q)$ denote the canonical basis of $\mathbb{R}^q$. Since $R$ is reducible, there is a partition $T_1, \dots, T_k$ of $[1..q]$ such that the matrix of $R$ on the basis $(\vec{e}_{T_1[1]}, \vec{e}_{T_1[2]}, \dots, \vec{e}_{T_2[1]}, \vec{e}_{T_2[2]}, \dots)$ has a block-diagonal shape $\text{diag}(S_1, \dots, S_k)$. For each $i$, we set $\vec{s}_i = (r_{T_i[1]}, r_{T_i[2]}, \dots)$. There can be no edge between types in $T_i$ and in $T_j$ for $i \neq j$ because its weight would be 0. Therefore, any component of $G_{R, \vec{r}}^*$ with a vertex of type in $T_i$ has all its types in $T_i$. By construction, such a component is in $G_{S_i, \vec{s}_i}^*$. $\square$

The matrix $R$ is therefore always assumed to be irreducible. In this paper, we analyze asymptotic properties of $(n, m)-(R, \vec{r})$-graphs when $n$ goes to infinity, $m$ is equal to $cn$ and $R, \vec{r}$ and $c$ are fixed.

## 1.3 Applications

Inhomogeneous graphs have been used in [4] to analyze the phase transition of satisfiability problems. We present new applications to illustrate the expressiveness of the model, and motivate the theoretical analysis conducted in the next sections. In the properly $q$-colored graphs, each vertex has a color in $[1..q]$ and no edge links two vertices with the same one. We give a new proof of [15, Theorem 3] on their enumeration, which is not to be confused with an enumeration of $q$-colorable graphs, a problem addressed in [1].

**Application 2** Let $R^{(\text{col})}$ denote the $q \times q$ matrix with all coefficients equal to 1 and 0s on the diagonal, then the number of properly $q$-colored $(n, m)$-graphs is equal to the total weight of $(n, m)-(R^{(\text{col})}, \vec{1})$-graphs. When $\frac{m}{n}$ is in a fixed closed interval of $\mathbb{R}_{>0}$, its asymptotics is

$$\frac{n^{2m}}{2^m m!} \left(1 + \frac{2}{q-1} \frac{m}{n}\right)^{-\frac{q-1}{2}} \left(1 - \frac{1}{q}\right)^m q^n + o(1).$$

For properly $q$-colored simple graphs, the previous asymptotics is multiplied by $\exp\left(\left(\frac{m}{n}\right)^2 \frac{q}{q-1}\right)$.

**Proof:** Let us identify the types and the colors. If an $(R^{(\text{col})}, \vec{1})$-graph is properly colored, the product of the weights of its edges is 1, otherwise it is 0, hence the first assertion of the theorem. The eigenvalues of
$R^{(\text{col})}$ are $q-1$ and $-1$, with multiplicities $1$ and $q-1$. The asymptotics is then a direct application of Theorem 14 and the remark following Theorem 16. $\square$

As a second example, we consider a world where each person has a number $k$ of topics of interest among a set of size $t \ge 2k$, and where two people can only become friend if they share at least one common topic of interest. We call *friendship graph* the graph where each vertex represents a person and each edge a friendship relation. The graph is naturally assumed to be simple. To analyze the friendship graphs, we introduce the following notations. Let $\sigma$ denote a numbering of the subsets of size $k$ of $[1..t]$, and $R^{(\text{fs})}$ the adjacency matrix of the complement of the *Kneser graph* (see for example [10]). This matrix of dimension $q = \binom{t}{k}$ is defined by

$$R_{i,j}^{(\text{fs})} = \begin{cases} 1 & \text{if } |\sigma(i) \cap \sigma(j)| \ge 1, \\ 0 & \text{otherwise.} \end{cases}$$

**Application 3** The number of friendship graphs with $n$ people and $m$ friendship relations is equal to the total weight of simple $(n, m)-(R^{(\text{fs})}, \bar{1})$-graphs. When $\frac{m}{n}$ is in a closed interval of $]0, \frac{1}{2}]$, almost all friendship graphs contain no component with more than one cycle. There is a value $\beta > \frac{1}{2}$ such that when $\frac{m}{n}$ is in a closed interval of $]0, \beta]$, the asymptotics of friendship graphs is

$$\frac{n^{2m}}{2^m m!} \left( \binom{t}{k} - \binom{t-k}{k} \right)^m \binom{t}{k}^{n-m} C + o(1)$$

where the value $C$, bounded with respect to $n$, is

$$C = \exp \left( - \frac{\binom{t}{k} \frac{m}{n} \left(1 + \frac{m}{n}\right)}{\left(\binom{t}{k} - \binom{t-k}{k}\right)} \prod_{j=1}^{k} \left(1 - (-1)^j \frac{2m}{n} \frac{\binom{t-k-j}{k-j}}{\binom{t}{k} - \binom{t-k}{k}}\right)^{-\frac{1}{2} \left(\binom{t}{j} - \binom{t}{j-1}\right)} \right).$$

**Proof:** Identifying each type $i$ with the set of topics of interest $\sigma(i)$, the definition of the matrix $R^{(\text{fs})}$ implies that the weight of a simple $(R^{(\text{fs})}, \bar{1})$-graph is 1 if it is a friendship graph, and 0 otherwise. The spectrum of the Kneser graph is known, and available in [5]. The spectrum of its complement follows: the dominant eigenvalue is $\binom{t}{k} - \binom{t-k}{k}$ and for all $j$ from 1 to $k$, $(-1)^j \binom{t-k-j}{k-j}$ is an eigenvalue with multiplicity $\binom{t}{j} - \binom{t}{j-1}$. The result is then a consequence of Theorem 14 and the remark that follows Theorem 16, with parameters $\text{Tr}(R^{(\text{fs})}) = \binom{t}{k}$ and $\text{Tr}((R^{(\text{fs})})^2) = \binom{t}{k} - \binom{t-k}{k}$. $\square$

Inhomogeneous graphs can as well handle generalizations of the model. For example, the weight of a friendship could be a real value, function of the number of common topics of interest.

## 2 Global enumeration

In this section, we reduce the problem of deriving the asymptotics of $(n, m)-(R, \vec{r})$-graphs to the location of the minimums of a function parameterized by $R, \vec{r}$ and $\frac{m}{n}$. We start with an explicit formula.

**Theorem 4** The total weight of $(n, m)-(R, \vec{r})$-graphs is

$$G_{R, \vec{r}}(n, m) = \frac{1}{2^m m!} \sum_{\{\vec{n} \in \mathbb{N}^q \mid \bar{1} \vec{n} = n\}} \binom{n}{\vec{n}} \vec{r}^{\vec{n}} (\bar{n} R \vec{n})^m. \quad (1)$$
**Proof:** Let us consider a fixed partition of the set of labels $[1..n]$ into $q$ sets $V_1, \dots, V_q$ of sizes $n_1, \dots, n_q$, and denote by $G(\vec{n}, m)$ the set of $(n, m)-(R, \vec{r})$-graphs where the type of the vertices in $V_i$ is $i$. Then the total weight of graphs in $G(\vec{n}, m)$ is expressed by summation over all sequences of vertices as

$$ \sum_{G \in G(\vec{n}, m)} \omega(G) = \frac{1}{2^m m!} \prod_{i=1}^{q} r_i^{n_i} \sum_{v_1, w_1, \dots, v_m, w_m \in [1..n]^{2m}} \prod_{i=1}^{m} R_{l(v_i), t(w_i)}. $$

Switching the sum and the product, the previous equation becomes

$$ \sum_{G \in G(\vec{n}, m)} \omega(G) = \frac{1}{2^m m!} \prod_{i=1}^{q} r_i^{n_i} \left( \sum_{1 \le i, j \le q} n_i n_j R \right)^m = \vec{r} \vec{n} \frac{(\vec{n} R \vec{n})^m}{2^m m!}. $$

Equation (1) is obtained by summation over all possible partitions $V_1 \uplus \dots \uplus V_q = [1..n]$. $\square$

To obtain the asymptotics of $G_{R,\vec{r}}(n, m)$, we will apply in the proof of Theorem 7 a multivariate Laplace method$^{(i)}$. This method requires to give to the previous expression a more suitable shape.

**Lemma 5** Let $S$ denote the set $\{\vec{x} \in \mathbb{R}^q \ge 0 | \vec{1}\vec{x} = 1\}$. The exact total weight of $(n, m)-(R, \vec{r})$-graphs is

$$ G_{R,\vec{r}}(n,m) = \frac{n^{2m}}{2^m m!} \frac{1}{(2\pi n)^{\frac{q-1}{2}}} \sum_{\{\vec{n} \in \mathbb{N}^q | \vec{1}\vec{n} = n\}} A_n\left(\frac{\vec{n}}{n}\right) e^{-n\Phi_{\vec{m}}\left(\frac{\vec{n}}{n}\right)}, \quad (2) $$

where, with the usual conventions $0 \log(0) = 0$ and $0^0 = 1$, the functions $A_n$ and $\Phi_c$ are defined on $S$ by

$$ A_n(\vec{x}) = \frac{n!}{n^ne^{-n}\sqrt{2\pi n}} \prod_{i=1}^{q} \frac{(nx_i)^{nx_i} e^{-nx_i}\sqrt{2\pi n x_i}}{\Gamma(nx_i+1)\sqrt{x_i}}, \\ \Phi_c(\vec{x}) = (\log(\bar{x}) - \log(\bar{r}))\vec{x} - c \log(\bar{x}R\bar{x}). $$

**Proof:** In Expression (1), we divide and multiply each factorial from the multinomial coefficient by its Stirling approximation, and rescale each $n_i$ by a factor $1/n$

$$ G_{R,\vec{r}}(n,m) = \frac{n^{2m}}{2^m m!} \frac{1}{(2\pi n)^{\frac{q-1}{2}}} \sum_{\substack{\vec{n} \in \mathbb{N}^q \\ \vec{1}\vec{n} = n}} \frac{n!}{n^ne^{-n}\sqrt{2\pi n}} \prod_{i=1}^{q} \frac{n_i^{n_i} e^{-n_i}\sqrt{2\pi n_i}}{n_i!\sqrt{n_i/n}} \left(\frac{\vec{r}\vec{n}/n}{(\vec{n}/n)^{\vec{n}/n}}\right)^n \left(\frac{\vec{n}}{n}R\frac{\vec{n}}{n}\right)^m. $$

The functions $A_n$ and $\Phi_c$ are then introduced to simply this expression. $\square$

Let $E$ denote a $q \times (q-1)$ matrix with left-kernel of dimension 1 containing the vector $\vec{1}$, e.g.

$$ E = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & \vdots \\ \vdots & \vdots & \ddots & 0 \\ 0 & \cdots & 0 & 1 \\ -1 & \cdots & \cdots & -1 \end{pmatrix}. $$

Two vectors $\vec{u}$ and $\vec{v}$ belong to $S$ only if there is a vector $\vec{\epsilon}$ of dimension $q-1$ for which $\vec{u} = \vec{v} + E\vec{\epsilon}$. The following lemma provides tools to locate the minimums of the function $\Phi_c$.

<footnote>(i) We thank Nathanaël Fijalkow and Antoine Crouzet for the time spent with us on this asymptotics.</footnote>
**Lemma 6** For all $c > 0$, the Taylor expansion of $\Phi_c$ near any point $\vec{x}$ in the interior of $S$ is

$$ \Phi_c(\vec{x} + E\vec{\epsilon}) = \Phi_c(\vec{x}) + \bar{\nabla}_{\Phi_c(\vec{x})} \vec{\epsilon} + \frac{1}{2} \bar{\epsilon} \mathcal{H}_{\Phi_c(\vec{x})} \vec{\epsilon} + \mathcal{O}(\|\vec{\epsilon}\|^3), $$

where the gradient vector and the Hessian matrix have dimension $q-1$ and are defined by

$$ \bar{\nabla}_{\Phi_c(\vec{x})} = \left( \log(\vec{x}) - \log(\bar{r}) - \frac{2c}{\bar{x}R\bar{x}} \bar{x}R \right) E, $$

$$ \mathcal{H}_{\Phi_c(\vec{x})} = E^{\top} \left( \hat{x}^{-1} + \frac{2c}{\bar{x}R\bar{x}} \left( \frac{2}{\bar{x}R\bar{x}} R \bar{x} \hat{x} R - R \right) \right) E. $$

If $\vec{\varphi}$ is a minimum of $\Phi_c$, then $\vec{\varphi}$ is in the interior of $S$, $\bar{\nabla}_{\Phi_c(\vec{\varphi})} = \bar{0}$ and $\mathcal{H}_{\Phi_c(\vec{\varphi})}$ is positive-semidefinite.

**Proof:** Let $\Psi_c$ denote the function $\vec{x} \to (\log(\vec{x}) - \log(\bar{r})) \vec{x} - c \log(\bar{x}R\bar{x})$ from $[0, 1]^q \setminus \{\bar{0}\}$ to $\mathbb{R}$. Its restriction to $S$ is equal to $\Phi_c$ and its Taylor expansion starts with

$$ \Psi_c(\vec{x} + \vec{\epsilon}) = \Psi_c(\vec{x}) + \bar{\nabla}_{\Psi_c(\vec{x})} \vec{\epsilon} + \frac{1}{2} \bar{\epsilon} \mathcal{H}_{\Psi_c(\vec{x})} \vec{\epsilon} + \mathcal{O}(\|\vec{\epsilon}\|^3) $$

where the gradient $\bar{\nabla}_{\Psi_c(\vec{x})}$ and the Hessian matrix $\mathcal{H}_{\Psi_c(\vec{x})}$ of $\Psi_c$ are computed using partial derivations. It follows that the Taylor expansion of $\Phi_c$ near any point $\vec{x}$ in the interior of $S$ is

$$ \Phi_c(\vec{x} + E\vec{\epsilon}) = \Phi_c(\vec{x}) + \bar{\nabla}_{\Psi_c(\vec{x})} E\vec{\epsilon} + \frac{1}{2}\bar{\epsilon} E^{\top} \mathcal{H}_{\Psi_c(\vec{x})} E\vec{\epsilon} + \mathcal{O}(\|\vec{\epsilon}\|^3). $$

Observing the limit of the gradient $\bar{\nabla}_{\Phi_c(\vec{x})}$ of $\Phi_c$ when one coordinate of $\vec{x}$ vanishes, we conclude that the local minimums of $\Phi_c$ cannot be reached on the boundary of $S$, and must therefore cancel $\bar{\nabla}_{\Phi_c(\vec{x})}$. $\square$

Gathering the previous results, we can finally apply the multivariate Laplace method.

**Theorem 7** Let $[a, b]$ be a fixed closed interval such that the function $(c, \vec{x}) \to \det(\mathcal{H}_{\Phi_c(\vec{x})})$ from $[a, b] \times S$ to $\mathbb{R}$ does not vanish, and let $\vec{\varphi}_{c,1}, \dots, \vec{\varphi}_{c,s}$ denote the local minimums of $\Phi_c$, then when $n$ is large while $c = \frac{m}{n}$ is in $[a, b]$, the asymptotics of the total weight of $(n, m)-(R, \vec{r})$-graphs is

$$ G_{R,\vec{r}}(n,m) \sim \frac{n^{2m}}{2^m m!} \sum_{\vec{\varphi} \in \{\vec{\varphi}_{c,1}, \dots, \vec{\varphi}_{c,s}\}} \left(\frac{\vec{r} \cdot \vec{\varphi}}{\vec{\varphi} \cdot \vec{\varphi}}\right)^n \frac{(\vec{\varphi} R \vec{\varphi})^m}{\sqrt{\det(\mathcal{H}_{\Phi_c(\vec{\varphi})}) \prod_{i=1}^q \varphi_i}}. $$

**Proof:** We inject in the integral representation of the sum (2) the following relations

$$ A_n(\vec{\varphi} + E\vec{\epsilon}) \sim \prod_{i=1}^{q} \varphi_i^{-1/2} + \mathcal{O}(\|\vec{\epsilon}\|^2), \quad e^{-n\Phi_c(\vec{\varphi} + E\vec{\epsilon})} = \left(\frac{\vec{r} \cdot \vec{\varphi}}{\vec{\varphi} \cdot \vec{\varphi}}\right)^n (\vec{\varphi} R \vec{\varphi})^m e^{-\frac{1}{2}n\bar{\epsilon} \mathcal{H}_{\Phi_c(\vec{\varphi})} \vec{\epsilon} + \mathcal{O}(n\|\vec{\epsilon}\|^3)}, $$

valid for any minimum $\vec{\varphi}$ of $\Phi_c$, and apply the multivariate Laplace method (see [13, Chapter 5]). $\square$

The previous theorem requires to locate the minimums of $\Phi_c$, and to avoid the values of $c$ for which those minimums cross or merge. Even when the dimension of the matrix $R$ is 2, those minimums can exhibit interesting behaviors. For example, for $R = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix})$, $\Phi_c$ has a unique minimum when $c \le 1/6$ and two local minimums when $c > 1/6$. Investigating the link between the inhomogeneous graph model and the *Stochastic Block Model* from [11] may provide an explanation for this change in $\Phi_c$. Theorems 12 and 14 provide two examples of families of parameters $R, \vec{r}$ and $\frac{m}{n}$ for which $\Phi_c$ has a unique minimum and a more explicit asymptotics for the total weight of $(n, m)-(R, \vec{r})$-graphs can be derive.
## 3 Trees and unicycles

An $(R, \vec{r})$-tree is a connected $(R, \vec{r})$-graph that contains no cycle. Such a graph is *rooted* if one vertex, called the *root*, is marked. An $(R, \vec{r})$-unicycle is a connected $(R, \vec{r})$-graph with exactly one cycle. A classic result of Erdős and Rényi [7] states that almost all $(n, m)$-graphs with $\frac{m}{n} < \frac{1}{2}$ contain only trees and unicycles. In this section, we derive a similar result for $(R, \vec{r})$-graphs. We also give a more explicit asymptotics for the total weight of $(n, m)-(R, \vec{r})$-graphs than in Theorem 7 when $\frac{m}{n}$ is smaller than a value $\beta$, defined in Theorem 12.

**Lemma 8** Let $T_i(z)$, $U(z)$ and $V(z)$ denote the generating functions of $(R, \vec{r})$-rooted trees with root of type $i$, $(R, \vec{r})$-trees and $(R, \vec{r})$-unicycles, and let $\vec{T}(z)$ denote the vector $(T_1(z), \dots, T_q(z))^{\top}$, then

$$ \vec{T}(z) = z\hat{r}\exp(R\vec{T}(z)), \quad U(z) = \vec{1}\vec{T}(z) - \frac{1}{2}\vec{T}(z)RT(z), \quad V(z) = -\frac{1}{2}\log\left(\det\left(I - \hat{T}(z)R\right)\right). $$

**Proof:** An $(R, \vec{r})$-rooted tree is a root with a set of sons which are $(R, \vec{r})$-rooted trees themselves. Let $i$ denote the type of the root, and $j$ the type of the root of one of those sons, then the root has weight $r_i$ and the weight of the edge linking the root to the son is the coefficient $R_{i,j}$. Using the *Symbolic Method* (see for example the book of Flajolet and Sedgewick [9]) the previous combinatorial description translates into the first relation on $\vec{T}(z)$. The expression for $U(z)$ is obtained using the *Dissymmetry Theorem* presented in [2]. The proof of the expression of $V(z)$ is a variation of [9, Proposition V.6]. □

**Lemma 9** The generating functions $\vec{T}(z)$ has the following singular expansions

$$ \vec{T}(z) = \vec{\tau} - \vec{\gamma}\sqrt{1 - z/\rho} + \mathcal{O}(1 - z/\rho) $$

where the value $\rho$ and the vectors $\vec{\tau}$ and $\vec{\gamma}$ have positive coefficients and are characterized by the system

$$ \vec{\tau} = \rho \hat{r} \exp(R \vec{\tau}), \quad (I - \hat{r} R) \vec{\gamma} = 0, \quad \frac{1}{2} \vec{\gamma} R \hat{\gamma} R \vec{\gamma} = \vec{1} \vec{\gamma}. \qquad (3) $$

**Proof:** The square-root singular expansion of $\vec{T}(z)$ is a consequence of [6, Proposition 3]. The constraints on its coefficients are obtained by injection of this expansion into the relation $\vec{T}(z) = z\hat{r}\exp(R\vec{T}(z))$ and identification of the coefficients corresponding to the same power of $\sqrt{1 - z/\rho}$. □

We can now build $(R, \vec{r})$-graphs that contain only trees and unicycles.

**Theorem 10** We set $\alpha = \frac{\vec{\tau}R\vec{\tau}}{\vec{1}\vec{1}}$. For $c = \frac{m}{n}$ in any closed interval of $]0, \alpha[$, let $\zeta_c$ and $\vec{\varphi}_c$ be characterized by

$$ \frac{1}{2} \frac{\vec{T}(\zeta_c) R \vec{T}(\zeta_c)}{\vec{1} \vec{T}(\zeta_c)} = c \quad \text{and} \quad \vec{\varphi}_c = \frac{\vec{T}(\zeta_c)}{\vec{1} \vec{T}(\zeta_c)}, \qquad (4) $$

then the total weight of $(n, m)-(R, \vec{r})$-graphs that contain only trees and unicycles is

$$ G_{R, \vec{r}}^{(U,V)}(n, m) \sim \frac{n^{2m}}{2^m m!} C_{c, \vec{\varphi}_c}^{-1/2} \left( \frac{\vec{r} \vec{\varphi}_c}{\vec{\varphi}_c^2} \right)^n (\vec{\varphi}_c R \vec{\varphi}_c)^m, $$

$$ \text{where} \quad C_{c, \vec{x}} = \frac{1}{c} \left( (1-c) \vec{1} \left( I - \frac{2c}{\vec{x}R\vec{x}} \hat{x}R \right)^{-1} \vec{x} - 1 \right) \det \left( I - \frac{2c}{\vec{x}R\vec{x}} \hat{x}R \right). \qquad (5) $$
**Proof:** A tree with $n$ vertices has $n-1$ edges, and a unicycle with $n$ vertices has $n$ edges. Therefore, an $(n, m)-(R, \vec{r})$-graph that contains only trees and unicycles is a set of $n-m$ trees and a set of unicycles

$$G_{R, \vec{r}}^{(U,V)}(n,m) = n![z^n] \frac{U(z)^{n-m}}{(n-m)!} e^{V(z)}.$$

We apply [9, Theorem VIII.8] to extract its asymptotics. The saddle-point equation is Equation (4). We then introduce the notation $\vec{\varphi}$, which satisfies the relation

$$\vec{T}(\zeta_c) = \frac{2c}{\vec{\varphi}_c R \vec{\varphi}_c} \vec{\varphi}_c,$$

and apply Stirling approximations to rearrange the expression. $\square$

In a longer version of this article, we plan to enumerate connected $(n, m)-(R, \vec{r})$-graphs when $m-n \ge 1$ is fixed, and to prove that such components appear with a non-zero probability when $m = \alpha n + O(n^{2/3})$. This would extend to $(R, \vec{r})$-graphs the result obtained for graphs in [12] with $\alpha = \frac{1}{2}$. Therefore, we conjecture that $\frac{m}{n} = \alpha$ is the threshold for the emergence of components with at least two cycles. Following the approach of [8], one could as well derive the limit law of the number of edges when the first cycle appear in a random $(n, m)-(R, \vec{r})$-graph.

The following lemma links the determinant of the Hessian matrix $\mathcal{H}_{\Phi_c(\vec{x})}$ to the value $C_{c,\vec{x}}$.

**Lemma 11** Let $\vec{\tau}$, $C_{c,\vec{x}}$ and $\mathcal{H}_{\Phi_c(\vec{x})}$ be defined by Equations (3), (5) and Lemma 6, and set $\alpha$ to $\frac{1}{2} \frac{\vec{\tau} R \vec{\tau}}{1 \vec{\tau}}$, then for all $c \in [0, \alpha[$ and $\vec{x} \in S$, the following identity holds

$$C_{c, \vec{x}} = \det(\mathcal{H}_{\Phi_c(\vec{x})}) \prod_{i=1}^{q} x_i.$$

**Proof:** We introduce the matrix $M = \frac{\vec{x} R \vec{x}}{2c} \hat{x}^{-1} - R$ and the vector $\vec{v} = \sqrt{2/(\vec{x} R \vec{x})} \vec{x}$. Since $E$ is a $q \times (q-1)$ matrix, it becomes a square matrix $F$ if we concatenate to its right the column vector $\vec{v}$. The determinant of $F^T M F$ can be expressed as $\det(F)^2 \det(M)$ or using a block-determinant formula. The equality between those two expressions is

$$\frac{2}{\vec{x} R \vec{x}} \det(M) = (\vec{v} M \vec{v} + 1) \det(E^T M E) - \det(E^T (M + M \vec{v} \vec{v} M) E). \quad (6)$$

The properties of the matrix $E$ imply

$$\det(E^T M E) = \det(M) \bar{1} M^{-1} \bar{1} \quad \text{and} \quad E^T (M + M \vec{v} \vec{v} M) E = \frac{\vec{x} R \vec{x}}{2c} \mathcal{H}_{\Phi_c(\vec{x})}.$$

The result is obtained by injection of those relations in Equation (6) and rearrangement of the terms. $\square$
## 4 Global enumeration when $\Phi_c$ has a unique minimum

In this section, we present two cases where the result of Theorem 7 can be made more specific.

**Theorem 12** We set $\beta = \sup\{c | \forall \vec{x} \in S, \det(\mathcal{H}_{\Phi_c(\vec{x})}) > 0\}$, then $\beta$ is greater than $\alpha$ (defined in Theorem 10). The equation $\bar{\nabla}_{\Phi_c(\vec{\varphi})} = \bar{0}$ defines implicitly on $[0, \beta]$ a unique solution $\vec{\varphi}_c$, given by Equation (4) when $c \in [0, \alpha]$. Finally, when $\frac{m}{n}$ is in a closed interval of $[0, \beta]$, the asymptotics of $(n, m)-(R, \vec{r})$-graphs is

$$G_{R,\vec{r}}(n,m) \sim \frac{n^{2m}}{2^m m!} \left( \frac{\vec{r} \cdot \vec{\varphi}_c}{\vec{\varphi}_c \cdot \vec{\varphi}_c} \right)^n \frac{(\vec{\varphi}_c R \vec{\varphi}_c)^m}{\sqrt{\det(\mathcal{H}_{\Phi_c(\vec{\varphi}_c)}) \prod_{i=1}^q \varphi_i}}.$$

**Proof:** When $c = 0$, for all $\vec{x} \in S$ the matrix $\mathcal{H}_{\Phi_0(\vec{x})}$ is positive-definite. By continuity of its eigenvalues with respect to $c$ and $\vec{x}$, $\mathcal{H}_{\Phi_c(\vec{x})}$ stays positive-definite for all $c \in [0, \beta]$ and $\vec{x} \in S$, so the function $\Phi_c$ is convex. According to Lemma 6, $\Phi_c$ has no minimum on the boundary of $S$, so it has a unique minimum, which cancels its gradient $\bar{\nabla}_{\Phi_c(\vec{x})}$. The asymptotics is then a consequence of Theorem 7. For $c \in [0, \alpha]$, let us define $\vec{\varphi}_c$ as in Equation (4). A direct computation shows that $\log(\vec{\varphi}_c) - \log(\bar{r}) - 2c\bar{\varphi}R/(\bar{\varphi}R\bar{\varphi})$ is collinear to $\bar{1}$, so $\vec{\varphi}_c$ cancels $\bar{\nabla}_{\Phi_c(\vec{x})}$. We extend continuously $\vec{\varphi}_c$ for $c = 0$ and $c = \alpha$ with

$$\vec{\varphi}_0 = \lim_{z \to 0} \frac{\vec{T}(z)}{\bar{1} \vec{T}(z)} = \frac{\vec{r}}{\bar{1} \vec{r}}, \quad \vec{\varphi}_\alpha = \lim_{z \to \rho} \frac{\vec{T}(z)}{\bar{1} \vec{T}(z)} = \frac{\vec{\tau}}{\bar{1} \vec{\tau}}.$$

The last point we need to prove is that $\beta > \alpha$. According to Lemma 11, $\det(\mathcal{H}_{\Phi_c(\vec{x})})$ vanishes only if $C_{c,\vec{x}}$ does, and Theorem 10 implies in particular $C_{c,\vec{\varphi}_c} > 0$ when $c \in [0, \alpha]$. Observe that $\mathcal{H}_{\Phi_c(\vec{x})}$ is independent of $\vec{r}$ and that for each $\vec{x} \in S$, there is a vector $\vec{r} \in \mathbb{R}_{>0}^q$ such that $\vec{\varphi}_c = \vec{x}$. This proves $\beta \ge \alpha$. For $c = \alpha$, $\vec{\varphi}_\alpha$ is equal to $\vec{\tau}/(\bar{1}\vec{\tau})$. The definitions (3) of $\vec{\tau}$ and (5) of $C_{c,\vec{\varphi}_c}$ then imply

$$\det \left( I - \frac{2\alpha}{\bar{\varphi}_\alpha R \bar{\varphi}_\alpha} \hat{\varphi}_\alpha R \right) = 0 \quad \text{and} \quad C_{\alpha, \bar{\varphi}_\alpha} = \frac{1 - \alpha}{\alpha} \bar{1} \operatorname{adj}(I - \hat{\tau} R) \frac{\vec{\tau}}{\bar{1} \vec{\tau}}.$$

The value of the generating function of unrooted $(R, \vec{r})$-trees $\bar{1}\vec{T}(z) - \vec{T}(z)RT(z)/2$ is positive at its dominant singularity $\rho$, and $\vec{\tau} = \vec{T}(\rho)$, so $\alpha = \bar{\tau}R\vec{\tau}/(2\bar{1}\vec{\tau})$ is smaller than 1. By definition of $\vec{\tau}$, the irreducible matrix $\hat{\tau}R$ has dominant eigenvalue 1 of dimension 1 with eigenvector $\vec{\gamma}$, defined in Equation (3). Therefore, $\operatorname{adj}(I - \hat{\tau}R)$ is proportional to $\vec{\gamma}\vec{\gamma}$, which has positive coefficients. This implies $C_{\alpha, \bar{\varphi}_\alpha} > 0$, so $\det(\mathcal{H}_{\Phi_\alpha(\vec{x})})$ is positive for all $\vec{x} \in S$ and $\Phi_\alpha$ is still strictly convex. Therefore, $\beta$ is greater than $\alpha$. $\square$

The following corollary is obtained by comparison of the asymptotics of $G_{R,\vec{r}}^{(U,V)}(n, m)$ from Theorem 10 and $G_{R,\vec{r}}(n, m)$ from Theorem 12, using the relation $C_{c,\vec{x}} = \det(\mathcal{H}_{\Phi_c(\vec{x})}) \prod_{i=1}^q x_i$ from Lemma 11.

**Corollary 13** When $c = \frac{m}{n}$ is in a closed interval of $[0, \alpha]$, then almost all $(n, m)-(R, \vec{r})$-graphs contain only trees and unicycles.

When $R$ is the adjacency matrix of a regular graph, then $\bar{1}$ is an eigenvector and $\vec{\varphi}_c$ becomes explicit.

**Theorem 14** Let $\lambda_1 \ge \dots \ge \lambda_q$ denote the eigenvalues of $R$, and assume that $\bar{1}$ is an eigenvector of $R$, then when $\frac{m}{n}$ is in a closed interval of $[0, \beta]$, the asymptotics of $(n, m)-(R, \bar{1})$-graphs is

$$G_{R,\bar{1}}(n,m) \sim \frac{n^{2m}}{2^m m!} \lambda_1^m q^{n-m} \prod_{i=2}^q \left(1 - 2 \frac{\lambda_i}{\lambda_1} \frac{m}{n}\right)^{-1/2}.$$
If $\lambda_2$ is positive, $\beta < \frac{\lambda_1}{2\lambda_2}$, otherwise the previous asymptotics holds for $\frac{m}{n}$ in any closed interval of $\mathbb{R}_{>0}$.

**Proof:** $R$ has non-negative coefficients and is irreducible. The Perron-Fröbenius theorem implies that its dominant eigenvalue is positive and corresponds to the unique eigenvector with positive coefficients, thus $R\bar{\bar{1}} = \lambda_1\bar{\bar{1}}$. The first assertion of the theorem is then a consequence of Theorem 12 with $\bar{\varphi}_c = \bar{\bar{1}}/q$,

$$ \bar{\nabla}_{\Phi_c(\bar{\bar{1}}/q)} = \bar{0} \quad \text{and} \quad \det(\mathcal{H}_{\Phi_c(\bar{\bar{1}}/q)}) = \frac{q^q}{1-2c} \det\left(I - \frac{2c}{\lambda_1}R\right) = q^q \prod_{i=2}^q \left(1 - 2c \frac{\lambda_i}{\lambda_1}\right). $$

Observe that $\det(\mathcal{H}_{\Phi_c(\bar{\bar{1}}/q)})$ vanishes at $c = \frac{\lambda_1}{2\lambda_2}$. Let us now consider the case $\lambda_2 \le 0$. The function $\log(\bar{x})\bar{x}$ reaches its unique minimum on $S$ at $\bar{1}/q$. To prove that the function $\Phi_c(\bar{x}) = \log(\bar{x})\bar{x} - c\log(\bar{x}R\bar{x})$ does the same, it is then sufficient to prove that $\bar{x}R\bar{x}$ reaches at $\bar{1}/q$ its global maximum. Since $\bar{x}$ is in $S$, there is a vector $\bar{y} \in \mathbb{R}^{q-1}$ that satisfies $\bar{x} = \bar{1}/q + E\bar{y}$. Since $\bar{1}E$ is equal to $\bar{0}$, we obtain

$$ \bar{x}R\bar{x} = \frac{\lambda_1}{q} + \bar{y}E^TRE\bar{y}. $$

The symmetry of $R$ implies the existence of an orthogonal matrix $Q$ with first row $\bar{1}/\sqrt{q}$ such that $R = Q^T \text{diag}(\lambda_1, \dots, \lambda_q)Q$. The first row of $QE$ is $\bar{0}$. Let $P$ denote the $(q-1) \times (q-1)$ matrix in the lower block of $QE$. Then $P$ is invertible, and

$$ E^T Q^T \text{diag}(\lambda_1, \dots, \lambda_q)QE = P^T \text{diag}(\lambda_2, \dots, \lambda_q)P. $$

We set $\bar{z} = P\bar{y}$ and obtain $\bar{x}R\bar{x} = \frac{\bar{1}}{q} + \sum_{i=2}^q \lambda_i z_i^2$. Therefore, $\bar{x}R\bar{x}$ reaches its global maximum $\lambda_1/q$ when $\bar{z} = \bar{0}$, which implies $\bar{y} = \bar{0}$ and $\bar{x} = \bar{1}/q$. $\square$

A future direction of research is the expansion of the family of parameters $R$, $\bar{r}$ and $c$ for which we can link the asymptotics of $(n, m)-(R, \bar{r})$-graphs to the spectrum of $R$. Information on the location of the minimums of $\Phi_c$ for $c$ greater than $\beta$ would also be instructive.

# 5 Simple $(R, \bar{r})$-Graphs

The previous sections focused on $(R, \bar{r})$-graphs where loops and multiple edges were allowed. We now extend those results to simple $(R, \bar{r})$-graphs, starting with a theorem similar to Theorem 4.

**Theorem 15** The total weight of simple $(n, m)-(R, \bar{r})$-graphs is

$$ SG_{R,\bar{r}}(n,m) = [w^m] \sum_{\bar{1}\bar{n}=n} \binom{n}{\bar{n}} \bar{r}^{\bar{n}} \prod_{1 \le i < j \le q} (1 + R_{i,j}w)^{n_i n_j} \prod_{i=1}^q (1 + R_{i,i}w)^{n_i(n_i-1)/2}. \quad (7) $$

**Proof:** We consider a partition $V_1 \cup \dots \cup V_q = [1..n]$ of the set of vertices and define $n_i = |V_i|$ for all $i$. Let $SG(\bar{n}, m)$ denote the set of simple $(n, m)-(R, \bar{r})$-graphs where each vertex of $V_i$ has type $i$. When $i \ne j$, there are $n_i n_j$ available edges between vertices of $V_i$ and $V_j$, and for all $i$, there are $n_i(n_i - 1)/2$ possible edges between vertices of $V_i$. Therefore, the total weight of graphs in $SG(\bar{n}, m)$ is

$$ \sum_{G \in SG(\bar{n}, m)} \omega(G) = [w^m] \bar{r}^{\bar{n}} \prod_{1 \le i < j \le q} (1 + R_{i,j}w)^{n_i n_j} \prod_{i=1}^q (1 + R_{i,i}w)^{n_i(n_i-1)/2}. $$
The result of the Lemma is obtained by summation over all partitions $V_1 \uplus \cdots \uplus V_q = [1..n]$. $\square$

**Theorem 16** With the notations of Theorem 7, for all $c = \frac{m}{n}$ in $[a, b]$, the asymptotics of simple $(n, m)$-$\langle R, \vec{r} \rangle$-graphs is

$$SG_{R,\vec{r}}(n,m) \sim \frac{n^{2m}}{2^m m!} \sum_{\vec{\varphi} \in \{\vec{\varphi}_{c,1}, \dots, \vec{\varphi}_{c,s}\}} \left(\frac{\vec{r} \cdot \vec{\varphi}}{\vec{\varphi} \cdot \vec{\varphi}}\right)^n (\vec{\varphi} R \vec{\varphi})^m \frac{e^{-\frac{c}{\vec{\varphi} R \vec{\varphi}}} \mathrm{Tr}(\hat{\varphi} R) - \left(\frac{c}{\vec{\varphi} R \vec{\varphi}}\right)^2 \mathrm{Tr}((\hat{\varphi} R)^2)}{\sqrt{\det(\mathcal{H}_{\Phi_c(\vec{\varphi})}) \prod_{i=1}^q \varphi_i}}.$$

**Proof:** Starting with the exact expression (7), we replace $w$ with $nw$

$$SG_{R,\vec{r}}(n,m) = n^m \sum_{\vec{1}\vec{n}=n} \binom{n}{\vec{n}} \vec{r}^{\vec{n}} [w^m] e^{F_n(\vec{n}/n,w)}, \qquad (8)$$

$$\text{where } F_n(\vec{x}, w) = \log \left( \prod_{1 \le i < j \le q} (1 + R_{i,j} \frac{w}{n})^{nx_i n x_j} \prod_{i=1}^{q} (1 + R_{i,i} \frac{w}{n})^{nx_i (nx_i - 1)/2} \right).$$

An expansion of the logarithm reduces this expression to

$$F_n(\vec{x}, w) = n \bar{x} R \bar{x} \frac{w}{2} - \frac{1}{2} \mathrm{Tr}(\hat{x} R) w - \frac{1}{4} \mathrm{Tr}((\hat{x} R)^2) w^2 + \mathcal{O}(n^{-1}).$$

With $c = \frac{m}{n}$ bounded, we apply [9, Theorem VIII.8] with saddle-point $\zeta = 2c/(\bar{x}R\bar{x})$:

$$[w^m] e^{F_n(\vec{x}, w)} = \frac{n^m}{2^m m!} (\bar{x} R \bar{x})^m \exp \left( -\frac{1}{2} \mathrm{Tr}(\hat{x} R) \frac{2c}{\bar{x} R \bar{x}} - \frac{1}{4} \mathrm{Tr}((\hat{x} R)^2) \left( \frac{2c}{\bar{x} R \bar{x}} \right)^2 \right) (1 + \mathcal{O}(n^{-1}))$$

holds uniformly for $\vec{x} \in S$. Adopting the notation $\Phi_c$ of Lemma 5, Equation (8) then becomes

$$SG_{R,\vec{r}}(n,m) = \frac{n^{2m}}{2^m m!} \frac{1}{(2\pi n)^{\frac{q-1}{2}}} \sum_{\{\vec{n} \in \mathbb{N}^q \mid \vec{1}\vec{n} = n\}} SA_n\left(\frac{\vec{n}}{n}\right) e^{-n\Phi_{\frac{\vec{n}}{n}}(\frac{\vec{n}}{n})},$$

$$\text{where } SA_n(\vec{x}) = \prod_{i=1}^{q} \frac{(nx_i)^{nx_i} e^{-nx_i} \sqrt{2\pi nx_i}}{\Gamma(nx_i + 1)} \frac{1}{\sqrt{x_i}} e^{-\mathrm{Tr}(\hat{x}R) \frac{c}{\bar{x}R\bar{x}}} - \mathrm{Tr}((\hat{x}R)^2) \left(\frac{c}{\bar{x}R\bar{x}}\right)^2 (1 + \mathcal{O}(n^{-1})).$$

The end of the proof is the same as in Theorem 7. $\square$

Theorems 12 and 14 extend to simple $(R, \vec{r})$-graphs in the same way.

**Corollary 17** When $\frac{m}{n}$ is in a closed interval of $]0, \alpha[$, almost all simple $(n, m)$-$\langle R, \vec{r} \rangle$-graphs contain only trees and unicycles.

**Proof:** We verify that the asymptotics of simple $(n, m)$-$\langle R, \vec{r} \rangle$-graphs containing only trees and unicycles is equal to the asymptotics of all simple $(n, m)$-$\langle R, \vec{r} \rangle$-graphs, derived in Theorem 16. The generating function $U(z)$ of $\langle R, \vec{r} \rangle$-trees is the same for graphs and simple graphs. The generating function $SV(z)$ of simple $(R, \vec{r})$-unicycles becomes

$$SV(z) = V(z) - \frac{1}{2} \mathrm{Tr}(\hat{T}(z)R) - \frac{1}{4} \mathrm{Tr}((\hat{T}(z)R)^2)$$

to avoid loops and double edges in the cycle. The end of the proof is the same as in Theorem 10. $\square$

<figure><img src="image_1.png" /></figure>
References

[1] D. ACHLIOPTAS AND A. COJA-OGHLAN, *Algorithmic barriers from phase transitions*, in Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS '08, Washington, DC, USA, 2008, IEEE Computer Society, pp. 793–802.

[2] F. BERGERON, G. LABELLE, AND P. LEROUX, *Combinatorial Species and Tree-like Structures*, Cambridge University Press, 1997.

[3] B. BOLLOBÁS, S. JANSON, AND O. RIORDAN, *The phase transition in inhomogeneous random graphs*, Random Structures and Algorithms, 31 (2007), pp. 3–122.

[4] E. DE PANAFIEU AND V. RAVELOMANANA, *Analytic description of the phase transition of inhomogeneous multigraphs*, European Journal of Combinatorics, (2015).

[5] P. DELSARTE AND V. I. LEVENSHTEIN, *Association schemes and coding theory*, IEEE Transactions on Information Theory, 44 (1998), pp. 2477–2504.

[6] M. DRMOTA, *Systems of functional equations*, Random Structures & Algorithms, 10 (1999), pp. 103–124.

[7] P. ERDŐS AND A. RÉNYI, *On the evolution of random graphs*, Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5 (1960), p. 17.

[8] P. FLAJOLET, D. E. KNUTH, AND B. PITTEL, *The first cycles in an evolving graph*, Discrete Mathematics, 75 (1989), pp. 167–215.

[9] P. FLAJOLET AND R. SEDGEWICK, *Analytic Combinatorics*, Cambridge University Press, 2009.

[10] C. GODSIL AND G. ROYLE, *Algebraic Graph Theory*, Graduate Texts in Mathematics, New-York : Springer-Verlag, 2001.

[11] P. W. HOLLAND, K. B. LASKEY, AND S. LEINHARDT, *Stochastic blockmodels: First steps*, Social Networks, 5 (1983), pp. 109–137.

[12] S. JANSON, D. E. KNUTH, T. ŁUCZAK, AND B. PITTEL, *The birth of the giant component*, Random Structures and Algorithms, 4 (1993), pp. 233–358.

[13] R. PEMANTLE AND M. C. WILSON, *Analytic Combinatorics in Several Variables*, Cambridge University Press, New York, NY, USA, 2013.

[14] B. SÖDERBERG, *General formalism for inhomogeneous random graphs*, Phys. Rev. E, 66 (2002), pp. 066–121.

[15] E. M. WRIGHT, *Counting coloured graphs III*, Canadian Journal of Mathematics, 14 (1972), pp. 82–89.