Maximum Eigenvalue of a Graph

Statement

Let $G=(V,E)$ be a graph on $n$ vertices with adjacency matrix $A\in \{0,1{\}}^{n\times n}$, that is, $a_{ij}=1$ if $(i,j)\in E$ and $a_{ij}=0$ otherwise. Since $A$ is symmetric, it has real eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_n$. Let $\tilde{\delta }$ be the avarage degree of $G$, defined as

$$\tilde{\delta }=\frac{1}{n}\sum _{i=1}^n{\delta }_i=\frac{2|E|}{n}$$

where ${\delta }_i$ is the degree of vertex $i$.

The maximum eigenvalue ${\lambda }_1$ of $A$ is greater than or equal to the average degree $\tilde{\delta }$ of $G$.

---

Proof

By the variational definition of the eigenvalues (see (Wilkinson, 1988)) of a symmetric matrix, we have that

$${\lambda }_i=\underset{S\subseteq {\mathbb{R}}^n,\dim (S)=i}{\max }\underset{x\in S,x\ne 0}{\min }\frac{x^{T}Ax}{x^{T}x}=\underset{S\subseteq {\mathbb{R}}^n,\dim (S)=n-i+1}{\min }\underset{x\in S,x\ne 0}{\max }\frac{x^{T}Ax}{x^{T}x},$$

where $S$ is a subspace of ${\mathbb{R}}^n$ with dimension $\dim (S)$. For the special case of the maximum eigenvalue, i.e. $i=1$, we can take $S={\mathbb{R}}^n$ (on the right-side of the equation) and obtain the following inequality

$${\lambda }_1=\underset{x\in {\mathbb{R}}^n,x\ne 0}{\max }\frac{x^{T}Ax}{x^{T}x}.$$

Now, by taking $x=1$ (the vector of all ones), we have

$$\begin{array}{rl}{\lambda }_1& =\underset{x\in {\mathbb{R}}^n,x\ne 0}{\max }\frac{x^{T}Ax}{x^{T}x}\ge \frac{1^{T}A1}{1^{T}1}\\ & =\frac{{\sum }_{i,j}{a}_{i,j}}{n}=\frac{2|E|}{n}=\tilde{\delta }.\end{array}$$

References

Wilkinson, J. H. (1988). The algebraic eigenvalue problem. Oxford University Press, Inc.