Inequalities for Laplacian Eigenvalues of Signed Graphs with Given Frustration Number

Abstract

Balanced signed graphs appear in the context of social groups with symmetric relations between individuals where a positive edge represents friendship and a negative edge represents enmities between the individuals. The frustration number f of a signed graph is the size of the minimal set F of vertices whose removal results in a balanced signed graph; hence, a connected signed graph $\dot{G}$ is balanced if and only if $f=0$. In this paper, we consider the balance of $\dot{G}$ via the relationships between the frustration number and eigenvalues of the symmetric Laplacian matrix associated with $\dot{G}$. It is known that a signed graph is balanced if and only if its least Laplacian eigenvalue ${\mu }_n$ is zero. We consider the inequalities that involve certain Laplacian eigenvalues, the frustration number f and some related invariants such as the cut size of F and its average vertex degree. In particular, we consider the interplay between ${\mu }_n$ and f.

1. Introduction

For a simple undirected graph $G=\left(V\right(G),E(G\left)\right)$, let $\sigma :E\left(G\right)⟶\{-1,+1\}$. Then $\dot{G}=(G,\sigma )$ is a signed graph, G is the corresponding underlying graph and $\sigma$ is a sign function (defined on the edge set). We set $n=\left|V\right(\dot{G}\left)\right|$ and $m=\left|E\right(\dot{G}\left)\right|$. The edge set $E\left(\dot{G}\right)$ is composed of subsets containing positive and negative edges, respectively. We interpret an ordinary unsigned graph as a signed graph in which all edges are positive.

A cycle in a signed graph is called balanced if the number of its negative edges is not odd. Accordingly, we say that a signed graph or its subgraph is balanced if every cycle in it (if any) is balanced. A balance is one of the fundamental concepts in the theory of signed graphs; for more details, see [1,2]. An unbalanced signed graph is also called frustrated (mostly in physical domain). The minimum number of edges (resp. vertices) to be deleted such that the signed graph is balanced is called the frustration index (frustration number); these invariants measure how unbalanced the signed graph is.

An application of signed graphs considers social groups with both positive and negative symmetric relations between individuals. The simplest approach to study the behaviour of such a population is to consider a signed graph $\dot{G}$ in which the vertices represent the individuals, while positive edges represent friendships and negative edges enmities between them. In Heider’s theory of balance [3] a social group is said to be balanced if the vertices of the corresponding signed graph can be partitioned into two parts, say X and Y, in such a way that an edge is negative if and only if it joins a vertex in X with a vertex in Y. It is known that in this case the corresponding signed graph is balanced [1,2].

The Laplacian matrix of $\dot{G}$ is the symmetric matrix $L_{\dot{G}}=D_{\dot{G}}-A_{\dot{G}}$, where $D_{\dot{G}}$ is the diagonal matrix of vertex degrees and $A_{\dot{G}}$ is the standard symmetric adjacency matrix of $\dot{G}$. The Laplacian eigenvalues of $\dot{G}$ are identified to be the eigenvalues of $L_{\dot{G}}$. They are denoted by ${\mu }_1,{\mu }_2,\dots ,{\mu }_n$ and indexed non-increasingly. As $L_{\dot{G}}$ is positive semidefinite, Laplacian eigenvalues are non-negative.

The interplay between the eigenvalues of a matrix associated with a signed graph $\dot{G}$ and structural parameters of $\dot{G}$ has received a great deal of attention in literature (not listed here). In particular, relationships between the eigenvalues and the frustration index are considered in [4,5,6,7]. On the other hand, there is a very restricted number of results concerning relationships between the eigenvalues and the frustration number; some of them can be found in [4,8]. This motivates us to establish certain inequalities which estimate particular Laplacian eigenvalues in terms of the frustration number (in this paper, denoted by f) and some related structural parameters. Needles to add, all of them can be seen as estimations of the mentioned structural parameters in terms of the the corresponding eigenvalues. The latter is of particular interest since there are efficient polynomial algorithms for computing eigenvalues, while in general the frustration number is hardly determined.

