Search

Let f(r) denote the smallest number of points in a non-bipartite r-regular graph of girth 4. It is known that f(r) ≥ 5r2 and that f(r) = 5r2 if r is even. It is proved that f(r) ∼ 5r2 and exact values for f(r) are provided for odd integers of the form r = 4n − 1. Tight bounds for f(r) for odd integers of the form r= 4n + 1 are given.

Triples ( p , n , r ) for which there exists an r -regular K n -free graph on p points are determined.