Every (2, r)-regular graph is regular

Abstract

A simple graph G is called (2, r)-regular if, for any pair of distinct vertices u and w in G, there are exactly r vertices of G adjacent to u or w (or both). In this note we apply a theorem of Ryser to prove that every (2, r)-regular graph of order n is in fact regular of degree d = [(2n -1) -√4(n - 1)(n - r) + 1]/2. Consequently, we find that the (2, r)-regular graphs are just a species of strongly regular graphs.