Our contribution is reported in Section 2. Proofs are separated in Section 3. Some concluding remarks are given in Section 4.

2. Our Contribution

For a vertex subset S, we write $\dot{G}\left[S\right]$ and $\dot{G}-S$ to denote the subgraph induced by S and the subgraph obtained by removing all vertices of S, respectively. We also write $m\left(S\right)$ for the number of edges in $\dot{G}\left[S\right]$ and $c\left(S\right)$ for the cut size of S, i.e., the number of edges of $\dot{G}$ with one end in S and the other in $V\left(\dot{G}\right)\setminus S$. The average vertex degree in S is denoted by ${\overline{d}}_S$. In other words, ${\overline{d}}_S=\frac{1}{\left|S\right|}{\sum }_{i\in S}{d}_i$, where $d_i$ is the degree of the vertex i in $\dot{G}$. In particular, we use F to denote a minimal set of vertices of $\dot{G}$ to be removed such that the resulting signed graph is balanced. Clearly, $\left|F\right|$ is the frustration number f of $\dot{G}$.

In Section 3, we prove the following results.

Theorem 1.

For a signed graph $\dot{G}$ with n vertices and the frustration number f,

$${\mu }_1+{\mu }_2\ge \frac{1}{n-f}c\left(F\right)+{\overline{d}}_F,$$

(1)

where F denotes a minimal set of vertices whose removal results in a balanced signed graph.

The inequality (1) is of the Nordhaus–Gaddum type and gives a relationship between the sum of the two largest Laplacian eigenvalues in terms of f, $c\left(F\right)$ and ${\overline{d}}_F$. We also consider the least Laplacian eigenvalue in the following two results.

Theorem 2.

For a signed graph $\dot{G}$ with n vertices and the frustration number f,

$${\mu }_n\le \frac{1}{n}\left(\frac{f}{n-f}c\left(F\right)+(n-f){\overline{d}}_F\right),$$

(2)

where F denotes a minimal set of vertices whose removal results in a balanced signed graph.

Theorem 3.

For a signed graph $\dot{G}$ with n vertices and the frustration number f,

$${\mu }_n\le \frac{1}{n}\left(c\left(F\right)+f{\overline{d}}_F\right),$$

(3)

where F denotes a minimal set of vertices whose removal results in a balanced signed graph. Equality holds if $\dot{G}$ is balanced.

In [4] Belardo gave an elegant upper bound for ${\mu }_n$,

$${\mu }_n\le f.$$

(4)

It can be easily verified that the upper bounds (2)–(4) are incomparable. The inequalities (3) and (4) immediately give that $f=0$ implies ${\mu }_n=0$; this and the opposite implication, in the case of a connected signed graph, can be found in a work of Zaslavsky [2]. For $\dot{G}$ regular with vertex degree r, in (1)–(3), ${\overline{d}}_F$ can be replaced by r.

We also consider the sum of the first k Laplacian eigenvalues in a particular case.

Theorem 4.

If a signed graph $\dot{G}$ with vertex set $\{1,2,\dots ,n\}$ does not contain unbalanced cycles of length at most l, then for every partition $V\left(\dot{G}\right)=S_1\bigsqcup S_2\bigsqcup \cdots \bigsqcup S_k$, such that $|S_i|\le l-1$, for $1\le i\le k$, we have

$$\sum _{i=1}^k{\mu }_i\ge -2\sum _{i=1}^k\frac{m_i}{|S_i|}+\sum _{j:i\in S_j}\frac{d_i}{|S_j|},$$

where $m_i=m\left(S_i\right)$.

3. Proofs

