Abstract   Erdős et al. [6] asked for what values of  k  there is a sequence of graphs ( G   n  )  n   ∞  = 1 such that  G   n   has  n  vertices and independence number o( n ), contains no  K  4 , and no  k  + 1 vertices have the same degree. In [6] it is proved that such a  k  has to be at least 4, but the problem whether  any  such  k  exists is left open. By making use of some graphs constructed by Bollobas and Erdős [3], we shall prove that for  k  = 5 (and so for  k  ⩾ 5) there is such a sequence ( G   n  )  n   ∞  = 1.
['Béla Bollobás']
Degree multiplicities and independent sets in K 4 -free graphs