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:

Pelo Lema do Aperto de Mão, sabemos que $\gamma := \varepsilon (G) = \frac {d_{med}(G)}{2}$ é maior ou igual a $2k$; onde $\varepsilon(G)$ é a quantidade média de arestas por vértices de G e $d_{med}(G)$ é o grau médio de $G$. 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\|$$

Consideremos, então, todos os subgrafos $G' \subseteq G$, tal que:

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

Tais grafos $G'$ existem, haja vista que o próprio grafo $G$ configura um deles. Notemos inclusive que nenhum grafo como em $(*)$ possui ordem exatemnete $2k$, pois isso implicaria $||G’|| > \gamma k \geq 2k^2 > \binom{|G'|}{2}$. Em outras palavras, se tivéssemos $|G'|=2k$, o subgrafo $G'$ possuiria mais arestas que um grafo completo com $|G'|$ vértices, o que é um absurdo. Portanto, temos que $|G'| > 2k$.

Com isso em mente, considere um grafo $H \subseteq G$ que satisfaça $(*)$ e que seja o grafo com o menor número de vértices possíveis, isto é, o de menor ordem dentre todos os outros grafos $G' \subseteq G$.

Suponhamos por um momento que existe um vértice $v \in V(H)$ de grau máximo $\gamma$ em $H$, isto é, $v$ possui no máximo $\gamma$ vizinhos em $H$. Segundo esta observação, temos:

$$|H \setminus v| = |H|-1 > 2k -1 \geq 2k$$ e $$||H \setminus v || \geq ||H|| - \gamma > \gamma(|H|-k) - \gamma = \gamma((|H-1)-k) = \gamma(|H \setminus v| -k)$$

Ou seja, $H \setminus v$ ainda satisfazeria $(*)$, contradizendo a minimalidade de $H$. Portanto, a minimalidade de $H$ implica que $\delta(H) > \gamma$. Em particular, temos $|H| \geq \gamma$. E disso concluimos que:

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

Como desejado.

Para finalizar a demonstração, resta mostrar que $H$ é $(k-1)-$conexo. Suponhamos que isso não aconteça 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 decorre que $|H_1| \geq \gamma \geq 2k$. Por um argumento simétrico, temos que $|H_2| \geq \gamma \geq 2k$.

Portanto, pela minimalidade de $H$, tem-se que $||H_1|| \leq \gamma(|H_1| -k)$ e $||H_2|| \leq \gamma(|H_2| - k)$, logo, nem $H_1$ nem $H_2$ satisfaz $(*)$. 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_i|| \leq \gamma(|h_i|-k)$$

Mas então:

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

Como $|H_1 \cap H_2| \leq k$. E ainda temos que:

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

o que contradiz o fato de $H$ respeitar a relação $(*)$. Portanto, $H$ deve ser $(k+1)-$conexo.

$\square$