Maille (théorie des graphes)
# Maille (théorie des graphes)

En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de −1).

## Définition

La maille d'un graphe est la longueur du plus court de ses cycles.

## Exemples

* Le graphe de Petersen a une maille de 5 et est une cage.
* Le graphe de Heawood a une maille de 6 et est une cage.
* Le Graphe de Frucht contient des triangles, il a une maille de 3.

## Familles associées

* Une (r,g)-cage est un graphe régulier de degré r et de maille g minimal en nombre de sommets.
* Les graphes de maille supérieure ou égale à quatre sont les graphes sans triangle.

## Lien avec la coloration

Il existe des théorèmes à propos du rapport entre la maille et le nombre chromatique des graphes. Par exemple, un théorème de Paul Erdős publié en $1959^,$ donne que pour tout g et k, il existe un graphe de maille au moins g et de nombre chromatique au moins k. Par exemple, le graphe de Grötzsch a une maille de 4 et un nombre chromatique de 4. La preuve de ce théorème utilise la méthode probabiliste.

