.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/graph_theory/extremal/plot_01_turan_theorem.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_graph_theory_extremal_plot_01_turan_theorem.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_graph_theory_extremal_plot_01_turan_theorem.py:


Turán's theorem: the densest clique-free graphs
=====================================================

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's theorem: a triangle-free graph on n vertices has at
most n^2/4 edges.

.. GENERATED FROM PYTHON SOURCE LINES 12-16

.. code-block:: Python

    import matplotlib.pyplot as plt

    from mathematicskit.graph_theory import clique_number, random_graph, turan_graph, turan_number








.. GENERATED FROM PYTHON SOURCE LINES 17-19

Turán graphs
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 19-24

.. code-block:: Python


    for n, r in [(8, 2), (9, 3), (12, 4)]:
        g = turan_graph(n, r)
        print(f"T({n}, {r}): {len(g.edges())} edges = turan_number {turan_number(n, r)}, largest clique {clique_number(g)}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    T(8, 2): 16 edges = turan_number 16, largest clique 2
    T(9, 3): 27 edges = turan_number 27, largest clique 3
    T(12, 4): 54 edges = turan_number 54, largest clique 4




.. GENERATED FROM PYTHON SOURCE LINES 25-27

Random graphs above the Turán number contain big cliques
-----------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 27-42

.. code-block:: Python


    n, r = 12, 3
    counts, cliques = [], []
    for seed in range(300):
        g = random_graph(n, 0.55, seed=seed)
        counts.append(len(g.edges()))
        cliques.append(clique_number(g))

    fig, ax = plt.subplots()
    ax.scatter(counts, cliques, alpha=0.4)
    ax.axvline(turan_number(n, r), color="tab:red", ls="--", label=f"Turán number t({n}, {r}) = {turan_number(n, r)}")
    ax.set_xlabel("edges")
    ax.set_ylabel("clique number")
    ax.legend()
    ax.set_title("Every graph right of the line has a clique of size 4")



.. image-sg:: /api/gallery/graph_theory/extremal/images/sphx_glr_plot_01_turan_theorem_001.png
   :alt: Every graph right of the line has a clique of size 4
   :srcset: /api/gallery/graph_theory/extremal/images/sphx_glr_plot_01_turan_theorem_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none


    Text(0.5, 1.0, 'Every graph right of the line has a clique of size 4')




.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.045 seconds)


.. _sphx_glr_download_api_gallery_graph_theory_extremal_plot_01_turan_theorem.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_turan_theorem.ipynb <plot_01_turan_theorem.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_turan_theorem.py <plot_01_turan_theorem.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_turan_theorem.zip <plot_01_turan_theorem.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_