Editing Turán graph (section)

==Turán's theorem==
{{Main|Turán's theorem}}
Turán graphs are named after [[Pál Turán]], who used them to prove Turán's theorem, an important result in [[extremal graph theory]].

By the pigeonhole principle, every set of ''r''&nbsp;+&nbsp;1 vertices in the Turán graph includes two vertices in the same partition subset; therefore, the Turán graph does not contain a [[Clique (graph theory)|clique]] of size&nbsp;''r''&nbsp;+&nbsp;1. According to Turán's theorem, the Turán graph has the maximum possible number of edges among all (''r''&nbsp;+&nbsp;1)-clique-free graphs with ''n''&nbsp;vertices. {{harvtxt|Keevash|Sudakov|2003}} show that the Turán graph is also the only (''r''&nbsp;+&nbsp;1)-clique-free graph of order ''n'' in which every subset of &alpha;''n'' vertices spans at least <math>\frac{r\,{-}\,1}{3r}(2\alpha -1)n^2</math> edges, if α is sufficiently close to 1.{{sfnp|Keevash|Sudakov|2003}} The [[Erdős–Stone theorem]] extends Turán's theorem by bounding the number of edges in a graph that does not have a fixed Turán graph as a subgraph. Via this theorem, similar bounds in extremal graph theory can be proven for any excluded subgraph, depending on the [[chromatic number]] of the subgraph.