Abstract :
Let v, e and t denote the number of vertices, edges and triangles, respectively, of a K4-free graph. Fisher (1988) proved that t ⩽ (e/3)3/2, independently of v. His bound is attained when e = 3k2 for some integer k, but not in general. We find here, for any given value of e, the maximum possible value of t. Again, the maximum does not depend on v. We also show that certain ‘gaps’ occur in the set of triples (v, e, t) realizable by K4-free graphs.
