Graph Theory
- To: mathgroup at yoda.physics.unc.edu
- Subject: Graph Theory
- From: puglisi at settimo.italtel.it
- Date: Thu, 7 Oct 93 18:00:17 MDT
Milan, 7 Oct. 93
Hi, I am reading a book on "Graph Theory" by Harary.
I am interested in the "Turan" theorem which state that
the maximum number of edges a graph with p points can have
without containing a complete subgraph of n vertices (i.e. Kn)
is given by the formula: ( page 18)
(n-2)(p^2 - r^2)
ex(p,Kn) = ---------------- + Binomial[r,2] with (n<=p)
2(n-1)
where p = r mod(n-1) and (0<= r <n-1)
Now "p" is at most equal to n-2 which seems to contradict the entire formula.
Can anybody help me understand if there is a typo error or something else?
Thanks Anyway
Alberto Puglisi
Italtel R&D
Milan, Italy Internet: puglisi at settimo.italtel.it