Na teoria dos grafos , a malha de um gráfico é o comprimento do mais curto de seus ciclos . Um gráfico acíclico é geralmente considerado como tendo uma malha infinita (ou, para alguns autores, uma malha de -1).
A malha de um gráfico é o comprimento do mais curto de seus ciclos .
O gráfico de Petersen tem uma malha de 5 e é uma gaiola.
O gráfico Heawood tem uma malha 6 e uma gaiola.
O Gráfico de Frucht contém triângulos, ele tem uma malha de 3.
Existem teoremas sobre a relação entre a malha e o número cromático de gráficos. Por exemplo, um teorema por Paul Erdős publicada em 1959 que dá para todos g e k , existe um gráfico com malha de, pelo menos, g e número cromática pelo menos k . Por exemplo, o gráfico de Grötzsch tem uma malha de 4 e um número cromático de 4. A prova desse teorema usa o método probabilístico .