Turán's theorem
E750082
Turán's theorem is a fundamental result in extremal graph theory that determines the maximum number of edges a graph can have without containing a complete subgraph of a given size.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
result in extremal graph theory
ⓘ
theorem ⓘ |
| appearsIn |
combinatorics textbooks
ⓘ
introductory extremal graph theory courses ⓘ |
| assumes |
no loops
ⓘ
no multiple edges ⓘ |
| characterizes | extremal graphs without K_r ⓘ |
| dealsWith |
cliques
ⓘ
complete graphs ⓘ edge density ⓘ simple finite graphs ⓘ |
| edgeCountFormula | floor(((r-2)/(2(r-1))) * n^2) ⓘ |
| edgeCountType | exact formula ⓘ |
| extremalGraph | Turán graph T_{r-1}(n) NERFINISHED ⓘ |
| extremalGraphProperty |
complete (r-1)-partite graph
ⓘ
parts as equal in size as possible ⓘ |
| field |
extremal graph theory
NERFINISHED
ⓘ
graph theory ⓘ |
| forbidsSubgraph | complete graph K_r ⓘ |
| generalizes | Mantel's theorem NERFINISHED ⓘ |
| gives | exact extremal number ex(n, K_r) ⓘ |
| graphType | undirected graphs ⓘ |
| hasConsequence | stability results for near-extremal graphs ⓘ |
| hasExtension |
Turán-type theorems for hypergraphs
NERFINISHED
ⓘ
stability versions of Turán's theorem ⓘ weighted versions of Turán's theorem ⓘ |
| implies | upper bounds on edge density avoiding K_r ⓘ |
| importance |
fundamental result in extremal graph theory
ⓘ
prototype of many extremal problems ⓘ |
| mainTopic | maximum number of edges in graphs without a given complete subgraph ⓘ |
| namedAfter | Pál Turán NERFINISHED ⓘ |
| originalAuthor | Pál Turán NERFINISHED ⓘ |
| originalPublicationLanguage | Hungarian NERFINISHED ⓘ |
| parameterizedBy |
clique size r
ⓘ
number of vertices n ⓘ |
| proofMethod |
averaging arguments
ⓘ
induction on the number of vertices ⓘ symmetrization ⓘ |
| relatedTo |
Erdős–Stone theorem
NERFINISHED
ⓘ
Mantel's theorem NERFINISHED ⓘ Zarankiewicz problem NERFINISHED ⓘ |
| specialCaseOf | extremal graph theory results ⓘ |
| statementInformal | Among all n-vertex graphs with no K_r subgraph, the Turán graph T_{r-1}(n) has the maximum number of edges ⓘ |
| usedIn |
Ramsey theory
NERFINISHED
ⓘ
bounding chromatic number via forbidden cliques ⓘ design of extremal constructions ⓘ probabilistic method in combinatorics ⓘ |
| yearProved | 1941 ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.