Hoffman Bound for Independent Sets

The Bound and Its Hypotheses

An independent set is a set of vertices containing no adjacent pair. Its largest possible size can be difficult to determine by direct search. For a regular graph, the least eigenvalue of the adjacency matrix gives a useful upper bound: it translates the condition of having no edges inside the set into a quadratic-form constraint.

Throughout, graphs are finite and simple, and the graph has order $n\geq 1$. A set $S\subseteq V(G)$ is independent if no edge has both endpoints in $S$. The independence number $\alpha(G)$ is the maximum size of an independent set. The graph is $r$-regular if every vertex has degree $r$. We use the adjacency matrix $\mathbf A(G)$, whose $uv$ entry is $1$ when $u$ and $v$ are adjacent and $0$ otherwise.

Theorem (Hoffman bound for independent sets): Let $G$ be an $r$-regular graph on $n\geq1$ vertices, with $r>0$, and let $s$ be the least eigenvalue of $\mathbf A(G)$. Then $$ \alpha(G)\leq \frac{n(-s)}{r-s}. $$ For an independent set $S$, equality $|S|=n(-s)/(r-s)$ holds if and only if its indicator vector, after subtracting its mean, is an eigenvector of $\mathbf A(G)$ with eigenvalue $s$.

The assumption $r>0$ matters: for an edgeless graph, $r=s=0$, so the displayed quotient is undefined, while $\alpha(G)=n$. In the theorem's setting $s<0$, as shown below, and therefore the denominator $r-s$ is positive. The vector characterization also specifies exactly what “equality” means; since $|S|$ is an integer, the numerical bound need not be attained.

Why the Bound Holds

Write $\mathbf 1$ for the all-ones vector and $\mathbf x$ for the indicator vector of an independent set $S$: its $v$-coordinate is $1$ for $v\in S$ and $0$ otherwise. Put $a=|S|$. Regularity gives $\mathbf A(G)\mathbf 1=r\mathbf 1$. Also, $\mathbf x^{T}\mathbf A(G)\mathbf x=0$: this quadratic form counts ordered adjacent pairs of vertices in $S$, and there are none.

Separate the constant part of $\mathbf x$ from the part perpendicular to $\mathbf 1$:

\mathbf x=\frac{a}{n}\mathbf 1+\mathbf y,\qquad \mathbf y^{T}\mathbf 1=0.

The earlier material on Rayleigh quotients and least eigenvalues gives the spectral inequality $\mathbf y^{T}\mathbf A(G)\mathbf y\geq s\,\mathbf y^{T}\mathbf y$. It applies because $\mathbf y$ is perpendicular to $\mathbf 1$ and, in fact, the least-eigenvalue inequality holds for every vector. Expanding the quadratic form, the mixed terms vanish: $\mathbf 1^{T}\mathbf A(G)\mathbf y=r\mathbf 1^{T}\mathbf y=0$. Further, $\mathbf x^{T}\mathbf x=a$, so $\mathbf y^{T}\mathbf y=a-a^{2}/n$. Consequently,

0=\mathbf x^{T}\mathbf A(G)\mathbf x =\frac{r a^{2}}{n}+\mathbf y^{T}\mathbf A(G)\mathbf y \geq \frac{r a^{2}}{n}+s\left(a-\frac{a^{2}}{n}\right) =a\left(s+\frac{(r-s)a}{n}\right).

If $a=0$, the claimed upper bound holds because its right side is positive. If $a>0$, divide by $a$, then rearrange; $r-s>0$, so dividing by it preserves the inequality:

s+\frac{(r-s)a}{n}\leq0 \quad\Longrightarrow\quad a\leq\frac{n(-s)}{r-s}.

For the equality condition, suppose first that $a=n(-s)/(r-s)$. The final expression $a(s+(r-s)a/n)$ is then zero. The chain above starts and ends at zero, so $\mathbf y^{T}\mathbf A(G)\mathbf y=s\,\mathbf y^{T}\mathbf y$. By the spectral theorem, equality in the least-eigenvalue quadratic-form inequality holds exactly when $\mathbf y$ lies in the eigenspace for $s$ (including the zero vector). Conversely, if $\mathbf A(G)\mathbf y=s\mathbf y$, then the expansion gives $0=r a^{2}/n+s(a-a^{2}/n)=a(s+(r-s)a/n)$. If $a=0$, the vector $\mathbf y=0$ cannot be an eigenvector with eigenvalue $s<0$ unless interpreted trivially, but the claimed numerical equality does not hold because the bound is positive. Thus in this converse we consider a nonempty set, as equality with the positive bound requires. Dividing by $a>0$ gives $a=n(-s)/(r-s)$. This proves both directions. $\square$

To justify the sign used here, $r$ is an eigenvalue because $\mathbf A(G)\mathbf 1=r\mathbf 1$. The sum of the eigenvalues is the trace of $\mathbf A(G)$, which is $0$ because the graph has no loops. Since $r>0$, the eigenvalues cannot all be nonnegative: their sum would then be positive. Thus the least eigenvalue satisfies $s<0$.

Worked Examples

Worked Example: The Four-Cycle Attains the Bound

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,41\}$. It is 2-regular, so $n=4$ and $r=2$. To identify its least eigenvalue, take the four independent vectors $(1,1,1,1)$, $(1,-1,1,-1)$, $(1,0,-1,0)$, and $(0,1,0,-1)$. Multiplication by the adjacency matrix sends these respectively to $2$ times the first, $-2$ times the second, and zero times each of the last two. They form a basis, so the eigenvalues are $2,-2,0,0$, and $s=-2$.

