Haemers Regular Upper Bound

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.