Teorema: Tutte(1963)

O espaço de ciclo de um grafo $3$-conexo é gerado por seus ciclos induzidos não separados.

Demonstração:

Seja $G$ um grafo fixo $3$-conexo, de ordem $n$ digamos. Provamos que cada um de seus ciclos $C$ é uma soma de ciclos induzidos não separados, aplicando indução em $k(C) := n-b$, onde $b$ denota a maior ordem de um componente de $G-C$ se houver um, e $b=0$ se $V(C)=V(G)$.

Não há ciclos $C$ para os quais $k(C)=0$, então a indução começa. Agora seja dado $C$ para a etapa de indução. Se $C$ é um ciclo gerador, é a soma de dois ciclos $C_1,C_2 \subseteq C+e$, onde $e$ é uma corda. Como $k(C_1),k(C_2) < n = k(C)$, estamos em casa por indução.

Suponha agora que $G-C \neq \emptyset$, e seja $B$ o maior componente de $G-C$. Suponha primeiro que $G-B$ contém um $C$-caminho $P=u \dots v$ tal que cada um dos dois caminhos $u-v$ em $C$ tem um vértice interno em $N(B)$. $(*)$

Então $C$ é a soma dos dois ciclos $C_1,C_2 \subseteq C \cup P$ contendo $P$, e para cada um destes $C_{i}$ existe uma componente de $G-C_{i}$ que contém $B$ propriamente. Daí $k(C_{i}) < k(C)$ , e estamos novamente em casa por indução.

Suponha finalmente que $(*)$ falhe. Então cada vértice de $C$ envia uma aresta para $B$. (De fato, se não, então $C$ contém um $N(B)$-caminho $Q = x \dots y$ com $\dot Q \neq \emptyset$. Como $G$ é $3$-conexo, $C-Q \neq \emptyset$, e há um caminho $\dot Q-(C-Q)$ em $G-\{x,y\}$. Tal caminho $P$ seria satisfaz $(*)$.) Como $V(C)=N(B)$, qualquer corda de $C$ também seria um caminho $P$ como em $(*)$, então $C$ não tem cordas. Portanto, a menos que o próprio $C$ seja induzido e não separado, $G-C$ tem um componente $B' \neq B$. Seja $P=u \dots v$ um $C$-caminho através de $B'$, e seja $Q$ um caminho $C-P$ em $G-\{u,v\}$. Observe que $Q$ também evita $B$. Agora $C \cup P \cup Q$ contém três ciclos $C_1,C_2,C_3$ somando a $C$ e cada um perdendo um vértice de $C$.

Como todo vértice de $C$ envia uma aresta para $B$, temos, portanto, $k(C_{i}) < k(C)$ para cada $i$, completando a etapa de indução.

$\square$