Vertex Deletion and Interlacing Calculations

From Vertex Deletion to a Smaller Matrix

Deleting a vertex changes a graph locally, but it can change every eigenvalue of its adjacency matrix. Cauchy interlacing gives a precise comparison: each eigenvalue of the smaller graph lies between two consecutive eigenvalues of the original graph. We will apply that result to paths, cycles and complete graphs, keeping track of the actual spectra as well as the inequalities.

All graphs in this tutorial are finite and simple. For a graph $G=(V,E)$, its adjacency matrix $\mathbf{A}(G)$ has entry $1$ in positions $u,v$ when $uv\in E$, and entry $0$ otherwise. Its eigenvalues are real because $\mathbf{A}(G)$ is symmetric. We list them in nonincreasing order, including multiplicities, as $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$.

Definition: For a vertex $v\in V(G)$, the graph $G-v$ is obtained by deleting $v$ and every edge incident with $v$. It is the induced subgraph on $V(G)\setminus\{v\}$. The adjacency eigenvalues of $G-v$, listed in nonincreasing order and with multiplicities, are denoted $\mu_1\ge\cdots\ge\mu_{n-1}$.

To see the matrix connection, order the vertices of $G$ so that $v$ is last. Removing the last row and column of $\mathbf{A}(G)$ leaves exactly $\mathbf{A}(G-v)$. Such a matrix is called a principal submatrix. The eigenvalue comparison below is therefore a special case of Cauchy interlacing for induced subgraphs.

The Vertex-Deletion Interlacing Theorem

Theorem (Cauchy interlacing for vertex deletion): Let $G$ be a graph of order $n\ge2$, and let $G-v$ be obtained by deleting one vertex. With eigenvalues ordered as above, $$ \lambda_i\ge\mu_i\ge\lambda_{i+1} \qquad (1\le i\le n-1). $$

Proof. Reorder the vertices so that $v$ is last, and let $A=\mathbf{A}(G)$ and $B=\mathbf{A}(G-v)$. Regard $B$ as the restriction of the quadratic form $x^{T}Ax$ to the coordinate subspace $H$ consisting of vectors whose last coordinate is zero. The subspace $H$ has dimension $n-1$.

For a real symmetric matrix with eigenvalues $\theta_1\ge\cdots\ge\theta_r$, the variational characterization of its $i$-th eigenvalue is $$ \theta_i=\max_{\dim U=i}\ \min_{\substack{x\in U\\ \|x\|=1}}x^{T}Mx. $$ This identity follows from an orthonormal eigenbasis: the span of the first $i$ eigenvectors has every unit-vector quotient at least $\theta_i$, while every $i$-dimensional subspace intersects the span of eigenvectors $i,i+1,\ldots,r$ in a nonzero vector, whose quotient is at most $\theta_i$.

For $B$, the same characterization maximizes over $i$-dimensional subspaces $U$ restricted to $H$. Since these are also subspaces available in the maximization for $A$, we get $\mu_i\le\lambda_i$. For the other inequality, take the span $S$ of eigenvectors of $A$ for $\lambda_1,\ldots,\lambda_{i+1}$. Its dimension is $i+1$. Since $H$ has dimension $n-1$, the dimension formula gives $\dim(S\cap H)\ge i$. Choose an $i$-dimensional subspace $U$ of $S\cap H$. Every unit vector $x\in U$ has $x^{T}Ax\ge\lambda_{i+1}$, because $x$ is a linear combination of eigenvectors with eigenvalues at least $\lambda_{i+1}$. The variational characterization applied to $B$ now gives $\mu_i\ge\lambda_{i+1}$. Together the inequalities prove the theorem. $\square$

Proposition: If the vertices of $G$ are ordered with $v$ last, then the principal submatrix obtained by removing the last row and column of $\mathbf{A}(G)$ is $\mathbf{A}(G-v)$.

Proof. Each entry of the remaining matrix records whether a pair of vertices other than $v$ is adjacent in $G$. Deleting $v$ removes no edges between those remaining vertices, so that entry is also exactly the corresponding entry of $\mathbf{A}(G-v)$. This holds for every pair of remaining vertices, hence the matrices agree. $\square$

Interlacing gives bounds, not usually the exact smaller spectrum by itself. The examples below calculate both spectra independently and then check every interlacing inequality.

Worked Example: Deleting the Middle Vertex of a Path

Let $G=P_5$, with $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{12,23,34,45\}$. Delete vertex $3$. The remaining graph has vertices $\{1,2,4,5\}$ and edges $\{12,45\}$, so it consists of two disjoint copies of $P_2$.

For the original path, let $p_k(x)$ be the characteristic polynomial of $P_k$. Expanding the determinant of the path’s tridiagonal adjacency matrix along its last row gives $p_k(x)=xp_{k-1}(x)-p_{k-2}(x)$, with $p_0(x)=1$ and $p_1(x)=x$. Thus $p_2=x^2-1$, $p_3=x^3-2x$, $p_4=x^4-3x^2+1$, and $$ p_5=xp_4-p_3=x(x^4-3x^2+1)-(x^3-2x)=x^5-4x^3+3x=x(x^2-1)(x^2-3). $$ The roots give the ordered spectrum $\lambda=(\sqrt{3},1,0,-1,-\sqrt{3})$.

