Metraipolis › archive › dc_8a0b133c4dfb

Turán's theorem — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T23:09:21.184Z
SHA-256 of the archived text
13fa23b70e863ea5c90a7c50c1fc1ed3c54b968b0403ca7266d26a868ba0e168
Stable URL of this page
https://metraipolis.com/documento/dc_8a0b133c4dfb

How to cite

Turán's theorem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8a0b133c4dfb (Metraipolis archive dc_8a0b133c4dfb, sha256 13fa23b70e863ea5c90a7c50c1fc1ed3c54b968b0403ca7266d26a868ba0e168)
BibTeX
@misc{dc8a0b133c4dfb,
  title = {Turán's theorem — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8a0b133c4dfb; sha256 13fa23b70e863ea5c90a7c50c1fc1ed3c54b968b0403ca7266d26a868ba0e168},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties, and is a special case of the forbidden subgraph problem on the maximum number of edges in a graph that does not have a given subgraph. An example of an n {\displaystyle n} -vertex graph that does not contain any ( r + 1 ) {\displaystyle (r+1)} -vertex clique K r + 1 {\displaystyle K_{r+1}} may be formed by partitioning the set of n {\displaystyle n} vertices into r {\displaystyle r} parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the Turán graph T ( n , r ) {\displaystyle T(n,r)} . Turán's theorem states that the Turán graph has the largest number of edges among all Kr+1-free n-vertex graphs. Turán's theorem, and the Turán graphs giving its extreme case, were first described and studied by Hungarian mathematician Pál Turán in 1941. The special case of the theorem for triangle-free graphs is known as Mantel's theorem; it was stated in 1907 by Willem Mantel, a Dutch mathematician.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Turán's theorem» — https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem
Wikidata Q1047749: «theorem bounding the number of edges in a graph that has no large cliques» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1047749
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1373581004, consultata il 2026-10-07T22:47:33.188Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 70353a2681fe005f93f9a28144b53870b4085613b6df5c9e715d5625e68552c8