Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655519 | Journal of Combinatorial Theory, Series A | 2013 | 11 Pages |
Abstract
Using the formalism of flag algebras, we prove that every triangle-free graph G with n vertices contains at most (n/5)5 cycles of length five. Moreover, the equality is attained only when n is divisible by five and G is the balanced blow-up of the pentagon. We also compute the maximal number of pentagons and characterize extremal graphs in the non-divisible case provided n is sufficiently large. This settles a conjecture made by Erdős in 1984.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics