===== O Teorema de Mader ===== Vimos [[.ciclodeltakconexidade | anteriormente]] que um grafo precisa ter um [[.grauminimo | grau mínimo]] alto para que seja altamente conexo ou altamente aresta-conexo. Nesse sentido, é natural nos perguntarmos se isso é também suficiente: todo grafo com grau mínimo alto é [[.defkconexo | $k-$conexo]] e/ou [[.defLarestaconex |$\ell$-aresta-conexo]] para certos números $k,\ell \in \mathbb{N}$ razoavelmente grandes? Os exemplos abaixo mostram que não é difícil responder a esse questionamento negativamente. {{ :grafos:1conexo.png?400 |}} O grafo desenhado acima é obtido da seguinte maneira: dados dois [[.defcompleto | grafos completos]] de $n$ vértices, adicione um novo vértice adjacente a todos esses. Como a remoção do novo vértice torna esse grafo desconexo, ele é $1-$conexo, mesmo com seu grau mínimo sendo $n$. Vale ressaltar aqui que tal grafo não serioa $2$-conexo, ou seja, sua [[.connectivity| conectividade]] é $1$. Uma construção similar é feita abaixo, em que uma aresta é adicionada com extremidades em duas cópias de um $K_n$. Esse é um grafo $1-$aresta-conexo, portanto, mesmo seu grau mínimo sendo $n-1$. Assim, como o ultimo exemplo, vale ressaltar que este grafo não seria $2$-aresta-conexo. {{ :grafos:1arestaconexo.png?340 |}} Ainda assim, os grafos acima possuem cópias de grafos completos como [[.subgrafos| subgrafos]], que são altamente conexos. O Teorema de Mader justifica esse fenômeno, argumentando que grafos com [[.graumedio| grau médio]] alto possuem subgrafos com conexidade proporcional: \\ ==== 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 [[.grauMedio|Grau médio]] do grafo $G$, e;// * $\varepsilon(H)$ e $\varepsilon(G)$ são,[[.arestasmedia | quantidade média de arestas]] respectivamente, de $H$ e de $G$. //**Demonstração:**// Pelo [[.numTotaldeArestas|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 [[.arestasMedia|quantidade média de arestas por vértices de G]] e $d_{med}(G)$ é o [[.grauMedio| 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| 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 [[.defCompleto| 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$ [[.vizinhosDeV| 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 [[.separar | separador]] de $H$ com $|S| \leq k$. Seja $V_1$ o conjunto dos vértices de uma das [[.defCompCon|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$ ---- === Referências === * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 13. Acesso em 01/02/2023.