Sabotaging Mantel's Theorem
Abstract
One of the earliest results in extremal graph theory, Mantel's theorem, states that the maximum number of edges in a triangle-free graph $G$ on $n$ vertices is $\lfloor n^2/4 \rfloor$. We investigate how this extremal bound is affected when $G$ is additionally required to contain a prescribed graph $H$ as a subgraph. We establish general upper and lower bounds for this problem, which are tight in the exponent for random triangle-free graphs and graphs generated by the triangle-free process, when the size of $H$ lies within certain ranges.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Combinatorial Mathematics
Advanced Graph Theory Research
Publication details
- Journal / source
- The Electronic Journal of Combinatorics
- Volume
- 33
- Issue
- 1
- Publication date
- 26 February 2026
- Language
- EN