Lema 1

Existe uma função $h : \mathbb{N} \to \mathbb{N}$ tal que, para todo $\ell \in \mathbb{N}$, todo grafo de grau médio pelo menos $h(\ell)$ contém $K^{\ell}$ como minor topológico.

Teorema

Existe uma função $f: \mathbb{N} \to \mathbb{N}$ tal que todo grafo $f(k)$-conexo é $k$-ligado, para todo $k \in \mathbb{N}$.

Demonstração:

Provamos a afirmação para $f(x) = h(3k)+2k$, onde $h$ é uma função como no Lema logo acima. Seja $G$ um grafo $f(k)$-conexo. Então $d(G) \geq \delta (G) \geq \kappa (G) \geq h(3k)$, seja $K$ um $TK^{3k}$ em $G$ conforme fornecido pelo Lema acima, e seja $U$ o seu conjunto de vértices de ramificação.

Para a prova de que $G$ é $k$-ligado, sejam dados vértices distintos $s_1, \dots, s_k$ e $t_1, \dots, t_k$. Pela definição de $f(k)$, temos $\kappa (G) \geq 2k$. Portanto, pelo Teorema de Menger , $G$ contém caminhos disjuntos $P_1, \dots, P_k,Q_1, \dots, Q_k$ de modo que cada $P_i$ comece em $s_i$, cada $Q_i$ comece em $t_i$, e todos esses caminhos terminem em $U$, mas não tenha ennhum vertice interno em $U$. Seja o conjunto $\mathcal{P}$ desses caminhos escolhido de modo que o número total de arestas fora de $E(K)$ seja o menor possível.

Seja $u_1, \dots, u_k$ aqueles $k$ vértices em $U$ que não são um fim do caminho em $\mathcal{P}$. Para cada $i=1,dots,k$, seja $L_i$ o $U$-caminho em $K$ (ou seja, a aresta subdividida do $K^{3k}$) de $u_i$ até o final de $P_i$ em $U$, e seja $v_i$ o primeiro vértice de $L_i$ em qualquer caminho $P \in \mathcal{P}$. Por definição de $\mathcal{P}$, $P$ não tem mais arestas fora de $E(K)$ do que $Pv_iL_iu_i$, então $v_iP = v_iL_i$ e, portanto, $P= P_i$.Da mesma forma, se $M_i$ denota o $U$-caminho em $K$ de $u_i$ até o final de $Q_i$ em $U$, e $v_i$ denota o primeiro vértice de $M_i$ em qualquer caminho em $\mathcal{P}$, então esse caminho é $Q_i$. Então os caminhos $s_iP_iv_iL_iu_iM_iw_iQ_it_i$ são disjuntos para $i$ diferentes e mostra que $G$ é $k$-ligado.

Teorema (Thomas & Wollan 2005)

Seja $G$ um grafo e $k \in \mathbb{N}$. Se $G$ é $2k$-conexo e $\varepsilon (G) \geq 8k$, então $G$ é $k$-conexo.

Lema 2

Qualquer grafo $H$ com $\delta (G) \geq 8k \geq |H|/2$ tem um subgrafo $k$-ligado.

Demonstração:

Se o próprio $H$ é $k$-ligado, não há nada para mostrar, então suponha que não seja. Então podemos encontrar um conjunto $X$ de $2k$ vértices $s_1, \dots,s_k,t_1, \dots, t_k$ que não podem ser ligados em $H$ por caminhos disjuntos $P_i = s_i \dots t_i$. Seja $\mathcal{P}$ um conjunto de tantos caminhos quanto possível, sem vértices internos em $X$ e todos com comprimento máximo de $7$. Se existem vários conjuntos como $\mathcal{P}$, escolhemos um com $|\bigcup \mathcal{P}|$ mínimo. Podemos assumir que $\mathcal{P}$ não contém nenhum caminho de $s_1$ para $t_1$. Seja $J$ o subgrafo de $H$ induzido por $X$ e todos os vértices nos caminhos em $\mathcal{P}$, e seja $K := H-J$.