We resume the notation introduced in the previous sections and also use $m^{-}$ and $m^{\pm }$ (or $m^{-}\left(\dot{G}\right)$ and $m^{\pm }\left(\dot{G}\right)$) to denote the number of negative edges and the difference of the numbers of positive and negative edges in $\dot{G}$, respectively. For a vertex subset S, for the sake of simplicity, we write $m^{-}\left(S\right)$ and $m^{\pm }\left(S\right)$ for $m^{-}\left(\dot{G}\left[S\right]\right)$ and $m^{\pm }\left(\dot{G}\left[S\right]\right)$. Similarly, $c^{-}\left(S\right)$ (resp. $c^{\pm }\left(S\right)$) stands for the number of negative edges (the difference of the numbers of positive and negative edges) of $\dot{G}\left[S\right]$ with exactly one end in S.

The signed graph ${\dot{G}}^S$ obtained from $\dot{G}$ by reversing the sign of each edge with exactly one end in S is said to be switching equivalent to $\dot{G}$. Switching equivalent signed graphs share the same (Laplacian) eigenvalues, which is one of building blocks in the forthcoming proofs. We also apply the following Lemma 1, its consequence formulated in Corollary 1, Theorem 5 obtained by Bollobás and Nikiforov [9] and the Rayleigh principle.

Lemma 1.

For every signed graph $\dot{G}$ with m ($m\ge 1$) edges, there exists a switching equivalent signed graph with $m^{\pm }>0$ and another switching equivalent signed graph with $m^{\pm }<0$.

Proof. 

We consider the first part, i.e., construct a switching equivalent signed graph with $m^{\pm }>0$. Up to the switching equivalence, $\dot{G}$ has a positive edge, and then there exists a partition of $V\left(\dot{G}\right)$, say $T_1\bigsqcup T_2\bigsqcup \cdots \bigsqcup T_k$, such that there is no negative edge in any $G\left[T_i\right]$’s and at least one of them contains a (positive) edge.

If $c^{\pm }\left(T_i\right)\ge 0$, for $1\le i\le k$, we are done. Otherwise, we arrive at the desired switching equivalent signed graph by the following iterative algorithm. Take any $T_i$ for which $c^{\pm }\left(T_i\right)<0$ and make a switching with respect to $T_i$. Clearly, all the edges (if any) in $T_i$ remain positive, while $c^{\pm }\left(T_i\right)$ becomes positive. Continue with the next such a $T_i$. Since every step is followed by a strict decreasing in the total number of negative edges, after a finite repetition we arrive at the result.

Interchanging the roles of positive and negative edges in the previous part of the proof, we arrive at the proof of the second part of the lemma. □

A similar result can be found in [10]. Applying the algorithm described in the previous proof, we can obtain some specified switching equivalent signed graphs. Two of them, which will be used in the forthcoming proofs, are pointed out in the next corollary.

Corollary 1.

For every vertex set partition $S_1\bigsqcup S_2\bigsqcup \cdots \bigsqcup S_k$$(1\le k\le n)$ of a signed graph

(i) 

there exists a switching equivalent signed graph in which $2m^{-}\left(S_i\right)\ge m\left(S_i\right)$ and

(ii) 

there exists a switching equivalent signed graph in which $2m^{-}\left(S_i\right)\le m\left(S_i\right)$ and $2c^{-}\left(S_i\right)\ge c\left(S_i\right)$,

for $1\le i\le k$.

The first inequality in (i) and (ii) is strict whenever $S_i$ induces a signed graph with at least one edge.

Proof. 

Observe that the algorithm described in the proof of Lemma 1 (or its counterpart with positive and negative edges interchanged) can be applied irrespectively of any subgraph induced by $S_i$, for $1\le i\le k$. In this way we arrive at the inequality of (i) and the first inequality of (ii), which are strict whenever $S_i$ induces a signed graph with at least one edge.

To conclude (ii), we apply the same algorithm once again, but now with respect to the partition $S_1\bigsqcup S_2\bigsqcup \cdots \bigsqcup S_k$. □

