.. _sphx_glr_api_gallery_graph_theory_extremal:

Extremal graph theory
---------------------

Turán's theorem: the most edges a graph can have without a large
clique.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Builds the Turán graph T(n, r), checks that it has no clique of size r + 1, and shows that adding any missing edge creates one. For r = 2 this is Mantel&#x27;s theorem: a triangle-free graph on n vertices has at most n^2/4 edges.">

.. only:: html

  .. image:: /api/gallery/graph_theory/extremal/images/thumb/sphx_glr_plot_01_turan_theorem_thumb.png
    :alt:

  :doc:`/api/gallery/graph_theory/extremal/plot_01_turan_theorem`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Turán's theorem: the densest clique-free graphs</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/graph_theory/extremal/plot_01_turan_theorem