MAXIMAL TRIANGLE-FREE GRAPHS WITH RESTRICTIONS ON THE DEGREES

We investigate the problem that at least how many edges must a maximal triangle-free graph on n vertices have if the maximal valency is less than or equal to D. Denote this minimum value by F(n, D). For large e nough n, we determine the exact value of F(n, D) if D greater than or equal to (n - 2)/2 and we prove that lim F(n, cn)/n = K(c) exists for all 0 < c with the possible exception of a sequence C-k -->, 0. The de termination of K(c) is a finite problem on all intervals [gamma, infin ity). For D = cn(8), 1/2 < epsilon < 1, we give upper and lower bounds for F(n, D) differing only in a constant factor. (Clearly, D < (n - 1 )(1/2) is impossible in a maximal triangle-free graph.) (C) 1994 John Wiley and Sons, Inc.