We quote the following result.

Theorem 5.

[9] Let $M=\left(m_{ij}\right)$ be a Hermitian matrix of size n and with eigenvalues ${\nu }_1,{\nu }_2,\dots ,{\nu }_n$ taken with their repetition and indexed non-increasingly. For every partition $\{1,2,\dots ,n\}=S_1\bigsqcup S_2\bigsqcup \cdots \bigsqcup S_k$ ($2\le k\le n$), we have

$$\sum _{i=1}^k{\nu }_i\ge \sum _{i=1}^k\frac{1}{|S_i|}\sum _{i,j\in S_i}{m}_{ij}$$

and

$$\sum _{i=n-k+2}^n{\nu }_i\le \sum _{i=1}^k\frac{1}{|S_i|}\sum _{i,j\in S_i}{m}_{ij}-\frac{1}{n}\mathrm{sum}\left(M\right),$$

where $\mathrm{sum}\left(M\right)$ denotes the sum of the entries of M.

Taking the Laplacian matrix of a signed graph we arrive at the following.

Theorem 6.

Let $\dot{G}$ be a signed graph with n vertices, m edges, Laplacian eigenvalues ${\mu }_1,{\mu }_2,\dots ,{\mu }_n$ and the partition $V\left(\dot{G}\right)=S_1\bigsqcup S_2\bigsqcup \cdots \bigsqcup S_k$ ($2\le k\le n$). Then, it holds

$$\sum _{i=1}^k{\mu }_i\ge -2\sum _{i=1}^k\frac{m_i^{\pm }}{|S_i|}+\sum _{j:i\in S_j}\frac{d_i}{|S_j|}$$

(5)

and

$$\sum _{i=n-k+2}^n{\mu }_i\le -2\left(\sum _{i=1}^k\frac{m_i^{\pm }}{|S_i|}+\frac{(m-m^{\pm })}{n}\right)+\sum _{j:i\in S_j}\frac{d_i}{|S_j|},$$

(6)

with $m^{\pm }=m^{\pm }\left(\dot{G}\right)$ and $m_i^{\pm }=m_i^{\pm }\left(S_i\right)$.

Proof. 

This follows directly from Theorem 5. □

We are ready to prove the announced results.

Proof of Theorem 1.

Let F be a minimal set of vertices whose removal results in a balanced signed graph. Without loss of generality, we may assume that all the edges of $\dot{G}-F$ are positive, and in that case we denote this subgraph by H. Using Theorem 6, we compute

$$\begin{array}{cc}\hfill {\mu }_1+{\mu }_2\ge & -2\left(\frac{1}{n-f}m\left(H\right)+\frac{1}{f}{m}^{\pm }\left(F\right)\right)+\frac{1}{n-f}\sum _{i\in V\left(H\right)}{d}_i+\frac{1}{f}\sum _{i\in F}{d}_i\hfill \\ \hfill =& \frac{1}{n-f}c\left(F\right)+\frac{1}{f}\left(-2m^{\pm }\left(F\right)+2m\left(F\right)+c\left(F\right)\right)\hfill \\ \hfill =& \left(\frac{1}{n-f}+\frac{1}{f}\right)c\left(F\right)+\frac{4}{f}{m}^{-}\left(F\right),\hfill \end{array}$$

giving

$${\mu }_1+{\mu }_2\ge \frac{1}{f}\left(\frac{n}{n-f}c\left(F\right)+4m^{-}\left(F\right)\right).$$

This inequality holds for every signed graph belonging to the switching class of $\dot{G}$ and in which the edges of H remain positive. Selecting such a signed graph with largest $m^{-}\left(F\right)$, and using Corollary 1(i), we obtain

$${\mu }_1+{\mu }_2\ge \frac{1}{f}\left(\frac{n}{n-f}c\left(F\right)+2m\left(F\right)\right).$$

