Teorema

Todo grafo $G$ que contém um ciclo satisfaz:

$$g(G) \leq 2 diam(G) + 1$$

onde:

• $g(G)$ é a cintura de $G$;
• $diam(G)$ é o diâmetro de $G$.

Demonstração:

Vamos considerar $C$ o ciclo de menor diâmetro, ou seja, o ciclo de diâmetro $g(G)$. Por contradição, suponha $g(G) \geq 2diam(G) + 2$. Dessa forma, $C$ possui dois vértices cuja distância em $C$ é pelo menos $diam(G)+1$. Mas como o diâmetro é a maior distância possível entre quaisquer dois vértices do grafo, é preciso que haja um caminho menor entre eles. Então existe $x$ e $y$ no ciclo tal que há um $C$-caminho entre eles.

Esse $C$-caminho em união com o caminho entre $x$ e $y$ formado por vértices de $C$ forma um ciclo menor que $C$, o que é um absurdo, uma vez que consideramos $C$ como o ciclo de menor diâmetro. Logo, segue que $g(G) \leq 2diam(G) + 1$.

$\square$