Let t and n be
positive integers with t at least equal to 2, and n greater than
or equal to t. The maximum number of
edges of a
graph of order n that doesn't
contain a complete
subgraph of order t is
(n) - sigma {i = 1, t - 1} (n
i)
(2) (2)
where the n
i form a
partition of n into t-1 parts which are as equal
as possible.
Furthermore, the complete (t-1)-partite
graph with parts of size n1,n2,...nt-1
is the only
graph whose number of
edges is equal to the
bound above but
still doesn't contain a complete
subgraph of order t.
--back to
combinatorics--