Editing Turán's theorem (section)

=== Other Forbidden Subgraphs ===
Turán's theorem shows that the largest number of edges in a <math>K_{r+1}</math>-free graph is <math>\left(1-\frac{1}{r}+o(1)\right) \frac{n^2}{2}</math>. The [[Erdős–Stone theorem]] finds the number of edges up to a <math>o(n^2)</math> error in all other graphs:<blockquote>(Erdős–Stone) Suppose <math>H</math> is a graph with [[chromatic number]] <math>\chi(H)</math>. The largest possible number of edges in a graph where <math>H</math> does not appear as a subgraph is<math display="block">\left(1-\frac{1}{\chi(H)-1}+o(1)\right) \frac{n^2}{2}</math>where the <math>o(1)</math> constant only depends on <math>H</math>. </blockquote>One can see that the Turán graph <math>T(n,\chi(H)-1)</math> cannot contain any copies of <math>H</math>, so the Turán graph establishes the lower bound. As a <math>K_{r+1}</math> has chromatic number <math>r+1</math>, Turán's theorem is the special case in which <math>H</math> is a <math>K_{r+1}</math>.

The general question of how many edges can be included in a graph without a copy of some <math>H</math> is the [[forbidden subgraph problem]].