Further, as $c\left(F\right)+2m\left(F\right)={\overline{d}}_{F}f$, we get

$$\begin{array}{cc}\hfill {\mu }_1+{\mu }_2\ge & \frac{1}{f}\left(\frac{n}{n-f}c\left(F\right)-c\left(F\right)+c\left(F\right)+2m\left(F\right)\right)\hfill \\ \hfill =& \frac{1}{f}\left(\frac{f}{n-f}c\left(F\right)+{\overline{d}}_{F}f\right)\hfill \\ \hfill =& \frac{1}{n-f}c\left(F\right)+{\overline{d}}_F,\hfill \end{array}$$

and we are done. □

Proof of Theorem 2.

Let H be as in the proof of Theorem 1. By Theorem 6 (for $k=2$), we get

$$\begin{array}{cc}\hfill {\mu }_n\le & -2\left(\frac{1}{n-f}m\left(H\right)+\frac{1}{f}{m}^{\pm }\left(F\right)\right)+\frac{1}{n-f}\sum _{i\in V\left(H\right)}{d}_i+\frac{1}{f}\sum _{i\in F}{d}_i-\frac{1}{n}\mathrm{sum}\left(L_{\dot{G}}\right)\hfill \\ \hfill =& \left(\frac{1}{n-f}+\frac{1}{f}\right)c\left(F\right)+\frac{4}{f}{m}^{-}\left(F\right)-\frac{4}{n}\left(c^{-}\left(F\right)+m^{-}\left(F\right)\right),\hfill \end{array}$$

giving

$${\mu }_n\le \left(\frac{n}{f(n-f)}\right)c\left(F\right)-\frac{4}{n}\left(c^{-}\left(F\right)-\frac{(n-f)}{f}{m}^{-}\left(F\right)\right).$$

(7)

This inequality holds for switching equivalent signed graphs with minimum $m^{-}\left(F\right)$ (which, by Corollary 1(ii), does not exceed $\frac{1}{2}m\left(F\right)$), and among them for those with maximum $c^{-}\left(F\right)$ (which, by Corollary 1(ii), is not less than $\frac{1}{2}c\left(F\right)$). Hence,

$$\begin{array}{cc}\hfill {\mu }_n\le & \left(\frac{n}{f(n-f)}\right)c\left(F\right)-\frac{2}{n}\left(c\left(F\right)-\frac{(n-f)}{f}m\left(F\right)\right)\hfill \\ \hfill =& \left(\frac{n}{f(n-f)}\right)c\left(F\right)-\frac{2}{n}\left(c\left(F\right)-\frac{(n-f)}{f}m\left(F\right)\right)+\frac{n-f}{fn}c\left(F\right)-\frac{n-f}{fn}c\left(F\right)\hfill \\ \hfill =& \frac{1}{n}\left(\frac{f}{n-f}c\left(F\right)+(n-f){\overline{d}}_F\right),\hfill \end{array}$$

and we are done. □

The next proof is based on the Rayleigh principle.

Proof of Theorem 3.

As in the previous proofs, without loss of generality, we may assume that the edges with both ends outside F are all positive. If $\mathbf{j}$ is the all-1 vector, then using the Rayleigh principle, we obtain

$$\begin{array}{cc}\hfill {\mu }_n\le & \frac{{\mathbf{j}}^T{L}_{\dot{G}}\mathbf{j}}{{\mathbf{j}}^T\mathbf{j}}=\frac{4}{n}(c^{-}\left(F\right)+m^{-}\left(F\right))\hfill \\ \hfill \le & \frac{2}{n}(c\left(F\right)+m\left(f\right))=\frac{1}{n}(c\left(F\right)+f{\overline{d}}_F),\hfill \end{array}$$

where for the latter inequality we switch into a signed graph in which $2c^{-}\left(F\right)\le c\left(F\right)$ and $2m^{-}\left(F\right)\le m\left(F\right)$ (obtained as those of Corollary 1). If $\dot{G}$ is balanced, then ${\mu }_n=0$ [2], and also F is empty, giving the equality. □

