A structure theory for graphs with fixed smallest eigenvalue

In this paper, we will give a structure theory for graphs with fixed smallest eigenvalue. In order to do this, the concept of Hoffman graph (as introduced by Woo and Neumaier) is used. Our main result states that for fixed positive integer λ and any graph G with smallest eigenvalue at least −λ, there exist dense induced subgraphs Q 1 , … , Q c in G such that each vertex lies in at most λ Q i 's and almost all edges of G lie in at least one of the Q i 's.