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

8. Subestruturas em grafos esparsos

Um grafo é esparso se seu número de arestas for da ordem do seu número de vértices. (Na verdade, o conceito só faz sentido quando aplicado a uma família de grafos com número arbitrariamente grande de vértices. Os grafos de tal família são esparsos se ‖G‖ = Ο(|G|) para G na família.)
Exemplos: Florestas são esparsas. O conjunto de todos os grafos com n vértices e menos que 1000n arestas são esparsos. Grafos completos não são esparsos.
Este capítulo estuda algumas condições suficientes para que um grafo tenha um máinor K^r. Essas condições são particularmente relevantes quando o grafo é esparso.
Exemplo: Existe uma função h tal que se ‖G‖ > h(r) |G| (ou seja, d(G) ≥ 2h(r)) então K^r é máinor topológico de G. (Esse é o Teorema 3.6.1.)

Exercícios:
1. [8.1] Dê uma prova elementar do seguinte teorema de Wagner: se chi(G) ≥ 2^r então K^r é máinor de G. (Sugestão: Indução em r.)
2. [8.2] Dê uma prova elementar do seguinte teorema de Mader: se d(G) ≥ 2^r–2 então K^r é máinor de G. (Sugestão: Indução em r.)

8.1 Máinors topológicos (topological minors)

Teorema 8.1.1 (Bollobás & Thomason, Komlós & Szemerédi): Existe c tal que, para todo r, se d(G) ≥ cr² então K^r é máinor topológico de G (ou seja, G inclui uma subdivisão de K^r ).
(Diestel usa c=1116. De acordo com Komlós e Szemerédi, c < 1.)
Prova: Um conjunto U de vértices é ligado (= linked) se para quaisquer vértices u₁, … , u_2h existem caminhos disjuntos de u₁ a u₂, de u₂ a u₃, … , de u_2h–1 a u_2h. Diremos que G é (k, l)-ligado se todo conjunto de k vértices tem um subconjunto ligado com l vértices.
Lema 8.1.2: Se G é k-conexo e tem um máinor H com 2 delta(H) ≥ |H| + 3k/2 então G é (k, ⌈k/2⌉)-ligado. (Compare com Teorema 3.6.2. Veja também Teorema 1.4.2.)
Lema 8.1.3: Para k ≥ 6, todo grafo com d(G) ≥ 2k tem um máinor H com 2 delta(H) ≥ |H| + k/6.

Exercícios:
1. [8.5] Mostre que toda função h como no Teorema 3.6.1 satisfaz a desigualdade h(r) > r²/8 para todo r par. Portanto, o Teorema 8.1.1 é o melhor possível (a menos da constante c).
2. Mostre que para todo r e qualquer f (r), existe G com d(G) > f (r) tal que nem todo conjunto com r(r − 1) vértices é ligado.
3. [8.6] Prove o Lema 8.1.3 no caso k < 6.
4. [8.7] Explique como o termo k/6 do Lema 8.1.3 é usado na prova do Teorema 8.1.1. Esse termo poderia ser trocado por k/1000?
5. [8.8] Mostre de onde surgiu o número 7/6 na prova do Lema 8.1.3. É possível substituir o número por 5/6?

8.2 Máinors (minors)

Teorema 8.2.1 (Kostochka, Thomason): Existe c tal que, para todo r, se d(G) ≥ c r (log r)^½ então K^r é máinor de G.
(O resultado é o melhor possível, a menos do valor de c.)
Apêndice: Teorema 8.2.2 (Thomassen): Se delta(G) ≥ 3 e g(G) ≥ 4k − 3 então G tem máinor H com delta(H) ≥ k. (Le,brete: g(G) é a cintura de G.)
Corolário 8.2.3: Existe c tal que, para todo r, se delta(G) ≥ 3 e g(G) ≥ c r (log r)^½ então K^r é máinor de G. (Surpreendente!)

8.3 Conjectura de Hadwiger

De acordo com o Corolário 5.2.3, se chi(G) ≥ c r (log r)^½ então K^r é máinor de G.
Conjectura (Hadwiger): Para todo grafo G e todo r, se chi(G) ≥ r então K^r é máinor de G. (Ou seja, todo grafo G inclui K^chi(G) como máinor.)
(Ou seja, se G não admite coloração com r − 1 cores então K^r é máinor de G. Ou seja, todo grafo sem máinor K^r admite uma coloração com r − 1 cores.)
A conjectura está verificada para r = 3 (grafos sem máinor K³ são florestas).
Corolário 8.3.2 (da Proposição 8.3.1): A conjectura está verificada para r = 4. (Grafos sem máinor K⁴ são série-paralelos. A Proposição 8.3.1 dá uma caracterização indutiva.)
Corolário 8.3.6 (do Teorema 8.3.4): A conjectura está verificada para r = 5. (O Teorema 8.3.4 (Wagner) caracteriza indutivamente grafos sem máinor K⁵.)
Teorema 8.3.7: A conjectura está verificada para r = 6.

Exercícios:
1. [8.10] Deduza o teorema da quatro cores (Teorema 5.1.1) do caso r = 5 da conjectura de Hadwiger.
2. [8.11] Mostre que se a conjectura de Hadwiger vale para r+1 então também vale para r.
3. [8.13, difícil] Dê uma prova elementar do caso r = 4 da conjectura de Hadwiger. Ou seja, mostre, sem recorrer à Proposição 8.3.1, que chi(G) ≥ 4 implica que K⁴ é máinor de G.
4. [8.15.i] Mostre que a conjectura de Hadwiger equivale à afirmação de que todo grafo tem um K^chi(G) como máinor.
5. [8.16] Seja G um grafo construído como na Proposição 8.3.1 (ou seja, G é K³ ou G = X∪Y onde X e Y foram construídos como na Proposição 8.3.1 e têm exatamente uma aresta em comum). Mostre que G não inclui um MK⁴ mas, para todo par xy de vértices não adjacentes de G, o grafo G+xy inclui um MK⁴.
6. Mostre que todo grafo construído como na Proposição 8.3.1 é da forma G∪T, onde G é um grafo construído como na Proposição 8.3.1 e T é um triângulo com exatamente uma aresta em comum com G.
7. [8.17] Mostre que se delta(G) ≥ 3 então K⁴ é máinor topológico de G. (Sugestão: Proposição 8.3.1).
8. [8.18] Um multigrafo é série-paralelo se pode ser construído recursivamente a partir de K² pelas operações de (1) subdivisão e (2) duplicação de arestas. Mostre que todo multigrafo 2-conexo é série-paralelo se e só não inclui K⁴ como máinor topológico.
9. Conjectura de Hajós: se chi(G) ≥ r então K^r é máinor topológico de G. Discuta o seguinte contraexemplo de Catlin: tome 5 cópias disjuntas de K³, arranje-as em um ciclo, e ligue cada duas cópias consecutivas por todas as 9 possíveis arestas.