Proof of Theorem 4.

Since $|S_i|\le l-1$, we have that $\dot{G}\left[S_i\right]$ does not contain unbalanced cycles, i.e., it is a balanced subgraph. In that case, $\dot{G}$ switches into a signed graph in which $\dot{G}\left[S_i\right]$ does not contain a negative edge. The result follows by Theorem 6. □

4. Concluding Remarks

As switching equivalent signed graphs share the same spectrum, it follows that the inequality (5) of Theorem 6 can be written as

$$\sum _{i=1}^k{\mu }_i\ge -2min\left\{\sum _{i=1}^k\frac{m_i^{\pm }}{|S_i|}:\dot{H}\in \mathcal{G}\right\}+\sum _{j:i\in S_j}\frac{d_i}{|S_j|},$$

where $\mathcal{G}$ denotes the switching class of $\dot{G}$, and similarly for the inequality (6) of the same theorem. Applying Lemma 1 to every $\dot{G}\left[S_i\right]$, we transform (5) into

$$\sum _{i=1}^k{\mu }_i\ge \sum _{m\left(S_i\right)\ne \varnothing }\frac{2}{|S_i|}+\sum _{j:i\in S_j}\frac{d_i}{|S_j|},$$

and, again, similarly for (6). Finally, by the corresponding theorem, (5) holds for $k\ge 2$. Of course, using the Rayleigh principle, we get

$${\mu }_1\ge {\displaystyle \frac{{\mathbf{j}}^T{L}_{\dot{G}}\mathbf{j}}{{\mathbf{j}}^T\mathbf{j}}}={\displaystyle \frac{2(-m^{\pm }+m)}{n}},$$

(8)

and so it also holds for $k=1$. Moreover, by (8), we have

$${\mu }_1\ge \frac{4m^{-}}{n}.$$

If $\dot{G}$ has at least one edge, then by Lemma 1, there exists a switching equivalent signed graph satisfying $m^{-}\ge ⌊\frac{m}{2}+1⌋$, which gives

$${\mu }_1\ge \frac{4⌊\frac{m+2}{2}⌋}{n}.$$

A natural and, in this case, difficult question is how tight the inequalities proved in the previous section are. Our numerical experiments show that for appropriately chosen signed graphs they can give a good estimate. For example, taking the complete signed graph with all the edges being negative, we get $f=n-2$, $c\left(F\right)=2(n-2)$, ${\overline{d}}_F=n-1$, and hence, by (2), we get

$${\mu }_n\le \frac{1}{n}({(n-2)}^2+2(n-1)).$$

Say, for $n=6$, this gives $4={\mu }_6\le 4.33$.

Regarding the inequality (7) observe that the minimum of $m^{-}\left(F\right)$ in the switching class of $\dot{G}$ is equal to the minimum number ℓ of edges of F whose removal results in a balanced subgraph of $\dot{G}\left[F\right]$; we have mentioned in Section 1 that this invariant is known as the frustration index of $\dot{G}\left[F\right]$. Thus, by replacing $m^{-}\left(F\right)$ with $\ell \left(F\right)$ in (7), we get

$$\begin{array}{cc}\hfill {\mu }_n\le & \left(\frac{n}{f(n-f)}\right)c\left(F\right)-\frac{2}{n}c\left(F\right)+4\frac{(n-f)}{fn}\ell \left(F\right)\hfill \\ \hfill =& \left(\frac{1}{n-f}+\frac{1}{f}-\frac{2}{n}\right)c\left(F\right)+4\frac{(n-f)}{fn}\ell \left(F\right)\hfill \\ \hfill \le & \left(\frac{1}{n-1}+1-\frac{2}{n}\right)c\left(F\right)+4\frac{(n-1)}{n}\ell \left(F\right)\hfill \\ \hfill \le & \frac{1}{n}\left(\frac{n^2+2}{n-1}c\left(F\right)+4(n+1)\ell \left(F\right)\right),\hfill \end{array}$$

