Os números de capítulos, seções, teoremas e exercícios se referem ao livro de Diestel, 2-a edição.

3. Conexidade (= connectivity)

3.3 O teorema de Menger

A e B são conjuntos de vértices.
Teorema 3.3.1 (Menger): O número mínimo de vértices que separam A de B é igual ao número máximo de caminhos disjuntos que ligam A a B.
Um conjunto X de vértices separa A e B se todo caminho de A a B passa por X.
Corolário 3.3.4.i: Para quaisquer vértices não adjacentes a e b, min |S| = max |P| , onde S é um subconjunto de V − {a,b} que separa a de b e P é um conjunto de caminhos independentes que ligam a a b.
Corolário 3.3.4.ii: Para quaisquer vértices distintos a e b, min |A| = max |P| , onde A é um conjunto de arestas que separa a de b e P é um conjunto de caminhos disjuntos nas arestas que ligam a a b.
Teorema 3.3.5.a: G é k-conexo se e só se cada par de vértices é ligado por k ou mais caminhos independentes.
Caminhos independentes (= internamente disjuntos): nenhum contém um vértice interno de outro.
Teorema 3.3.5.b: G é k-aresta-conexo se e só se cada par de vértices é ligado por k ou mais caminhos sem arestas em comum.

A := coleção disjunta de partes de V(G).
A-caminho: começa e termina em elementos distintos de A mas não tem vértices internos em elementos de A.
Split: coleção disjunta Y₁, … , Y_k de conjuntos de vértices.
Um split é separador se todo A-caminho tem um vértice em V(G) − (Y₁∪…∪Y_k) ou uma aresta em algum Y_i.
Capacidade do split: |V(G)| − |Y₁|−…−|Y_k| + ⌊½|∂Y₁|⌋ + … + ⌊½|∂Y_k|⌋ , sendo ∂Y o conjunto dos vértices em Y que estão na união dos elementos de A ou que têm algum vizinho fora de Y ∪ X, sendo X o complemento de Y₁∪ … ∪Y_k.
Teorema 3.4.1 (Mader): O número máximo de A-caminhos disjuntos é igual à capacidade de um split separador de capacidade mínima.

Exercícios:
1. Dê um bom exemplo para ilustrar o Teorema 3.4.1.
2. Mostre que o enunciado do teorema de Mader que está em Diestel é equivalente ao enunciado acima.

da seção 3.4 (baseada na nova prova do teorema de Mader descoberta por Schrijver).

Nesta seção, é mais apropriado trabalhar com multigrafos.
Um subgrafo H de um grafo G é gerador (= spanning) se V(H) = V(G). Qualquer subgrafo gerador que é uma árvore é conhecido como árvore geradora.
Aresta externa (= cross-edge) de uma partição P do conjunto de vértices: tem pontas em dois diferentes membros de P.
Teorema 3.5.1 (Tutte e Nash-Williams): Um multigrafo tem k árvores geradoras disjuntas se e só se toda partição P do conjunto de vértices tem pelo menos k (|P| − 1) arestas externas.
Corolário 3.5.2: Todo multigrafo 2k-aresta-conexo tem k árvores geradoras disjuntas.

Nesta seção, voltamos a tratar de grafos, não multigrafos.
Grafo k-ligado (= k-linked): para quaisquer vértices s₁, … , s_k, t₁, … , t_k distintos dois a dois, existem caminhos disjuntos P₁, … , P_k, cada P_j ligando s_j a t_j.
Teorema auxiliar 3.6.1 (Mader): Existe uma função h tal que todo grafo G com d(G) ≥ h(r) inclui K^r como máinor topológico (ou seja, inclui uma subdivisão do grafo completo com r vértices).
Lema técnico dentro da demonstração do Teorema 3.6.1: Suponha r ≥ 3. Para todo m ≥ r, se G tem d(G) ≥ 2^m então G contém uma subdivisão de algum grafo com r vértices e m arestas. (Para m = r, por exemplo, basta que G contenha um ciclo de comprimento ≥ r.)
(Veja também cap. 8.)
Teorema 3.6.2 (Jung e Larman & Mani): Existe uma função f tal que todo grafo f (k)-conexo é k-ligado.
Bollobás e Thomason mostraram que o Teorema 3.6.2 vale com f (k) = 22 k.