Minimum Degree and Spectral Radius of Subgraphs

Rayleigh Quotients and Graph Spectral Radius

The spectral radius records the largest absolute value of an adjacency-matrix eigenvalue. Rayleigh quotients give a direct way to compare it with structural features of a graph, without first computing all the eigenvalues. Two useful consequences are that the spectral radius is at least the minimum degree, and that it cannot increase when we pass to an induced subgraph.

Throughout, graphs are finite and simple. For a graph $G=(V,E)$ with $n=|V|\ge 1$, its adjacency matrix $\mathbf{A}(G)$ has entry $1$ in positions $u,v$ and $v,u$ when $uv\in E$, and entry $0$ otherwise. It is a real symmetric matrix. Its spectral radius $\rho(G)$ is the largest absolute value of its eigenvalues. For a nonzero real vector $x$ indexed by $V$, define its Rayleigh quotient by

R_G(x)=\frac{x^{\mathsf T}\mathbf{A}(G)x}{x^{\mathsf T}x}.

The denominator is positive because $x\ne 0$. The numerator can also be written as $2\sum_{uv\in E}x_ux_v$, since each edge contributes twice to the matrix product.

Theorem (Rayleigh principle for graphs): For a finite simple graph $G$ with at least one vertex, $$ \rho(G)=\max_{x\ne 0}R_G(x). $$

Proof. By the spectral theorem for real symmetric matrices, $\mathbf{A}(G)$ has an orthonormal basis of eigenvectors with real eigenvalues. The maximum of $R_G(x)$ over nonzero $x$ is therefore the largest eigenvalue, which we denote by $\lambda_{\max}$: expressing $x$ in that eigenbasis makes the quotient a weighted average of the eigenvalues, and an eigenvector for $\lambda_{\max}$ attains the maximum. It remains to check that this largest eigenvalue equals the largest absolute value of any eigenvalue. For every real vector $x$, let $|x|$ be the vector whose coordinates are the absolute values of the coordinates of $x$. Because every entry of $\mathbf{A}(G)$ is nonnegative, \[ |x^{\mathsf T}\mathbf{A}(G)x| \le |x|^{\mathsf T}\mathbf{A}(G)|x| \le \lambda_{\max}\,|x|^{\mathsf T}|x| =\lambda_{\max}\,x^{\mathsf T}x. \] The second inequality follows from the maximum property of $\lambda_{\max}$; it also shows $\lambda_{\max}\ge 0$, since every quotient is at most $\lambda_{\max}$ and a coordinate vector has quotient $0$. Applying the displayed inequality to a unit eigenvector with eigenvalue $\mu$ gives $|\mu|\le\lambda_{\max}$. Since $\lambda_{\max}$ is itself an eigenvalue, it equals the spectral radius. $\square$

Minimum Degree Gives a Lower Bound

Theorem: If $G$ is a finite simple graph with at least one vertex, then $$ \rho(G)\ge \frac{2|E|}{|V|}\ge \delta(G). $$ In particular, $\rho(G)\ge\delta(G)$.

Proof. Use the vector $\mathbf{1}$ whose coordinate at each vertex is $1$. Its squared length is $|V|$. The numerator $\mathbf{1}^{\mathsf T}\mathbf{A}(G)\mathbf{1}$ is $2|E|$, since each edge contributes $1$ at each of its two endpoints. Thus $R_G(\mathbf{1})=2|E|/|V|$, and the Rayleigh principle gives $\rho(G)\ge 2|E|/|V|$. Also, the sum of the degrees is $2|E|$, because each edge contributes $1$ to the degree of each endpoint. Every vertex degree is at least $\delta(G)$, so their average $2|E|/|V|$ is at least $\delta(G)$. Combining the inequalities proves the claim. $\square$

This argument actually gives the average degree as a lower bound, which can be stronger than the minimum-degree bound. The graph need not be connected. If $G$ has no edges but at least one vertex, both its minimum degree and spectral radius are $0$, so the theorem still applies.

Worked Example: The Minimum-Degree Bound for a Star

