Teorema de Mader

Dados $k > 0$ um número natural e $G = (V,A)$ um grafo com $d_{med}(G)\geq 4k$, existe $H$ um subgrafo de $G$ que é $(k+1)-$conexo e tal que:

$$ \varepsilon(H) > \varepsilon(G) - k$$

onde:

• $d_{med}(G)$ é o Grau médio do grafo $G$, e;
• $\varepsilon(H)$ e $\varepsilon(G)$ são, quantidade média de arestas respectivamente, de $H$ e de $G$.

Demonstração 1

Pelo Lema do Aperto de Mão, sabemos que $\gamma := \varepsilon(G) = \frac{d(G)}{2}$ é maior ou igual a $2k$. Pela definição de grau médio, inclusive, deve haver algum vértice de $G$ com grau maior ou igual a $4k$: caso contrário, a média dos graus de $G$ seria no máximo $4k-1$. Em particular, como $k > 0$, há pelo menos $2k$ vértices em $G$. Além disso,

$$\gamma(|G|-k) = \varepsilon(G)(|G|-k) =\frac{\|G\|}{|G|}(|G|-k) = \|G\|-\frac{k}{|G|}< \|G\|$$

Em outras palavras, a família $\mathcal{G}$ de subgrafos $G'\subset G$ que satisfazem $|G'|\geq 2k$ e $\|G'\|> \gamma(|G'|-k)$ é não vazia, pois $G\in\mathcal{G}$. Note inclusive que, se $G'\in \mathcal{G}$, então $|G'|> 2k$. Afinal, se tivéssemos $|G'| = 2k$, o subgrafo $G'$ possuiria mais arestas que um grafo completo com $|G'|$ vértices (pois $\|G'\|> \gamma(2k-k) = \gamma k \geq 2k^2 > \binom{|G'|}{2}$), o que é um absurdo.

Com isso, considere $H\in \mathcal{G}$ um grafo com o menor número de vértices possível. Suponha por um momento que existe um vértice $v\in V(H)$ de grau no máximo $\gamma$ em $H$ (isto é, $v$ possui no maximo $\gamma$ vizinhos em $H$). Pela observação feita acima, $|H\setminus v| = |H|-1 > 2k-1 \geq 2k$. Além disso, $\|H\setminus v\|\geq \|H\| - \gamma > \gamma(|H|-k)-\gamma = \gamma((|H|-1)-k) = \gamma(|H\setminus v| - k)$. Ou seja, $H\setminus v \in \mathcal{G}$, contradizendo a minimalidade da quantidade de vértices de $H$ como elemento de $\mathcal{G}$. Provamos portanto que $\delta(H) > \gamma$. Em particular, temos $|H|> \gamma$ e disso concluímos que:

$$\varepsilon(H) = \frac{\|H\|}{|H|} > \frac{\gamma(|H|-k)}{|H|} = \gamma - \frac{\gamma k}{|H|} > \gamma - k = \varepsilon(G)-k$$ $$\Downarrow$$ $$ \varepsilon(H) > \varepsilon(G) - k$$

Finalizando a demonstração, mostraremos que $H$ é também $(k+1)-$conexo. Por um momento, suponha que isso não ocorre e seja $S\subset V(H)$ um separador de $H$ com $|S|\leq k$. Seja $V_1$ o conjunto dos vértices de uma das componentes conexas de $H\setminus S$ e considere $V_2 = H\setminus (S\cup V_1)$ a coleção dos demais vértices de $H\setminus S$. Com isso, defina os subgrafos $H_1 = H[V_1 \cup S]$ e $H_2 = H[V_2 \cup S]$, de modo que $V(H_1)\cap V(H_2) = S$. Dado $v\in V_1$, a definição de componente conexa nos garante que $v$ não possui vizinhos em $V_2$. Ou seja, todos os seus vizinhos de $H$ se encontram em $H_1$. Como já provamos, porém, o grau mínimo de $H$ é maior que $\gamma$, disso decorrendo que $|H_1|\geq \gamma \geq 2k$. Por um argumento simétrico, $|H_2|\geq \gamma \geq 2k$.

Portanto, pela escolha de $H$ como elemento de menor ordem de $\mathcal{G}$, tem-se que $\|H_1\| \leq \gamma(|H_1|-k)$ e $\|H_2\| \leq \gamma(|H_2|-k)|$. Porém, $A(H) \subset A(H_1) \cup A(H_2)$, pois $H_i$ é definido como o subgrafo de $H$ induzido por $V_i$ e $S$, e, para cada $i=1,2$, os vértices de $V_i$ possuem apenas vizinhos entre si e entre $S$. Logo,

\[\|H\| \leq \|H_1\| + \|H_2\| \leq \gamma(|H_1|-k)+\gamma(|H_2|-k) = \gamma(|H_1|+|H_2|-2k) = \gamma(|H|+|S|-2k) = \gamma(|H|+k-2k)\leq \gamma(|H|-k),\] contradizendo o fato de que $H\in \mathcal{G}$. Portanto, $H$ deve ser $(k+1)-$conexo.

$\square$

Demonstração 2:

Pelo lema do Aperto de Mão, sabemos que $$\gamma := \varepsilon (G) = $\gamma := \varepsilon(G) = \frac{d(G)}{2}$ é maior ou igual a $2k$, e consideremos os subgrafos $G’ \subseteq G$, tal que:

$$|G’| \geq 2k$$ e $$||G’|| > \gamma (|G’| - k).(*)$$

Tais grafos $G'$ existem, hava vista que o próprio grafo $G$ configura um deles; seja $H$ o de menor ordem.

Nenhum grafo $G’$ como em $(*)$ possui ordem exatamente $2k$, pois isso implicaria que $||G’|| > \gamma k \geq 2k^2 > \binom{|G'|}{2}$. A minimalidade de $H$, portanto, implica que $\delta (H) > \gamma$. Caso contrário, poderíamos excluir um vértice de grau no máximo $\gamma$ e obter um grafo $G' \subseteq H$ ainda satisfazendo $(*)$. Em particular, temos $|H| \geq \gamma$. Dividindo a inequação $||H|| > \gamma |H| - \gamma k$ de $(*)$ por $|H|$, teremos $\varepsilon (H) > \gamma - k$, como desejado.

Resta mostrar então que $H$ é $(k+1)$-conexo. Sonhamos que não seja, então $H$ tem uma separação adequada $\{U_1 , U_2\}$ de ordem no máximo $k$; coloquemos $H[U_i] =: H_i$. Já que qualquer vértice $v \in U_1 \setminus U_2$ respeita a relação: $d(v) \geq \delta (H) > \gamma$ vizinhos de $H$ em $H_1$, temos $|H_1| \geq \gamma \geq 2k$. Similarmente, $|H_2| \geq 2k$.

Como pela minimalidade de $H$ nem $H_1$ nem $H_2$ satisfaz $(*)$, ainda temos:

$$||H_i|| \leq \gamma (|H_i| -k)$$

para $i = 1,2$. Mas então:

$$||H|| \leq ||H_1|| + ||H_2||$$ $$\Downarrow$$ $$||H|| \leq \gamma (|H_1| + |H_2| - 2k)$$

Como $|H_1 \cap H_2| \leq k$.

$$||H|| \leq \gamma (|H_1| + |H_2| - 2k)$$ $$\Downarrow$$ $$||H|| \leq \gamma (|H| -k)$$

o que contradiz $(*)$ para $H$.

$\square$