title: Théorème de Turán
text: # Théorème de Turán
  
  Le théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán.
  
  Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán.
  
  Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses $preuves^,.$
  
  ## Le théorème
  
  Tout graphe G ayant n sommets, et ne contenant pas de clique de taille plus grande que r (i.e. $K_{r+1}$ -free) possède au plus le nombre suivant d'arêtes :
  
      ${\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}.$
  
  Cette borne est atteinte par le graphe de Turán T(n,r).
  
  ## Théorème de Mantel
  
  Le cas particulier r = 2, correspond au théorème de Mantel :
  
     Le nombre maximal d'arêtes dans un graphe sans triangle est $\lfloor n^{2}/4\rfloor .$
  