The Haemers regular upper bound, also called the Haemers upper bound, is an upper bound on the vertex count of a regular graph that occurs as a vertex-induced subgraph of another regular graph.
More generally, let be a regular graph of vertex degree
on
vertices, and let
be its least graph eigenvalue.
If a vertex-induced subgraph
on
vertices has average vertex
degree
, then
In particular, if is a regular graph of vertex degree
,
then its vertex count is at most
.
When , partitioning the vertex
set of
into
and
gives a
quotient matrix with nontrivial eigenvalue
.
Eigenvalue interlacing gives
,
which rearranges to the bound above (Haemers 1980, 1995). The case
gives equality directly. Equality in the unrounded bound
implies that
and the other vertex-induced subgraph
are both regular graphs.
For , the result reduces to the Hoffman
ratio bound for the independence number.
Cardoso et al. (2007) later obtained the same upper bound as an explicit extension
of the Hoffman ratio bound.
For strongly regular graphs, the regular adjacency bounds give an upper bound at least as strong as this one, and sometimes strictly stronger.