  We give some existence/nonexistence statements on universal graphs, which
under GCH give a necessary and sufficient condition for the existence of a
universal graph of size lambda with no K(kappa), namely, if either kappa is
finite or cf(kappa)>cf(lambda). (Here K(kappa) denotes the complete graph on
kappa vertices.) The special case when lambda^{< kappa}= lambda was first
proved by F. Galvin. Next, we investigate the question that if there is no
universal K(kappa)-free graph of size lambda then how many of these graphs
embed all the other. It was known, that if lambda^{< lambda}= lambda (e.g., if
lambda is regular and the GCH holds below lambda), and kappa = omega, then this
number is lambda^+. We show that this holds for every kappa <= lambda of
countable cofinality. On the other hand, even for kappa = omega_1, and any
regular lambda >= omega_1 it is consistent that the GCH holds below lambda,
2^{lambda} is as large as we wish, and the above number is either lambda^+ or
2^{lambda}, so both extremes can actually occur.

Logic