Some Extremal Problems for Edge-Regular Graphs

We consider the class ER(n, d, lambda) of edge-regular graphs for some n > d > lambda, i.e., graphs regular of degree d on n vertices, with each pair of adjacent vertices having lambda common neighbors. It has previously been shown that for such graphs with lambda > 0 we have n >= 3(d - lambda) and much has been done to characterize such graphs when equality holds. Here we show that n >= 3(d - lambda) + 1 if lambda > 0 and d is odd and contribute to the characterization of the graphs in ER(n, d, lambda), lambda > 0, n = 3(d - lambda) + 1 by proving some lemmas about the structure of such graphs, and by classifying such graphs that satisfy a strong additional requirement, that the number t = t(u, v) of edges in the subgraph induced by the lambda common neighbors of any two adjacent vertices u and v is positive, and independent of u and v. The result is that there are exactly 4 such graphs: K-4 and 3 strongly regular graphs.