En teoría de grafos , la malla de un grafo es la longitud del más corto de sus ciclos . Un gráfico acíclico se considera generalmente que tienen una malla infinito (o, para algunos autores, una malla de -1).
La malla de un gráfico es la longitud del más corto de sus ciclos .
El gráfico de Petersen tiene una malla de 5 y es una jaula.
El gráfico Heawood tiene una malla 6 y una jaula.
El Frucht Graph contiene triángulos, tiene una malla de 3.
Existen teoremas sobre la relación entre la malla y el número cromático de gráficos. Por ejemplo, un teorema de Paul Erdős publicado en 1959 da que para todo g y k , existe un gráfico con malla al menos gy número cromático al menos k . Por ejemplo, el gráfico de Grötzsch tiene una malla de 4 y un número cromático de 4. La demostración de este teorema usa el método probabilístico .