From a Graph Spectrum to an Induced Subgraph
An induced subgraph keeps a selected set of vertices and every edge of the original graph whose two endpoints are in that set. Its adjacency matrix is therefore a principal submatrix of the original adjacency matrix. This link makes eigenvalue interlacing useful: once the eigenvalues of a graph are ordered, they give bounds on the eigenvalues of each of its induced subgraphs.
All graphs below are finite and simple. For a graph \(G\), its adjacency matrix \(\mathbf{A}(G)\) has entry \(1\) in positions corresponding to adjacent vertices and entry \(0\) otherwise. It is a real symmetric matrix, so its eigenvalues are real. Write them in nonincreasing order, repeating each eigenvalue according to its multiplicity:
For an induced subgraph \(H=G[S]\) with \(k=|S|\) vertices, write its ordered adjacency eigenvalues as \(\mu_1\ge\mu_2\ge\cdots\ge\mu_k\). Equal eigenvalues occupy multiple positions in these lists. The position, not just the distinct value, matters when applying interlacing.
The theorem applies because we can list the vertices of \(S\) first: in that ordering, \(\mathbf{A}(H)\) is the \(k\)-by-\(k\) upper-left principal submatrix of \(\mathbf{A}(G)\). The two bounds for \(\mu_i\) come from positions \(i\) and \(i+n-k\) in the parent spectrum. Thus the size difference \(n-k\) determines how far apart those positions are. If just one vertex is deleted, each eigenvalue of the smaller graph lies between consecutive eigenvalues of the original graph. If several vertices are omitted, the interval widens accordingly.
Interlacing does not usually determine the subgraph spectrum exactly. It gives necessary bounds, which can certify that an eigenvalue cannot exceed or fall below a specified value. When the subgraph is small enough to compute directly, comparing its eigenvalues with the interlacing intervals also checks that the ordering and indexing have been handled correctly.
Using the Indexing Carefully
Proof. Set \(i=1\) in the interlacing inequalities to obtain \(\lambda_1(G)\ge\mu_1(H)\ge\lambda_{1+n-k}(G)=\lambda_{n-k+1}(G)\). Set \(i=k\) to obtain \(\lambda_k(G)\ge\mu_k(H)\ge\lambda_{k+n-k}(G)=\lambda_n(G)\). These are exactly the stated bounds. \(\square\)
For an intermediate eigenvalue, use its own index rather than the first or last bound. A reliable procedure is to identify \(n\) and \(k\), write down the sorted parent list, and then calculate the two parent indices \(i\) and \(i+n-k\) for each subgraph eigenvalue \(\mu_i\). Repeated parent eigenvalues must remain in the list: removing repetitions changes the indices and can produce a false bound.
Worked Applications
Worked Example: Two Edges Induced in a Path
Let \(G=P_5\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,23,34,45\}\). Take \(S=\{1,2,4,5\}\) and \(H=G[S]\). Its edge set is \(\{12,45\}\): edges \(23\), \(34\) and any edge with an omitted endpoint do not belong to \(H\). Thus \(H\) consists of two disjoint edges.
First calculate the parent spectrum. For a path, the characteristic polynomials satisfy \(p_0(x)=1\), \(p_1(x)=x\), and \(p_r(x)=xp_{r-1}(x)-p_{r-2}(x)\). Applying the recurrence gives \(p_2=x^2-1\), \(p_3=x^3-2x\), \(p_4=x^4-3x^2+1\), and $$ p_5=x(x^4-4x^2+3)=x(x^2-1)(x^2-3). $$ The roots are \(\sqrt3,1,0,-1,-\sqrt3\), already in nonincreasing order. Hence \(n=5\), \(k=4\), and \(n-k=1\).
Each component of \(H\) is a single edge, with adjacency matrix \(\begin{pmatrix}0&1\\1&0\end{pmatrix}\) and eigenvalues \(1,-1\). Therefore the ordered spectrum of \(H\) is \(1,1,-1,-1\). Applying interlacing at all four positions gives:
| Index \(i\) | Interlacing interval | Subgraph value |
|---|---|---|
| 1 | \(\sqrt3\ge\mu_1\ge1\) | \(\mu_1=1\) |
| 2 | \(1\ge\mu_2\ge0\) | \(\mu_2=1\) |
| 3 | \(0\ge\mu_3\ge-1\) | \(\mu_3=-1\) |
| 4 | \(-1\ge\mu_4\ge-\sqrt3\) | \(\mu_4=-1\) |
For instance, the lower endpoint at \(i=3\) is \(\lambda_{3+5-4}=\lambda_4=-1\), so the interval is \(0\ge\mu_3\ge-1\). Check: the eigenvalues of \(H\) sum to \(1+1-1-1=0\), as the diagonal of its adjacency matrix is zero. Their squared sum is \(1+1+1+1=4\). The graph has two edges, so its adjacency matrix has four entries equal to \(1\); the trace of its square is therefore \(4\), agreeing with that squared-eigenvalue sum.
Worked Example: A Four-Vertex Induced Subgraph of a Cycle
Let \(G=C_6\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,23,34,45,56,61\}\). Select \(S=\{1,2,3,5\}\). The induced subgraph \(H=G[S]\) has exactly the edges \(\{12,23\}\). Vertex \(5\) is isolated in \(H\), because its two neighbors in \(G\), vertices \(4\) and \(6\), are not in \(S\).
The cycle eigenvalues are \(2\cos(2\pi j/6)\) for \(j=0,1,2,3,4,5\). Evaluating these gives \(2,1,-1,-2,-1,1\), which in nonincreasing order is \(2,1,1,-1,-1,-2\). In particular, multiplicities are retained. Here \(n=6\), \(k=4\), and \(n-k=2\).
The non-isolated part of \(H\) is the path on three vertices, whose adjacency eigenvalues are \(\sqrt2,0,-\sqrt2\); the isolated vertex contributes one more eigenvalue \(0\). Thus \(\mu_1,\mu_2,\mu_3,\mu_4\) are \(\sqrt2,0,0,-\sqrt2\). The interlacing intervals are:
| Index \(i\) | Parent positions \(i\) and \(i+2\) | Bound for \(\mu_i\) |
|---|---|---|
| 1 | \(\lambda_1=2,\ \lambda_3=1\) | \(2\ge\sqrt2\ge1\) |
| 2 | \(\lambda_2=1,\ \lambda_4=-1\) | \(1\ge0\ge-1\) |
| 3 | \(\lambda_3=1,\ \lambda_5=-1\) | \(1\ge0\ge-1\) |
| 4 | \(\lambda_4=-1,\ \lambda_6=-2\) | \(-1\ge-\sqrt2\ge-2\) |
Check: the eigenvalues of \(H\) sum to \(\sqrt2+0+0-\sqrt2=0\). Its two edges contribute four entries equal to \(1\) in \(\mathbf{A}(H)\), so the trace of \(\mathbf{A}(H)^2\) is \(4\). The squared eigenvalues sum to \((\sqrt2)^2+0^2+0^2+(-\sqrt2)^2=2+0+0+2=4\), as required.
Worked Example: A Star Induced in the Three-Dimensional Cube
Let \(G=Q_3\) have vertex set \(V(G)=\{000,001,010,011,100,101,110,111\}\), with two binary strings adjacent when they differ in exactly one position. Explicitly, its edge set is \(\{000,001\},\{000,010\},\{000,100\},\{001,011\},\{001,101\},\{010,011\},\{010,110\},\{100,101\},\{100,110\},\{011,111\},\{101,111\},\{110,111\}\).
Take \(S=\{000,001,010,100\}\). The induced subgraph has edge set \(\{\{000,001\},\{000,010\},\{000,100\}\}\), so it is a star with centre \(000\) and three leaves. The cube spectrum, obtained from the hypercube eigenvalues, is \(3\), \(1,1,1\), \(-1,-1,-1\), \(-3\). In ordered notation, \(n=8\), \(k=4\), and the parent values are \(\lambda_1=3,\lambda_2=\lambda_3=\lambda_4=1,\lambda_5=\lambda_6=\lambda_7=-1,\lambda_8=-3\).
For the star, an eigenvector with value \(a\) at the centre and the same value \(b\) at every leaf must satisfy \(\mu a=3b\) and \(\mu b=a\). These equations give \(\mu^2=3\), so the two eigenvalues from these vectors are \(\sqrt3\) and \(-\sqrt3\). The two independent leaf assignments whose values sum to zero, with value \(0\) at the centre, give eigenvalue \(0\) twice. Thus the ordered subgraph spectrum is \(\sqrt3,0,0,-\sqrt3\).
Since \(n-k=4\), the four interlacing intervals use pairs \((\lambda_1,\lambda_5)\), \((\lambda_2,\lambda_6)\), \((\lambda_3,\lambda_7)\), and \((\lambda_4,\lambda_8)\). They give \(3\ge\sqrt3\ge-1\), \(1\ge0\ge-1\), \(1\ge0\ge-1\), and \(1\ge-\sqrt3\ge-3\), respectively. This certifies every eigenvalue against its correct interval.
Check: the star has three edges, so the trace of the squared adjacency matrix is \(2\cdot3=6\), one contribution for each direction of each edge. Its eigenvalues have squared sum \((\sqrt3)^2+0^2+0^2+(-\sqrt3)^2=3+0+0+3=6\). The eigenvalues also sum to zero, matching the zero diagonal.
Common Pitfall: Sorting and Counting Positions
A frequent error is to sort the parent eigenvalues in increasing order but then apply the interlacing formula written for nonincreasing order. For the path example, this mistake would call \(-\sqrt3\) the first parent eigenvalue and might lead to the false claim that the largest subgraph eigenvalue \(1\) must be at most \(-\sqrt3\). The correction is to sort the parent spectrum as \(\sqrt3,1,0,-1,-\sqrt3\) before applying the formula. With \(n=5\), \(k=4\), and \(i=1\), the correct bound is \(\lambda_1\ge\mu_1\ge\lambda_2\), namely \(\sqrt3\ge1\ge1\).
Another related mistake is to remove repeated eigenvalues before counting positions. In the cube example, the parent spectrum has three copies of \(1\) and three copies of \(-1\). For \(i=2\), interlacing uses \(\lambda_2\) and \(\lambda_6\), both of which must be read from the full eight-entry list. Keeping multiplicities is essential: the theorem compares eigenvalues by index, not by rank among distinct values.
These calculations show why induced-subgraph structure and parent spectra work well together. The selected vertices determine the principal submatrix and the subgraph’s own eigenvalues; the parent graph supplies bounds indexed by the number of vertices omitted. Even when the subgraph spectrum is not calculated exactly, the same intervals can certify bounds on its ordered eigenvalues. To use them correctly, specify the induced vertex set, retain eigenvalue multiplicities, and check the indices \(i\) and \(i+n-k\) before drawing a conclusion.
Check Your Understanding
Use nonincreasing eigenvalue order throughout. In each problem, identify the parent indices used by interlacing.
- For the path with vertices \(\{1,2,3,4,5\}\) and edges \(\{12,23,34,45\}\), take the induced subgraph on \(\{1,2,3\}\). State the interlacing intervals for its three eigenvalues.
- For \(C_6\), take the induced subgraph on \(\{1,3,5\}\). What are its edges, and what bounds does interlacing give for its largest eigenvalue?
- Explain why the spectrum of \(Q_3\) must be listed with three copies each of \(1\) and \(-1\) when applying interlacing.
- A graph has ordered eigenvalues \(6,3,3,0,-2,-4\), and an induced subgraph has three vertices. Write the interlacing interval for its second-largest eigenvalue.
- In the cycle example, verify the ordering of the subgraph eigenvalues and explain why the isolated vertex contributes an eigenvalue \(0\).