| Para completar sua prova de $(*)$, escolha um vértice $v_0 \in V \setminu X$ de grau $d^*$ e considere o subgrafo $H$ induzido em $G$ por $v_0$ e seus vizinhos. Por $(2)$ temos $\delta (H) \geq 8k$, e por $(3)$ e a escolha de $v_0$ temos $|H| \leq 16k$. Pelo Lema $2$ anterior, então, $H$ tem um subgrafo $k$-ligado; seja $L$ o seu conjunto de vértices. Por definição de '$k$-ligado' , temos $|L| \geq 2k \geq |X|$. Se $G$ contiver $|X|$ caminhos $X-L$ disjuntos, então $X$ está ligado em $G$, conforme desejado. Se não, então $G$ tem uma pequena $X$-separação $(A,B)$ com $L \subseteq B$. Se escolhermos $(A,B)$ de ordem mínima, então $G[B]$ contém $|A \cap B|$ caminhos $(A \cap B)-L$ disjuntos pelo teorema de Menger. Mas então $(A,B)$ é uma $X$-separação ligada que contradiz $(1)$. | Para completar sua prova de $(*)$, escolha um vértice $v_0 \in V \setminus X$ de grau $d^*$ e considere o subgrafo $H$ induzido em $G$ por $v_0$ e seus vizinhos. Por $(2)$ temos $\delta (H) \geq 8k$, e por $(3)$ e a escolha de $v_0$ temos $|H| \leq 16k$. Pelo Lema $2$ anterior, então, $H$ tem um subgrafo $k$-ligado; seja $L$ o seu conjunto de vértices. Por definição de '$k$-ligado' , temos $|L| \geq 2k \geq |X|$. Se $G$ contiver $|X|$ caminhos $X-L$ disjuntos, então $X$ está ligado em $G$, conforme desejado. Se não, então $G$ tem uma pequena $X$-separação $(A,B)$ com $L \subseteq B$. Se escolhermos $(A,B)$ de ordem mínima, então $G[B]$ contém $|A \cap B|$ caminhos $(A \cap B)-L$ disjuntos pelo teorema de Menger. Mas então $(A,B)$ é uma $X$-separação ligada que contradiz $(1)$. |