Substituting these values into the bound gives $\alpha(G)\leq 4(-(-2))/(2-(-2))=8/4=2$. The set $S=\{1,3\}$ is independent, so $\alpha(G)\geq2$, and hence $\alpha(G)=2$. For its indicator vector $\mathbf x=(1,0,1,0)$, the mean part is $(1/2)\mathbf 1$, giving $\mathbf y=(1/2,-1/2,1/2,-1/2)$. The eigenvector calculation above gives $\mathbf A(G)\mathbf y=-2\mathbf y$, verifying the equality condition.

Check: each vertex has exactly two neighbors, and the edges $12,23,34,41$ all have at most one endpoint in $\{1,3\}$. The calculated independent-set size and the bound are both $2$.

Worked Example: A Complete Graph Attains the Bound

Let $G=K_4$, with $V=\{1,2,3,4\}$ and $E=\{12,13,14,23,24,34\}$. Every vertex is adjacent to the other three, so $r=3$ and $n=4$. Its adjacency matrix is $J-I$, where $J$ is the all-ones matrix and $I$ is the identity matrix. On $\mathbf 1$, $J-I$ acts by $4-1=3$. On any vector perpendicular to $\mathbf 1$, $J$ acts as zero, so $J-I$ acts by $-1$. Thus $s=-1$.

The bound is $\alpha(G)\leq4(-(-1))/(3-(-1))=4/4=1$. Every pair of distinct vertices is an edge, so an independent set has at most one vertex; each singleton is independent. Therefore $\alpha(G)=1$. For example, if $S=\{1\}$, then $\mathbf y=(3/4,-1/4,-1/4,-1/4)$, which is perpendicular to $\mathbf 1$. The calculation for vectors perpendicular to $\mathbf 1$ gives $\mathbf A(G)\mathbf y=-\mathbf y$, as required for equality.

Check: the graph has six edges and degree three at each of four vertices, so the degree sum is $4\cdot3=12=2\cdot6$. The bound and the directly determined independence number are both $1$.

Worked Example: The Five-Cycle Does Not Attain the Bound

Let $G$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51\}$. It is 2-regular, with $n=5$ and $r=2$. The cycle spectrum, computed in the earlier material on cycle eigenvalues, is $2\cos(2\pi k/5)$ for $k=0,1,2,3,4$. The least value is $s=2\cos(4\pi/5)=-(1+\sqrt5)/2$.

Substitute this value into the bound: \[ \alpha(G)\leq \frac{5(1+\sqrt5)/2}{2+(1+\sqrt5)/2} =\frac{5(1+\sqrt5)}{5+\sqrt5} =\sqrt5. \] For the last equality, multiplying the fraction by $(5-\sqrt5)/(5-\sqrt5)$ gives numerator $5(1+\sqrt5)(5-\sqrt5)=20\sqrt5$ and denominator $25-5=20$.

The set $\{1,3\}$ is independent. No three vertices can be independent: around the 5-cycle, each selected vertex would need at least one unselected vertex between it and the next selected vertex, requiring at least as many unselected vertices as selected ones. Three selected vertices would therefore require at least six vertices. Hence $\alpha(G)=2$. Since $2<\sqrt5$, the bound is not attained; the theorem does not assert that every graph has an independent set whose size equals the real-valued bound.

Check: the five listed edges give degree two at every vertex. Also, $\sqrt5>2$ because $5>4$, consistent with the strict comparison between the actual independence number and the bound.

Interpreting Equality and Avoiding Errors

The equality criterion is more informative than the numerical inequality alone. It says that a tight independent set must have a centered indicator vector entirely in the least-eigenvalue eigenspace. If the least eigenvalue has a multidimensional eigenspace, the condition is membership in that whole space, not alignment with one particular eigenvector. Conversely, a set is still required to be independent: the eigenvector condition is an equality test for an independent set, not a standalone method for declaring an arbitrary vertex set independent.

The bound can be useful even when it is not sharp. It gives a certificate that no independent set can exceed the stated size, without requiring a search through all vertex subsets. Since $\alpha(G)$ is an integer, a nonintegral bound can be rounded down when reporting an integer upper bound. For example, the five-cycle calculation yields $\alpha(G)\leq\sqrt5$, which implies $\alpha(G)\leq2$, because $\alpha(G)$ is an integer and $\sqrt5<3$.

Common pitfall: losing the minus sign. In $K_4$, the least eigenvalue is $s=-1$. Incorrectly replacing $-s$ by $s$ gives $4(-1)/(3-(-1))=-1$, an impossible negative upper bound for an independence number. The correct numerator is $-s=1$, and the bound is $4(1)/(3+1)=1$. Another error is to infer equality from the formula alone: the bound is an upper bound, and equality requires the centered indicator vector to lie in the least-eigenvalue eigenspace.

Check Your Understanding

Use the theorem and its equality condition to answer the following.

Why is the assumption $r>0$ needed for the displayed quotient, and what is $\alpha(G)$ when $G$ is edgeless on $n\geq1$ vertices?
For an independent set of size $a$, explain why its indicator vector satisfies $\mathbf x^{T}\mathbf A(G)\mathbf x=0$.
In a 3-regular graph on 8 vertices with least eigenvalue $-1$, calculate the Hoffman bound.
State the necessary and sufficient eigenspace condition for an independent set to attain the bound.
Why does an upper bound of $\sqrt5$ on an integer-valued independence number imply an upper bound of $2$?

Hoffman Bound for Independent Sets

What You'll Learn