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 \geq 3(d – \lambda)\) and much has been done to characterize such graphs when equality holds.
Here we show that \(n \geq 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.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.