Let $G=K_{1,3}$, with vertex set $\{c,1,2,3\}$ and edge set $\{c1,c2,c3\}$. The center $c$ has degree $3$, and each other vertex has degree $1$, so $\delta(G)=1$. There are $3$ edges and $4$ vertices, giving average degree $2(3)/4=3/2$. The theorem therefore gives $\rho(G)\ge 3/2\ge 1$.

For the exact spectral radius, consider a vector with coordinate $\sqrt{3}$ at $c$ and coordinate $1$ at each leaf. Multiplication by $\mathbf{A}(G)$ gives coordinate $3$ at $c$ and $\sqrt{3}$ at each leaf. These are $\sqrt{3}$ times the original coordinates, so $\sqrt{3}$ is an eigenvalue. To check that no eigenvalue has larger absolute value, write an eigenvector’s center coordinate as $a$, its leaf coordinates as $b_1,b_2,b_3$, and its eigenvalue as $\lambda$. The eigenvalue equations are $\lambda b_i=a$ for each leaf and $\lambda a=b_1+b_2+b_3$. If $\lambda\ne0$, these imply $\lambda^2a=3a$; for a nonzero eigenvector in this case $a\ne0$, so $\lambda^2=3$. If $\lambda=0$, the equations give $a=0$ and $b_1+b_2+b_3=0$. Hence the remaining eigenvalues are $0$, and $\rho(G)=\sqrt{3}$.

Check: The calculated value satisfies both bounds: $\sqrt{3}\ge 3/2$, since $3\ge 9/4$, and $3/2\ge\delta(G)=1$. The average-degree quotient itself is $R_G(\mathbf{1})=6/4=3/2$, as required.

Induced Subgraphs Cannot Increase Spectral Radius

Theorem: Let $G$ be a finite simple graph, and let $H=G[S]$ be the induced subgraph on a nonempty vertex set $S\subseteq V(G)$. Then $$ \rho(H)\le \rho(G). $$

Proof. Take any nonzero real vector $y$ indexed by $S$. Extend it to a vector $x$ indexed by $V(G)$ by setting $x_v=y_v$ for $v\in S$ and $x_v=0$ for $v\notin S$. Since $H$ is induced, its edges are exactly the edges of $G$ with both endpoints in $S$. Thus $x^{\mathsf T}\mathbf{A}(G)x=y^{\mathsf T}\mathbf{A}(H)y$, and $x^{\mathsf T}x=y^{\mathsf T}y$. Consequently $R_G(x)=R_H(y)$. The Rayleigh principle gives $R_G(x)\le\rho(G)$ for every such $y$; maximizing over nonzero $y$ gives $\rho(H)\le\rho(G)$. $\square$

The argument works because a vector on the induced subgraph can be viewed as a vector on the whole graph by assigning zero to every omitted vertex. The quotient is unchanged: edges with an omitted endpoint contribute zero, and all edges within $S$ are retained. If $S$ is empty, one may adopt the convention $\rho(G[S])=0$; then the inequality holds because spectral radii are nonnegative.

Worked Example: An Induced Path Inside a Cycle

Let $G$ have vertex set $\{1,2,3,4\}$ and edge set $\{12,23,34,41\}$, so $G=C_4$. Take $S=\{1,2,3\}$. The induced subgraph $H=G[S]$ has vertex set $\{1,2,3\}$ and edge set $\{12,23\}$, so it is a path on three vertices.

Every vertex of $G$ has degree $2$. The all-ones vector is therefore an eigenvector with eigenvalue $2$. Also, for any vector $x$, the inequality $2|x_ux_v|\le x_u^2+x_v^2$ on each edge gives \[ |x^{\mathsf T}\mathbf{A}(G)x| \le \sum_{uv\in E(G)}(x_u^2+x_v^2) =2\sum_{v\in V(G)}x_v^2. \] The last equality holds because each vertex belongs to two edges. Hence every eigenvalue has absolute value at most $2$, and $\rho(G)=2$.

