Characterization of a class of edge-regular graphs (Q1390367)

Let \(\Gamma= (V,E)\) be a finite unoriented simple graph. A flag of graph \(\Gamma\) is defined as a pair \((a,ab)\in V\times E\). E. Shult introduced strongly regular graphs in which, for arbitrary flag \((a,ab)\), there can be found a node \(c\) connected to \(a\) such that each node unconnected to \(a\) is exactly connected to one node of \(\{b,c\}\). The result of the present paper consists on the one hand in the fact that the requirement of the strong regularity can be weakened to that of edge regularity and on the other hand that the assumption that a node \(c\) must belong to a vicinity of \(a\) is removed. The corresponding theorem is formulated in such a way that there are given four assertions such that one of them is valid for an edge-regular graph \(\Gamma\) where, for an arbitrary flag \((a, ab)\), there is a node \(c\) such that every node from the anti-vicinity of \(a\) is connected with exactly one of the nodes \(b,c\). The proof is a very voluminous one. The author uses 19 lemmas.