Observe que cada vértice $v \in K$ tem no máximo três vizinhos em qualquer $P_i \in \mathcal{P}$ dado se tiver quatro, então substituir o segmento $uP_iw$ entre seu primeiro e seu último vizinho em $P_i$ pelo caminho $uvw$ reduziria $|\bigcup \mathcal{P}|$ e, portanto, contradiria nossa escolha de $\mathcal{P}$. Portanto, $v$ tem no máximo $3$ vizinhos em $J$ para cada $i=1, \dots,k$, no máximo $3k$ no total. Como hipótese $\delta (H) \geq 8k$, assim como $|H| \leq 16k$ e $|X| =2k$, deduzimos que

$$\delta (K) \geq 5k \qquad e \qquad |K| \leq 14k. \qquad \qquad (1)$$

Nosso próximo objetivo é mostrar que $K$ é desconexo. Como cada um dos caminhos em $\mathcal{P}$ tem no máximo oito vértices, temos $|J-\{s_1,t_1\}| \leq 8(k-1)$. Portanto $s_1$ tem um vizinho $s$ em $K$, $t_1$ tem um vizinho $t$ em $K$. Coloque $S := \{s' \in K \mid d_{K}(s,s') \leq 2\}$ e $T := \{t' \in K \mid d_{K}(t,t') \leq 2\}$. Como $|H-\bigcup \mathcal{P}|$ não contém nenhum $s_1-t_1$ caminho de comprimento máximo $7$, temos $S \cap T = \emptyset$ e não há aresta $S-T$ em $K$. Para provar que $K$ é desconexo, basta mostrar que $V(K)=S \cup T$. Mas para qualquer vértice $v \in K-(S \cup T)$ os conjuntos $N_K(s), N_K(t)$ e $N_K(v)$ são disjuntos e cada um tem tamanho em menos $5k$, contradizendo $(1)$.

Então $K$ é desconexo; seja $C$ sua menor componente. Por $(1)$:

$$2\delta (C) \geq 2\delta(K) \geq 7k+3k \geq \frac{1}{2}|K|+3k \geq |C|+3k. \qquad \qquad (2)$$

Completamos a prova mostrando que $C$ é $k$-ligado. Como $\delta (C) \geq 5k$, temos $|C| \geq 2k$. Seja $Y$ um conjunto de no máximo $2k$ vértices em $C$. Por $(2)$ , cada dois vértices em $Y$ têm pelo menos $3k$ vizinhos comuns, pelo menos $k$ dos quais estão fora de $Y$. Podemos, portanto, ligar quaisquer $\ell \leq k$ pares de vértices desejados em $Y$ indutivamente por caminhos de comprimento $2$ cujo vértice interno está fora de $Y$.

Definição: $X$-separação

Dado $k \in \mathbb{N}$, um grafo $G$, e $A,B,X \subseteq V(G)$, chame o par ordenado $(A,B)$ de uma $X$-separação de $G$ se $\{A,B\}$ for uma separação adequada de $G$ de ordem no máximo $|X|$ e $X \subseteq A$. Uma $X$-separação $(A,B)$ é pequena se $|A \cap B| < |X|$, e ligada se $A \cap B$ é ligada em $G[B]$.

Definição: Conjunto Leve

Chame um conjunto $U \subseteq V(G)$ leve em $G$ se $||U||^+ \leq 8k|U|$, onde $||U||^+$ denota o número de arestas de $G$ com pelo menos uma extremidade em $U$. Um conjunto de vértices é pesado se não for leve.

Demonstração do Teorema de Thomas & Wollan:

Provaremos o seguinte, para $k \in \mathbb{N}$ fixo:

Para ver que $(*)$ implica o teorema , suponha que $\kappa (G) \geq 2k$ e $\varepsilon (G) \geq 8k$, e seja $X$ um conjunto de exatamente $2k$ vértices. Então $G$ não tem $X$-separação pequena. E $V \setminus X$ é pesado, pois

$$||V \setminus X||^+ \geq ||G|| -\binom{2k}{2} > 8k|V|-16k^2=8k|V \setminus X|.$$

Por $(*)$, $X$ é ligado em $G$, completando a prova de que $G$ é $k$-ligado.

Provamos $(*)$ por indução em $|G|$, e para cada valor de $|G|$ por indução em $||V \setminus X||^+$. Se $|G|=1$ então $X$ está ligado em $G$. Para a etapa de indução, sejam $G$ e $X$ dados como em $(*)$. Primeiro provamos o seguinte:

