We study the connected regular graphs with four distinct eigenvalues. Properties and feasibility conditions of the eigenvalues are found. Several examples, constructions and characterizations are given, as well as some uniqueness and nonexistence results.

We give a bound on the sizes of two sets of vertices at a given minimum distance (a separated pair of subgraphs) in a graph in terms of polynomials and the spectrum of the graph. We find properties of the polynomial optimizing the bound. Explicit bounds on the number of vertices at maximal...