edges contains k disjoint triangles, with the exception of an (up to isomorphism) unique graph with n vertices and l edges. He states that a more complicated version of the proof can replace 400 k2 by Ck, where C is an absolute constant. The following further theorems are stated with brief hints for proof. Let G be a graph with n vertices. (1) If k \equiv n (mod 2) and every vertex has valency \geq 1/2 (n+k) and n \geq some n0(k), then G contains k disjoint triangles. (2) If n > ck, where c is a sufficiently large absolute constant, and G has 1/4 n2+k edges, then G contains k triangles no two of which have a common edge.
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag
|Books||Problems||Set Theory||Combinatorics||Extremal Probl/Ramsey Th.|
|Graph Theory||Add.Number Theory||Mult.Number Theory||Analysis||Geometry|
|Probabability||Personalia||About Paul Erdös||Publication Year||Home Page|