Para nossa prova de $(1)$, suponha que $G$ tenha uma $X$-separação ligada $(A,B)$. Vamos escolher um com $A$ mínimo e colocar $S := A \cap B$.

Primeiro consideramos o caso em que $|S|=|X|$. Se $G[A]$ contém $|X|$ caminhos $X-S$ disjuntos, então $X$ está ligado em $G$, porque $(A,B)$ está ligado, completando a prova de $(*)$. Se não, então pelo Teorema de Menger, $G[A]$ tem uma pequena $X$-separação $(A',B')$ tal que $B' \supseteq S$. Se escolhermos isso de ordem mínima, ou seja, com $|A' \cap B'|$ mínimo, podemos ligar $A' \cap B'$ a $S$ em $G[B']$ por $|A' \cap B'|$ caminhos disjuntos, novamente pelo teorema de Menger. Mas então $(A', B' \cup B)$ é uma $X$-separação ligada de $G$, o que contradiz a escolha de $(A,B)$.

Então $|S| < |X|$. Seja $G'$ obtido de $G[A]$ adicionando quaisquer arestas que faltam em $S$, de modo que $G'[S]$ seja um subgrafo completo de $G'$. Como $(A,B)$ agora é uma pequena $X$-separação, nossa suposição em $(*)$ diz que $B \setminus A$ é leve em $G$. Assim, $G'$ surge de $G$ excluindo $|B \setminus A|$ vértices fora de $X$ e no máximo $8k|B \setminus A|$ arestas, e possivelmente adicionando algumas arestas. Como $V \setminus X$ é pesado em $G$, isso implica que $A \setminus X$ é pesado em $G'$.

Para poder aplicar a hipótese de indução a $G'$, vamos mostrar a seguir que para toda pequena $X$-separação $(A',B')$ de $G'$ o conjunto $B' \setminus A'$ é leve em $G'$. Suponha que não, e escolha um contra-exemplo $(A',B')$ com $B'$ mínimo. Como $G'[S]$ é completo, temos $S \subseteq A'$ ou $S \subseteq B'$.

Se $S \subseteq A'$ então $B \cap B' \subseteq S \subseteq A'$, então $(A' \cup B, B')$ é uma pequena $X$-separação de $G$. Além disso,

$$B' \setminus (A' \cup B) = B' \setminus A',$$

e nenhuma aresta de $G'-E$ em $S$ é incidente com este conjunto.

Nossa suposição de que esse conjunto é pesado em $G'$, pela escolha de $(A',B')$, portanto implica que ele é pesado também em $G$. Como $(A' \cup B,B')$ é uma pequena $X$-separação de $G$, isso contradiz nossas suposições em $(*)$.

Portanto, $S \subseteq B'$. Por nossa escolha de $(A',B')$, o grafo $G'' := G'[B']$ satisfaz a premissa de $(*)$ para $X'' := A' \cap B'$. De fato, $B' \setminus X'' = B' \setminus A'$ é pesado e, pela minimalidade de $B'$, qualquer pequena $X''$-separação $(A'',B'')$ de $G''$ será tal que $B'' \setminus A''$ é leve, porque $(A' \cup A'',B'')$ será uma pequena $X$-separação de $G'$, e $B'' \setminus A'' = B'' \setminus (A' \cup A'')$.

