Dependencies

Given an ordered pair \((G,w) \in \mathcal{G}_k\), we define \(|G|\) to be the number of distinct vertices in the graph \(G\).

A Dyck path of length \(k\) is a sequence \((d_1,...,d_k) \in \{ \pm 1\} ^k\) such that their partial sum \(\sum _{i=1}^j d_i \geq 0\) and total sum \(\sum _{i = 1}^{k}d_i = 0\). More intuitively, consider a diagonal lattice path from \((0,0)\) to \((k, 0)\) consisting of \(\frac{k}{2}\) ups and \(\frac{k}{2}\) downs such that the path never goes below thw \(x\)-axis.

Define a map \(\psi \) whose input is a Dyck path of order \(k\): \(\mathbf{d} \in \{ \pm 1\} ^k\). Then the output is viewing this Dyck path as a contour reversal of a tree where an up (\(d_i = 1\)) corresponds to visiting a child node and a down (\(d_i = -1\)) corresponds to returning to parent node.

Let \(\mathbf{i} \in [n]^{k}\) be a \(k\)-index, \(\mathbf{i} = (i_1, i_2, \ldots , i_{k})\). Let \(Y\) be a symmetric matrix and let \(\{ Y_{ij}\} _{1\le i\le j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. We define \(\Pi (G_{\mathbf{i}}), w_{\mathbf{i}}\) as follows:

Let \(\mathcal{G}_k\) denote the set of all ordered pairs \((G,w)\) where \(G = (V,E)\) is a connected graph with at most \(k\) vertices, and \(w\) is a closed path covering \(G\) satisfying \(|w| = k\).

Let \((G_\mathbf {i},w_\mathbf {i})\) be an ordered pair generated by some \(k\)-index \(\mathbf{i}\) and \((G,w) \in \mathcal{G}_k\). We say \((G_\mathbf {i},w_\mathbf {i}) = (G,w)\) if and only if there exists a bijection \(\varphi \) from the set of entries \(\mathbf{i}\) onto the set of entries \(\mathbf{j}\) such that

where \(\mathbf{j}\) is a \(k\)-index generated by \((G,w)\).

Let \(\mathcal{G}_{k,w \geq 2}\) be a subset of \(\mathcal{G}_k\) in which the walk \(w\) traverses each edge at least twice.

Given \((G,w) \in \mathcal{G}_k\), we denote \(\mathbf{j}\) as the \(k\)-index generated by \((G,w)\) in the following way. The path \(w\) can be uniquely expressed under the condition of Lemma 3.1.18:

We define \(\mathbf{j} = (j_1,j_2,...,j_{k-1},j_k)\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index. Given graph \(G_{\mathbf{i}}\), define the connecting-edges \(E_{\mathbf{i}}^{c}\) as:

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). For any edge \(e=\{ i,j\} \) from \(E_{\mathbf{i}}\), we define the edge count \(w_{\mathbf{i}}(e)\) as the number of times each edge \(e\) is traversed, and if \((i, j) \notin E_{\mathbf{i}}\), then \(w_{\mathbf{i}}(\{ i, j\} ) = 0\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). A graph \(G_{\mathbf{i}}\) is defined as follows: the vertices \(V_{\mathbf{i}}\) are the distinct elements of

and the edges \(E_{\mathbf{i}}\) are the distinct pairs among

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). the path \(w_{\mathbf{i}}\) is the sequence

of edges from \(E_{\mathbf{i}}\)

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index. Given graph \(G_{\mathbf{i}}\), define the self-edges \(E_{\mathbf{i}}^{s}\) as:

the set of edges where both vertices are the same.

Define a map \(\phi \) whose input is \((G, w) \in \mathcal{G}^{k/2 + 1}_k\). Then for its output, define a sequence \(\mathbf{d}=\mathbf{d}(G,w)\in \{ +1,-1\} ^k\) recursively as follows. Let \(d_1=+1\). For \(1{\lt}j\le k\), if \(w_j\notin \{ w_1,\ldots ,w_{j-1}\} \), set \(d_j=+1\); otherwise, set \(d_j=-1\); then \(\mathbf{d}(G,w) = (d_1,\ldots ,d_k)\). \(\phi ((G,w)) = \mathbf{d}(G,w)\)

Given any graph \(G=(V,E)\) and a path \(w\), we let \(|w|\) denote the length of \(w\).

Given a path \(w_\mathbf {i}\) generated by some \(k\)-index \(\mathbf{i}\), we let \(|w_\mathbf {i}|\) denote the length of \(w_\mathbf {i}\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix. The matrix multi index \(Y_{\mathbf{i}}\) is defined as:

Given an ordered pair \((G,w) \in \mathcal{G}_k\), let \(\mathbf{j}\) be the \(k\)-index generated by \((G,w)\). We define

The semicircle distribution with mean \(\mu \) and variance \(v\) is the Dirac delta at μ if v = 0; otherwise, it’s the Lebesgue measure weighted by the semicircle PDF.

Let \(f : \mathbb {R} \times \mathbb {R}_{\geq 0} \times \mathbb {R} \to \mathbb {R}\) denote the real-valued semicircle density defined in Definition 4.1.1. Define the function \(h: \mathbb {R} \to \mathbb {R} \cup \{ \infty \} \) as follows:

Then we define the function \( g : \mathbb {R} \times \mathbb {R}_{\geq 0} \times \mathbb {R} \to [0,\infty ] \subseteq \overline{\mathbb {R}}_{\ge 0}\) by:

The function \(f : \mathbb {R} \times \mathbb {R}_{\geq 0} \times \mathbb {R} \rightarrow \mathbb {R}\) defined by

is called the probability density function (p.d.f.) of the semicircle distribution.

Let \(\mathcal{G}^{k/2+1}_k\) to be the set of pairs \((G,w)\in \mathcal{G}_k\) where \(G\) has \(k/2+1\) vertices, contains no self-edges, and the walk \(w\) crosses every edge exactly \(2\) times.

For any \(k\)-index \(\mathbf{i}\), the connected graph \(G_\mathbf {i} = (V_\mathbf {i},E_\mathbf {i})\) has at most \(k\) vertices. Furthermore

#{binary trees with \(\frac{k}{2}\) vertices} is given by Catalan number \(C_{k / 2}\)

\(\mathbb {E}[(X - \mu )^{2n + 1}] = 0 \)

\(\mathbb {E}[(X - \mu )^{2n}] = v_n C_n \)

\(\mathbb {E}[(X - \mu )^{2n + 1}] = 0 \)

\(\mathbb {E}[(X - \mu )^{2n}] = v_n C_n \)

\(\psi (\mathbf{d}_k) \subseteq \mathcal{G}^{k/2 + 1}_k\)

Given an ordered pair \((G,w) \in \mathcal{G}_{k,w \geq 2}\), we must have \(\# E \leq k/2\).

Given two \(k\)-indexes \(\mathbf{i} = (i_1,...,i_k)\) and \(\mathbf{j} = (j_1,...,j_k)\), suppose there exists a bijection \(\varphi \) from the set of entries of \(\mathbf{i}\) onto the set of entries of \(\mathbf{j}\) such that

Then \(\mathbb {E}(Y_\mathbf {i}) = \mathbb {E}(Y_{\mathbf{j}})\).

\(\phi ((G,w)) = \mathbf{d}(G,w) \subseteq \mathcal{D}_k\), where \(\mathcal{D}_k\) denotes the set of Dyck path of order \(k\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix. Then, we have the following:

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is integrable.

Given a mean \(\mu \in \mathbb {R}\) and a nonzero variance \(v \in \mathbb {R}_{{\gt} 0}\), the integral of the p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) equals \(1\).

Given \((G,w) \in \mathcal{G}_k\), we have

If \( v {\gt} 0 \), then the total integral of \( g \) with respect to Lebesgue measure is 1:

Given a mean \(\mu \in \mathbb {R}\) and a nonzero variance \(v \in \mathbb {R}_{{\gt} 0}\), the lower integral of the p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) equals \(1\).

Let \(Y\) be an \(n\times n\) matrix and \(k \in \mathbb {N}\). Then, for each \((i, j)\)-th entry of \(Y^{k}\), we have:

Let \(Y\) be an \(n\times n\) matrix and \(k \in \mathbb {N}\). Then, the trace of \(Y^{k}\) is given by:

The function \( x \mapsto g(\mu ,v,x) \) is measurable for all \( \mu \in \mathbb {R} \), \( v \in \mathbb {R}_{\ge 0} \).

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is measurable.

All the moments of a real semicircle distribution are finite. That is, the identity is in \(L_p\) for all finite \(p\)

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix. Then, we have the following:

Given an ordered pair \((G,w) \in \mathcal{G}_k\), suppose there exists an edge \(e \in E\) in which it is traversed only once in the walk \(w\). Then

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix and let \(\{ Y_{ij}\} _{1\le i\le j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. Then, we have the following:

Let \((\mathcal{X}, d)\) be a Polish space. Let \(\mu : \Omega \to \mathcal{P}(\mathcal{X})\) be measureable wiht respect to the cylinder \(\sigma \)-algebra on \(\mathcal{P}(\mathcal{X})\). Let \(f : \mathcal{X} \to \mathcal{Y}\) be measurable. define \(\varphi : \Omega \to \mathcal{Y}\) by

Then \(\varphi \) is a measurable map from \(\Omega \to \mathcal{Y}\).

For all \(\mu \in \mathbb {R} \), \( v \in \mathbb {R}_{\geq 0} \), the extended p. d. f. \( g : \mathbb {R} \to [0,\infty ]\) satisfies:

For all \(\mu , x \in \mathbb {R}\), and \(v \in \mathbb {R}_{\ge 0}\), we have:

For all \( \mu , x \in \mathbb {R} \), and \( v \in \mathbb {R}_{\ge 0} \), the extended p.d.f. is finite:

If \(v {\gt} 0\), then for all \(\mu , x \in \mathbb {R}\), the extended p.d.f. is nonnegative:

Let \( \mu \in \mathbb {R} \), \( v \in \mathbb {R}_{\ge 0} \), and \( x \in \mathbb {R} \). Then the real value recovered from the extended semicircle PDF satisfies:

If the variance \(v\) is zero, then the extended p.d.f. is identically zero:

For any p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(u \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), and \(x,y \in \mathbb {R}\).

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is given by

For any p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(u \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), \(x \in \mathbb {R}\), and nonzero \(c \in \mathbb {R}\).

For any p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(u \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), \(x \in \mathbb {R}\), and nonzero \(c \in \mathbb {R}\).

The p.d.f. of the semicircle distribution is always nonnegative.

For any p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(u \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), and \(x,y \in \mathbb {R}\).

If the variance \(v\) is given to be zero, then the p.d.f. of the semicircle distribution is the zero functional.

Given a real random variable \(X \sim \mathrm{SC}(\mu , v)\) then for a constant \(y \in \mathbb {R}\), \(X + y \sim \mathrm{SC}(\mu + y, v)\)

Given a real random variable \(X \sim \mathrm{SC}(\mu , v)\) then for a constant \(y \in \mathbb {R}\), \(X + y \sim \mathrm{SC}(y + \mu , v)\)

Given a real random variable \(X \sim \mathrm{SC}(\mu , v)\), then for a constant \(c \in \mathbb {R}\), \(cX \sim \mathrm{SC}(c\mu , c^2v)\)

The map of a semicircle distribution by addition of a constant is semicircular. That is, given a constant \(y \in \mathbb {R}\), \( \mathrm{SC}(\mu , v) \circ (X \mapsto X + y )^{-1} = \mathrm{SC}(\mu + y, v)\).

The map of a semicircle distribution by addition of a constant is semicircular. That is, given a constant \(y \in \mathbb {R}\), \( \mathrm{SC}(\mu , v) \circ (X \mapsto y + X )^{-1} = \mathrm{SC}(y + \mu , v)\).

The map of a semicircle distribution by multiplication by a constant is semicircular. That is, given a constant \(c \in \mathbb {R}\), \( \mathrm{SC}(\mu , v) \circ (X \mapsto cX )^{-1} = \mathrm{SC}(c\mu , c^2v)\).

The map of a semicircle distribution by multiplication by a constant is semicircular. That is, given a constant \(y \in \mathbb {R}\), \( \mathrm{SC}(\mu , v) \circ (X \mapsto y-X )^{-1} = \mathrm{SC}(y-\mu , v)\)

The map of a semicircle distribution by multiplication by a constant is semicircular. That is, given a constant \(c \in \mathbb {R}\), \( \mathrm{SC}(\mu , v) \circ (X \mapsto Xc )^{-1} = \mathrm{SC}(\mu c , c^2v)\).

Given a constant \(c \in \mathbb {R}\), \( \mathrm{SC}(\mu , v) \circ (X \mapsto -X )^{-1} = \mathrm{SC}(-\mu , v)\)

The map of a semicircle distribution by multiplication by a constant is semicircular. That is, given a constant \(y \in \mathbb {R}\), \( \mathrm{SC}(\mu , v) \circ (X \mapsto X - y )^{-1} = \mathrm{SC}(\mu - y , v)\)

Given a real random variable \(X \sim \mathrm{SC}(\mu , v)\), then for a constant \(c \in \mathbb {R}\), \(Xc \sim \mathrm{SC}(\mu c , c^2v)\)

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the p.d.f. \(f : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is strongly measurable.

Let \( \mu \in \mathbb {R} \) and \( v \in \mathbb {R}_{{\gt} 0} \). Then the support of the extended p.d.f. is

Let \(\mathbf{Y}_{n}\) be an \(n \times n\) symmetric matrix with independent entries, where \(\{ Y_{ij}\} _{1\le i\le j}\) are independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. Then, for any \(k\)-index \(\mathbf{i} \in [n]^k\), we have:

\(Var(X) = v\)

The variance of a real semicircle distribution with parameter \((\mu , v)\) is its variance parameter \(v\)

Given \((G,w) \in \mathcal{G}_k\), let us denote the path \(w\) by

Then we can choose the smallest integer appearing in \(\{ i_1,i_2\} \cap \{ i_{2k-1},i_{2k}\} \) such that \(w\) takes the form

Let \(k\) be even and let \(\mathcal{D}_k\) denote the set of Dyck paths of length \(k\)

Then \((G,w)\mapsto {d}(G,w)\) is a bijection \(\mathcal{G}_k^{k/2+1}\to \mathcal{D}_k\).

\(n(n-1)\cdots (n-|G|+1) \le n^{|G|}\).

The sequence \(n\mapsto \frac1n\mathbb {E}\operatorname{Tr}(X_n^k)\) is bounded.

\(\mathbb {E}(Y_{12}^2) = t^{\# E}\)

\(t^{\# E} = t^{k/2}\)

If \(k\) is even and there exists \(e\) such that \(w(e) \ge 3\), then \(\# E \le \frac{k-1}{2}\).

\(\lim _{n\to \infty }\frac{n^{k/2}}{n(n-1)\cdots (n-k/2+1)} = 1\).

\(|G_k|\) is finite.

The measure semicircleReal is a probability measure, no matter the values of \(\mu \in \mathbb {R}\) and \(v \in \mathbb {R}_{\ge 0}\).

Let \( f : \mathbb {R} \to E \) be a function where \( E \) is a normed vector space over \(\mathbb {R}\). For the semicircle distribution with mean \(\mu \in \mathbb {R}\) and variance \( v {\gt} 0 \), we have:

If the variance v is nonzero, then the semicircle distribution has no atoms.

Suppose \(k\) odd. Then, \(\frac{n(n-1)\cdots (n-|G|+1)}{n^{k/2+1}} \le \frac{1}{\sqrt{n}}\).

Suppose \(k\) odd. Then, \(|G| \le \frac{k}{2} + \frac{1}{2}\).

\(\Pi (G,w) = \prod _{e_c\in E^c} \mathbb {E}(Y_{12}^{w(e_c)})\)

The Radon–Nikodym derivative of the semicircle measure semicircleReal \(\mu \) \(v\) with respect to the Lebesgue measure is almost everywhere equal to the semicircle probability density function semicirclePDF \((\mu \), \(v)\).

For a semicircle distribution with mean \(\mu \) and nonzero variance \(v\), the measure semicircleReal \(μ\) \(v\) is absolutely continuous with respect to the Lebesgue measure.

For a semicircle measure with mean \(\mu \) and nonzero variance v, the measure of any measurable set \(s\) equals the Lebesgue integral over \(s\) of the semicircle probability density function at x.

For any real mean \(\mu \), and any nonnegative variance \(v\) that is not zero, and any measurable set \(s\) of real numbers, the semicircle distribution measure of the set \(s\) equals the extended nonnegative real number version (ENNReal.ofReal) of the integral of the semicircle probability density function over s.

If \(v \neq 0\), then the definition the semicircle distribution is defined as the Lebesgue measure weighted by the semicircle probability density function.

If the variance is 0, then the semicircle distribution is exactly the Dirac measure at \(\mu \).

Elements of \(G_k^{k/2+1}\) have \(|E| = k/2\).

Elements of \(G_k^{k/2+1}\) are trees.

For any graph \(G = (V, E)\) appearing in the sum in Equation 4.8, \(|G| \le k/2 + 1\).

\(\prod _{e_c\in E^c} \mathbb {E}(Y_{12}^{w(e_c)}) = \prod _{e_c\in E^c} \mathbb {E}(Y_{12}^2)\)

where \(|\mathcal{D}_k|\) denotes the number of Dyke paths of length \(k\) while \(C_k\) is the \(k\)th Catalan number.

Let \((G,w)\in \mathcal{G}_k\) with \(w\ge 2\), and suppose \(k\) is even. If there exists an edge \(e\) in \(G\) with \(w(e)\ge 3\), then \(|G|\le k/2\).

Let \((G,w)\in \mathcal{G}_k\) with \(w\ge 2\), and suppose \(k\) is even. If there exists a self-edge \(e\in E_s\) in \(G\), then \(|G|\le k/2\).

\(|\sum _{\mathcal{G}_{k}, w \ge 2} - \sum _{\mathcal{G}_k^{k/2+1}}| \le |\mathcal{G}_k|/n\).

Let \(\{ Y_{ij}\} _{1\le i\le j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. Suppose that \(r_k = \max \{ \mathbb {E}(|Y_{11}|^k),\mathbb {E}(|Y_{12}|^k)\} {\lt}\infty \) for each \(k\in \mathbb {N}\). Suppose further than \(\mathbb {E}(Y_{ij})=0\) for all \(i,j\) and set \(t=\mathbb {E}(Y_{12}^2)\). If \(i{\gt}j\), define \(Y_{ij} \equiv Y_{ji}\), and let \(\mathbf{Y}_n\) be the \(n\times n\) matrix with \([\mathbf{Y}_n]_{ij} = Y_{ij}\) for \(1\le i,j\le n\). Let \(\mathbf{X}_n = n^{-1/2}\mathbf{Y}_n\) be the corresponding Wigner matrix. Then

Let \(\{ Y_{ij}\} _{1 \leq i \leq j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\geq 1}\) identically distributed and \(\{ Y_{ij}\} _{1 \leq i {\lt} j}\) identically distributed. Suppose that \(r_k = \max \{ \mathbb {E}(|Y_{11}|^k),\mathbb {E}(|Y_{12}|^k)\} {\lt} \infty \) for each \(k\in \mathbb {N}\). Suppose further than \(\mathbb {E}(Y_{ij})=0\) for all \(i,j\). If \(i{\gt}j\), define \(Y_{ij} \equiv Y_{ji}\), and let \(\mathbf{Y}_n\) be the \(n\times n\) matrix with \([\mathbf{Y}_n]_{ij} = Y_{ij}\) for \(1\le i,j\le n\). Let \(\mathbf{X}_n = n^{-1/2}\mathbf{Y}_n\) be the corresponding Wigner matrix. Then

Suppose \(k\) odd. Then, \(\lim _{n\to \infty } \frac{1}{n}\mathbb {E}\operatorname{Tr}(X_n^k) = 0\).

\(\Pi (G,w) = t^{k/2}\).

\(\lim _{n\to \infty }\mathbb {E}\operatorname{Tr}(X_n^k) = \sum _{(G,w)\in \mathcal{G}^{k/2+1}_k} \Pi (G,w)\)

\(\lim _{n\to \infty } \mathbb {E}\operatorname{Tr}(X_n^k) = t^{k/2}\cdot \# \mathcal{G}_k^{k/2+1}\)

\(\frac1n\mathbb {E}\operatorname{Tr}(X_n^k) = \sum _{(G,w)\in \mathcal{G}^{k/2+1}_k} \Pi (G,w) \cdot \frac{n(n-1)\cdots (n-|G|+1)}{n^{k/2+1}} + O_k(n^{-1})\)

Let \(G=(V,E)\) be a connected finite graph. Then, \(|G|=\# V\le \# E+1\).

Let \(G=(V,E)\) be a connected finite graph. Then, \(|G|=\# V=\# E+1\) if and only if \(G\) is a plane tree.