giving an estimate in terms of $c\left(F\right)$ and $\ell \left(F\right)$.

All the foregoing results can be formulated in the case of the spectrum of the adjacency matrix. For example, the counterpart to Theorem 4 reads as follows.

Theorem 7.

If a signed graph $\dot{G}$ with non-increasingly indexed eigenvalues (of the adjacency matrix) ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ does not contain unbalanced cycles of length at most l, then for every partition $V\left(\dot{G}\right)=S_1\bigsqcup S_2\bigsqcup \cdots \bigsqcup S_k$, such that $|S_i|\le l-1$, for $1\le i\le k$, we have

$$\sum _{i=1}^k{\lambda }_i\ge 2\sum _{i=1}^k\frac{m_i}{|S_i|}$$

with $m_i=m\left(S_i\right)$.

Along with an analogous proof. Since Theorem 4 and its counterpart require a particular structure of a signed graph, it is natural to ask whether such a cyclic structure can be determined by some spectral invariants. We prove that this can be done by means of the eigenvalues of $\dot{G}$ and the eigenvalues of its underlying graph. Recall that a walk in a signed graph is a sequence of alternate vertices and edges such that consecutive vertices are incident with the corresponding edge. A walk is positive if the number of its negative edges (counted with their multiplicity if there are repeated edges) is not odd. Otherwise, it is negative.

Theorem 8.

If ${\lambda }_1\left(\dot{G}\right),{\lambda }_2\left(\dot{G}\right),\dots ,{\lambda }_n\left(\dot{G}\right)$ and ${\lambda }_1\left(G\right),{\lambda }_2\left(G\right),\dots ,{\lambda }_n\left(G\right)$ are the eigenvalues of a signed graph $\dot{G}$ and the eigenvalues of its underlying graph G, respectively, and k is the smallest non-negative integer such that ${\sum }_{i=1}^n{\lambda }_i{\left(G\right)}^k\ne {\sum }_{i=1}^n{\lambda }_i{\left(\dot{G}\right)}^k$. Then

(i) 

$\dot{G}$ does not contain an unbalanced cycle whose length is less than k and

(ii) 

${\sum }_{i=1}^n{\lambda }_i{\left(G\right)}^k-{\sum }_{i=1}^n{\lambda }_i{\left(\dot{G}\right)}^k=4k{u}_k$, where $u_k$ denotes the number of unbalanced cycles of length k in $\dot{G}$.

Proof. 

(i) Assume the contrary and let $l(l<k)$ be the length of the shortest unbalanced cycle in $\dot{G}$.

Recall that ${\sum }_{i=1}^n{\lambda }_i{\left(G\right)}^l$ and ${\sum }_{i=1}^n{\lambda }_i{\left(\dot{G}\right)}^l$ stand for the number of closed walks of length l in G and the difference of positive and negative closed walks of length l in $\dot{G}$, respectively. We divide closed walks of length l into the two types: those which do not traverse a cycle of length l and those which do. By the choice of l, we have that the number of walks of the first type in G is equal to the difference of positive and negative walks of the same type in $\dot{G}$. If $n_l$ denotes the number of cycles of length l in G, then the number of walks of the second type in G is $2l{n}_l$, while the difference of positive and negative ones in $\dot{G}$ is $2l(n_l-2u_l)$ ($u_l$ being the number of unbalanced cycles of length l). Hence,

$$\sum _{i=1}^n{\lambda }_i{\left(G\right)}^l-\sum _{i=1}^n{\lambda }_i{\left(\dot{G}\right)}^l=4l{u}_l>0,$$

contradicting the assumption of the theorem.

(ii) By setting $l=k$ in the previous part of the proof, we get the desired equality. □