Por hipótese de indução, portanto, $X''$ está ligado em $G''$. Mas então $X''$ também está ligado em $G[B' \cup B]$: como $S$ estava ligado em $G[B]$, simplesmente substituímos quaisquer arestas adicionadas em $S$ na definição de $G'$ por caminhos disjuntos através de $B$. Mas agora $(A',B' \cup B)$B é uma $X$-separação ligada de $G$ que viola a minimalidade de $A$ na escolha de $(A,B)$.

Mostramos assim que $G'$ satisfaz a premissa de $(*)$ em relação a $X$. Como $\{A,B\}$ é uma separação adequada, $G'$ tem menos vértices que $G$. Pela hipótese de indução, portanto, $X$ está ligado em $G'$. Substituindo arestas de $G' -E$ em $S$ por caminhos por $B$ como antes, podemos transformar qualquer ligação de $X$ em $G'$ em uma em $G$, completando a prova de $(*)$. Isso completa a prova de $(1)$.

Nosso próximo objetivo é mostrar que, pela hipótese de indução, podemos assumir que $G$ tem não apenas um grau médio grande, mas também um grau mínimo grande. Para nossa prova de que $X$ está ligado em $G$, sejam $s_1, \dots, s_{\ell},t_1, \dots, t_{\ell}$ os vértices distintos em $X$ que desejamos ligar por caminhos disjuntos $P_i = s_i \dots t_i$. Adicionemos a $G$ quaisquer arestas ausentes em $X$, exceto aquelas da forma $s_it_i$; como os caminhos $P_i$ não podem ter vértices internos em $X$, essas novas arestas não afetam nem a premissa nem a conclusão em $(*)$.

Após esta modificação, podemos agora provar o seguinte:

Para provar $(2)$, seja $e=uv$ tal aresta, seja $n$ o número de vizinhos comuns de $u$ e $v$, e seja $G' := G/e$ o gráfico obtido pela contração de $e$. Como $u,v$ não estão ambos em $X$, podemos ver $X$ como um subconjunto também de $V' := V(G')$, substituindo $u$ ou $v$ em $X$ pelo vértice $v_e$ contraído se $X \cap \{u,v\} \neq \emptyset$. Nosso objetivo é mostrar que, a menos que $n \geq 8k-1$ como desejado em $(2)$, $G'$ satisfaça a premissa de $(*)$. Então $X$ estará ligado em $G'$ pela hipótese de indução, então os caminhos $P_1,\dots,P_{\ell}$ desejados existem em $G'$. Se um deles contiver $v_e$, substituindo $v_e$ por $u$ ou $v$ ou $uv$ transforma-o em um caminho em $G$, completando a prova de $(*)$.

Para mostrar que $G'$ satisfaz a premissa de $(*)$ em relação a $X$, vamos mostrar primeiro que $V' \setminus X$ é pesado. Como $V \setminus X$ é pesado e $|V' \setminus X|=|V \setminus X|-1$, basta mostrar que a contração de $e$ resultou na perda de no máximo $8k$ arestas incidentes com um vértice fora de $X$. Se $u$ e $v$ estão ambos fora de $X$, então o número de arestas perdidas é apenas $n+1$: uma aresta em cada vizinho comum de $u$ e $v$, assim como $e$. Mas se $u \in X$, então $v \notin X$, e perdemos todas as $X-v$ arestas $xv$ de $G$ com $x \neq u$ também: enquanto $xv$ contava em direção a $||V \setminus X||^+$ , a aresta $xv_e$ está em $G'[X]$ e não conta em direção a $||V' \setminus X||^+$. Se $x$ não é um vizinho comum de $u$ e $v$, então esta é uma perda adicional. Mas $u$ é adjacente a todo $x \in X \setminus \{u\}$ exceto no máximo um (pela nossa suposição sobre $G[X]$), então todo $x$ exceto no máximo um é de fato um vizinho comum de $u$ e $v$. No total, perdemos no máximo $n+2$ arestas. A menos que $n \geq 8k-1$ (o que provaria $(2)$ diretamente para $u$ e $v$), isso significa que perdemos no máximo $8k$ arestas, conforme desejado para nossa prova de que $V' \setminus X$ é pesado.

Resta mostrar que para toda pequena $X$-separação $(A',B')$ de $G'$ o conjunto $B' \setminus A'$ é leve. Seja $(A',B')$ um contra-exemplo , escolhido com $B'$ mínimo. Então $G'[B']$, como na prova de $(1)$, satisfaz a premissa de $(*)$ com relação a $X' := A' \cap B'$. Portanto, $X'$ está ligado em $G'[B']$ por indução. Sejam $A$ e $B$ obtidos de $A'$ e $B'$ substituindo $v_e$, quando aplicável, por $u$ e $v$, e coloque $X'' := A \cap B$. Provaremos que a separação $(A,B)$ de $G$ contradiz nossa suposição $(1)$.

