Vamos começar nossa construção com um ciclo $G_{0}$ de tamanho $g$. Note que esse ciclo satisfaz a hipótese sobre a cintura, mas não é $k$-conexo.

Para tornar $G_{0}$ $k$-conexo, iremos acrescentar $k$ caminhos entre cada dois vértices de $G_{0}$, de forma que cada caminho tenha tamanho no mínimo $g$. Seja $G_{1}$ nosso novo grafo. Note que $G_{0}$ agora é $k$-conexo, e que $G_{1}$ satisfaz a propriedade da cintura. Mas $G_{1}$ não é $k$-conexo. Iremos então repetir esse processo formando um grafo $G_{2}$, e assim por diante.

Note que a união de todos os grafos tem cintura pelo menos $g$ e é $k$-conexo.