The adjacency matrix of each $P_2$ is $\begin{pmatrix}0&1\\1&0\end{pmatrix}$, whose characteristic polynomial is $x^2-1$. The two disjoint components therefore give the spectrum $\mu=(1,1,-1,-1)$. Interlacing, checked index by index, is $$ \sqrt{3}\ge1\ge1,\qquad 1\ge1\ge0,\qquad 0\ge-1\ge-1,\qquad -1\ge-1\ge-\sqrt{3}. $$ Each inequality holds. As an independent check of the smaller spectrum, its characteristic polynomial is $(x^2-1)^2$, whose roots are $1,1,-1,-1$.

Worked Example: Deleting a Vertex from a Cycle

Let $G=C_6$, with $V(G)=\{1,2,3,4,5,6\}$ and $E(G)=\{12,23,34,45,56,61\}$. Delete vertex $1$. The remaining vertices are $\{2,3,4,5,6\}$, and the remaining edges are $\{23,34,45,56\}$; thus $G-1=P_5$.

The eigenvalues of $C_6$ are $2\cos(2\pi j/6)$ for $j=0,1,2,3,4,5$. Substitution gives $2$, $2\cos(\pi/3)=1$, $2\cos(2\pi/3)=-1$, $2\cos(\pi)=-2$, $2\cos(4\pi/3)=-1$, and $2\cos(5\pi/3)=1$. In nonincreasing order, $\lambda=(2,1,1,-1,-1,-2)$. From the path calculation, the ordered spectrum of $P_5$ is $\mu=(\sqrt{3},1,0,-1,-\sqrt{3})$.

For the five indices, the interlacing checks are $2\ge\sqrt{3}\ge1$, $1\ge1\ge1$, $1\ge0\ge-1$, $-1\ge-1\ge-1$, and $-1\ge-\sqrt{3}\ge-2$. All hold. As an independent check, deleting a vertex from a cycle leaves precisely the chain of the other five vertices, with four consecutive edges and no edge joining its endpoints; that is $P_5$, whose spectrum was calculated from its characteristic polynomial.

Worked Example: Deleting a Vertex from a Complete Graph

Let $G=K_5$, with $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{12,13,14,15,23,24,25,34,35,45\}$. Delete vertex $5$. The remaining graph has vertices $\{1,2,3,4\}$ and edges $\{12,13,14,23,24,34\}$, so it is $K_4$.

For any $K_r$, its adjacency matrix is $J-I$, where $J$ is the $r$-by-$r$ all-ones matrix and $I$ is the identity matrix. The all-ones vector is an eigenvector of $J-I$ with eigenvalue $r-1$. Every vector whose coordinates sum to zero is sent to its negative, so it has eigenvalue $-1$. These subspaces have dimensions $1$ and $r-1$, respectively, and together account for all $r$ eigenvalues.

Consequently, $K_5$ has ordered spectrum $\lambda=(4,-1,-1,-1,-1)$, and $K_4$ has ordered spectrum $\mu=(3,-1,-1,-1)$. The checks are $4\ge3\ge-1$, $-1\ge-1\ge-1$, $-1\ge-1\ge-1$, and $-1\ge-1\ge-1$. As an independent check, $K_4$ has eigenvalue $3$ on its all-ones vector and eigenvalue $-1$ on the three-dimensional space of vectors with coordinate sum zero, giving exactly the four listed eigenvalues.

What the Comparisons Do—and Do Not—Say

The path example illustrates that deleting one vertex can split a connected graph into separate components. The cycle example shows that deleting a vertex can break a cycle into a path. The complete-graph example shows that deletion can change the largest eigenvalue while preserving the repeated eigenvalue $-1$. In each case, interlacing constrains where the smaller eigenvalues can lie, but the graph’s structure is needed to calculate them exactly.

A common mistake is to assume that deleting one vertex simply removes one eigenvalue. For $K_5$, that mistaken calculation would remove one of the $-1$ eigenvalues from $(4,-1,-1,-1,-1)$, giving $(4,-1,-1,-1)$ for $K_4$. But the sum of the eigenvalues of an adjacency matrix equals its trace, which is zero because a simple graph has no loops. The mistaken list sums to $4-1-1-1=1$, so it cannot be the spectrum of $K_4$. The correct spectrum is $(3,-1,-1,-1)$, as the direct calculation confirms. Interlacing compares eigenvalues in order; it does not identify the smaller spectrum by deleting an entry from the larger list.

The theorem requires $n\ge2$ so that the smaller matrix has eigenvalues to compare. If $n=1$, deleting the sole vertex leaves the empty graph, whose adjacency matrix has no eigenvalues; there are no inequalities of the stated form to check. For $n\ge2$, repeated eigenvalues cause no exception: eigenvalues are listed with multiplicity, and the inequalities apply at every index.

Check Your Understanding

Use the eigenvalues in nonincreasing order, counting multiplicities.

Let $G=P_4$, with vertices $\{1,2,3,4\}$ and edges $\{12,23,34\}$. What graph results from deleting vertex $2$, and what are its eigenvalues?
For $C_5$, deleting vertex $1$ leaves which path? Use interlacing to state the inequalities that compare their ordered eigenvalues.
Explain why the adjacency matrix of $G-v$ is a principal submatrix of the adjacency matrix of $G$.
For $K_6$, state the spectrum of $K_6$ and of the graph left after deleting one vertex, then check the interlacing inequalities.
Why does the eigenvalue list of a vertex-deleted graph generally not come from simply removing one entry from the original list?

Vertex Deletion and Interlacing Calculations

What You'll Learn