For $H$, the vector with coordinates $1,\sqrt{2},1$ in vertex order $1,2,3$ is an eigenvector with eigenvalue $\sqrt{2}$: multiplication by the adjacency matrix gives coordinates $\sqrt{2},2,\sqrt{2}$. The eigenvalue equations for a vector $(a,b,c)$ are $\lambda a=b$, $\lambda b=a+c$, and $\lambda c=b$. If $\lambda\ne0$, they imply $\lambda^2b=2b$; a nonzero eigenvector then has $b\ne0$, so $\lambda=\pm\sqrt{2}$. The zero eigenvalue is also possible, so $\rho(H)=\sqrt{2}$.

Check: The comparison is $\sqrt{2}\le2$, since both sides are nonnegative and $2\le4$ after squaring. The vector on $H$, extended by $0$ at vertex $4$, has the same Rayleigh quotient in $G$: its numerator is $2\sqrt{2}+2\sqrt{2}=4\sqrt{2}$, its squared length is $1+2+1=4$, and the quotient is $\sqrt{2}$.

Equality and Disconnected Graphs

Induced-subgraph monotonicity allows equality for a proper induced subgraph. For example, let $G$ have vertex set $\{1,2,3,4\}$ and edge set $\{12,23\}$. Its non-isolated component is a path on three vertices, and its other component is an isolated vertex. The path has spectral radius $\sqrt{2}$, as shown by the eigenvalue equations above; adding an isolated vertex adds only a zero eigenvalue. Thus $\rho(G)=\sqrt{2}$. The proper induced subgraph on $\{1,2,3\}$ also has spectral radius $\sqrt{2}$. Omitting an isolated vertex has not changed the spectral radius.

Worked Example: Strict and Equal Comparisons in a Disconnected Graph

For the graph $G$ just defined, consider two induced subgraphs. On $S_1=\{1,2,4\}$, the induced graph has the single edge $12$ and isolated vertex $4$. Its adjacency matrix has eigenvalues $1,-1,0$: the vectors supported on $1,2$ with coordinates $(1,1)$ and $(1,-1)$ give eigenvalues $1$ and $-1$, while the vector supported at $4$ gives eigenvalue $0$. Therefore $\rho(G[S_1])=1<\sqrt{2}=\rho(G)$. On $S_2=\{1,2,3\}$, the induced graph is the path with spectral radius $\sqrt{2}$, so $\rho(G[S_2])=\rho(G)$.

Check: The first comparison is strict because $1<\sqrt{2}$, which follows by squaring the positive quantities and obtaining $1<2$. The second is equality because both graphs have the same path component and the only omitted vertex is isolated.

Common Pitfall: Eigenvalues Are Not Inherited

A principal submatrix does not generally have eigenvalues that also occur in the full matrix. In the cycle example, the full graph has spectral radius $2$, while the induced path has spectral radius $\sqrt{2}$, not $2$. The correct conclusion is an inequality, proved by extending vectors by zero and comparing Rayleigh quotients. It is not a claim that the two graphs share eigenvalues.

A second error is to confuse the minimum degree with the average degree in the lower-bound proof. The all-ones vector gives $2|E|/|V|$, the average degree; the inequality $\rho(G)\ge\delta(G)$ follows only after observing that the average of all vertex degrees is at least their minimum. For a graph with at least one vertex, the full chain is \[ \rho(G)\ge \frac{2|E|}{|V|}\ge\delta(G). \] Neither inequality says that the spectral radius must equal the minimum degree.

Check Your Understanding

Use Rayleigh quotients and the stated graph definitions to answer the following.

For a graph with $5$ vertices and $6$ edges, what lower bound does the all-ones vector give for its spectral radius?
Let $G$ have vertex set $\{1,2,3\}$ and edge set $\{12,23\}$. Find $\delta(G)$ and the average degree, then state the resulting lower bounds on $\rho(G)$.
Explain why extending a vector by zero proves $\rho(G[S])\le\rho(G)$ when $G[S]$ is induced.
Give an example of a proper induced subgraph with the same spectral radius as its graph, and explain why equality occurs.
In the cycle-to-path example, why does the spectral-radius comparison not imply that the path’s largest eigenvalue is an eigenvalue of the cycle?