Cintura (teoría de grafos)

[3]​ Por ejemplo, un ciclo de cuatro vértices (cuadrado) tiene cintura 4.

Si un grafo tiene cintura mayor a tres, se dice que es libre de triángulos.

, existe un grafo con cintura al menos

Paul Erdos fue el primero en probar este resultado, mediante el uso del método probabilístico.

La cintura par y cintura impar de un grafo son las longitudes del menor ciclo par e impar, respectivamente.