Consideremos duas posições possíveis de $v_e$ sucessivamente. Se $v_e$ estiver em $A' \setminus B'$ ou $B' \setminus A'$ , então $u,v \in A \setminus B$ ou $u,v \in B \setminus A$. Então $X'' = X'$ está ligado em $G[B]$, porque está ligado em $G'[B']$: se $v_e$ ocorrer em um dos caminhos de ligação para $X'$, apenas substitua-o por $u$ ou $v$ ou $uv$ como anteriormente . Isso contradiz $(1)$. A outra possibilidade é que $v_e \in X'$. Mostramos que $G[B]$ satisfaz a premissa de $(*)$ em relação a $X''$; então $X''$ estará ligado em $G[B]$ por indução, novamente contradizendo $(1)$. Como $(A',B')$ é uma pequena $X$-separação, temos

$$|X''| \leq |X'|+1 \leq |X| \leq 2k.$$

Além disso, $B \setminus X'' = B' \setminus A'$ é pesado em $G$, porque é pesado em $G'$ pela escolha de $(A',B')$. Agora considere uma pequena $X''$-separação de $G[B]$. Então $(A \cup A'', B'')$ é uma pequena $X$-separação de $G$, porque $|X''| \leq |X|$. Portanto $B'' \setminus A'' = B'' \setminus (A \cup A'')$ é leve pela hipótese em $(*)$. Portanto $G[B]$ satisfaz a premissa de $(*)$ para $X''$ completando a prova de $(2)$.

Usando indução por contração de uma aresta, acabamos de mostrar que os vértices em $V \setminus X$ podem ser assumidos como tendo grande grau. Usando indução por exclusão de uma aresta, agora mostramos que seus graus não podem ser muito grandes. Uma vez que $(*)$ vale se $V=X$, podemos assumir que $V \setminus X \neq \emptyset$; seja $d^*$ o menor grau em $G$ de um vértice em $V \setminus X$. Provemos o seguinte:

O limite inferior em $(3)$, isto é, $8k \leq d^*$, segue de $(2)$ se assumirmos que $G$ não tem nenhum vértice isolado fora de $X$, o que podemos assumir claramente por indução. Para o limite superior,$d^* \leq 16k-1$, vejamos o que acontece se excluirmos uma aresta $e$ cujas extremidades $u,v$ não estão ambas em $X$. Se $G-e$ satisfaz a premissa de $(*)$ em relação a $X$, então $X$ está ligado em $G-e$ por indução e, portanto, em $G$. Se não, então ou $V \setminus X$ é leve em $G-e$, ou $G-e$ tem uma pequena $X$-separação $(A,B)$ tal que $B \setminus A$ é pesado. Se o último acontecer, então $e$ deve ser uma $(A \setminus B)-(B \setminus A)$ aresta: caso contrário, $(A,B)$ seria uma pequena $X$-separação também de $G$, e $B \setminus A$ seria pesado também em $G$, em contradição com nossas suposições em $(*)$. Mas se $e$ é uma dessas arestas, então quaisquer vizinhos comuns de $u$ e $v$ estão em $ \cap B$, então há menos de $|X| \leq 2k$ tais vizinhos. Isso contradiz $(2)$.

Então $V \setminus X$ deve ser leve em $G-e$. Para $G$, isso produz

$$||V \setminus X||^+ \leq 8k |V \setminus X|+1. \quad (4)$$

Para mostrar que isso implica o limite superior desejado para $d^*$, vamos estimar o número $f(x)$ de arestas que um vértice $x \in X$ envia para $V \setminus X$. Deve haver pelo menos uma dessas arestas, digamos $xy$, caso contrário $(X, V \setminus \{x\})$ seria uma pequena $X$-separação de $G$ que contradiz nossas suposições em $(*)$. Mas então, por $(2)$, $x$ e $y$ têm pelo menos $8k-1$ vizinhos comuns, no máximo $2k-1$ dos quais estão em $X$. Portanto, $f(x) \geq 6k$. Como

$$2||V \setminus X||^+ = \sum_{v \in V \setminus X}d_{G}(v) + \sum_{x \in X}f(x),$$

uma suposição de $d^* \geq 16k$ implicaria que

$$2(8k |V \setminus X| +1) \geq_{(4)} 2||V \setminus X||^+ \geq 16k|V \setminus X| +6k|X|,$$

produzindo a contradição de $2 \geq 6k|X|$. Isso completa a prova de $(3)$.

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)$.