Agora, consideramos o empacotamento e a cobertura em termos de arestas em vez de vértices. Quantas árvores geradoras arestas-disjuntas podemos encontrar em um determinado grafo conexo? E quantas árvores, não necessariamente arestas-disjuntas, são suficientes para cobrir todas as suas arestas? Essas duas perguntas têm dois teoremas clássicos para respondê-las. Mas, em vez de provar esses teoremas diretamente, obteremos ambos como corolários de uma bela unificação recente devida a Bowler e Carmesin: o Teorema da Embalagem-Cobertura.

Para motivar o problema de empacotamento de árvores, assuma por um momento que nosso grafo representa uma rede de comunicação e que, para cada escolha de dois vértices, queremos ser capazes de encontrar $k$ caminhos arestas-disjuntos entre eles. O Teorema de Menger nos diz que tais caminhos existem assim que nosso grafo for $k$-aresta-conexo, o que claramente também é necessário. Este é um bom teorema, mas não nos diz como encontrar esses caminhos; em particular, depois de encontrá-los para um par de vértices finais, não estamos necessariamente em melhor posição para encontrá-los para outro par. Se nosso grafo tiver $k$ árvores geradoras arestas-disjuntas, no entanto, sempre haverá $k$ caminhos conônicos, um em cada árvore. Uma vez armazenadas essas árvores em nosso computador, sempre seremos capazes de encontrar rapidamente os $k$ caminhos entre qualquer par de vértices.

Quando um grafo $G$ tem $k$ árvores geradoras arestas-disjuntas? Se possui, claramente deve ser $k$-aresta-conexo. A recíproca, entretanto, é facilmente vista como falsa (tente $k=2$); de fato, nem mesmo está claro que qualquer aresta-conectividade implicará a existência de $k$ árvores geradoras arestas-disjuntas. (Mas veja o Corolário $1$ abaixo).

Aqui está outra condição necessária. Se $G$ tem $k$ árvores geradoras arestas-disjuntas, então com relação a qualquer partição de $V(G)$ em $r$ conjuntos, cada árvore geradora de $G$ tem pelo menos $r-1$ arestas-cruzadas, arestas cujas extremidades estão em diferentes conjuntos de partições. Assim, se $G$ tem $k$ árvores geradoras arestas-disjuntas, ele tem pelo menos $k(r-1)$ arestas-cruzadas. Esta condição também é suficiente:

O Teorema acima tem um corolário impressionante: a $2k$-aresta-conectividade é suficiente para garantir a existência de $k$ árvores geradoras arestas-disjuntas.

Observe que a condição quantitativa sobre arestas-cruzadas no Teorema do empacotamento acima é equivalente a perguntar o mesmo apenas para partições em conjuntos de vértices conectados: qualquer outra partição é refinada por tal partição, e se a última tiver arestas-cruzadas suficientes (mesmo que tenha mais classes) então claramente o primeiro também tem. O teorema do empacotamento de árvores diz, portanto, que um multigrafo tem $k$ árvores geradoras arestas-disjuntas assim que todos os seus minores de contração tiverem arestas suficientes para suportar $k$ árvores geradoras arestas-disjuntas.

Voltaremos a encontrar o Teorema $1$ acima quando falarmos sobre Grafos Infinitos, onde provaremos uma analogia infinita. Isso não se baseia em árvores geradoras comuns (para as quais o resultado é falso), mas em árvores geradoras topológicas: as estruturas análogas em um espaço topológico formado pelo grafo junto com suas extremidades, pontos no infinito que o tornam compacto.

Passemos agora ao problema da cobertura. Para trazer à tona sua dualidade com o problema de empacotamento, começamos reformulando o último. Digamos que alguns subgrafos dados de um multigrafo $G$ formam uma aresta-decomposição de $G$ se suas arestas definem a partição $E(G)$. Nosso problema de árvore geradora pode agora ser reformulado da seguinte forma: em quantos subgrafos geradores conexos podemos aresta-decompor $G$? Uma vez que um subgrafo gerador é conexoo se, e somente se, tiver uma aresta em cada ligação, o problema de empacotamento nesta nova forma tem uma 'dupla' reminiscência do Teorema e do Teorema: em quantos subgrafos acíclicos, aqueles cujo complemento atende a todos seus circuitos, podemos aresta-decompor $G$?

Digamos que alguns grafos dados, não necessariamente subgrafos de $G$, cobrem suas arestas se todas as arestas de $G$ estiverem em pelo menos uma delas. Nosso problema duplo, então, é para quais multigrafos $G$ podemos cobrir suas arestas por no máximo $k$ árvores.

Uma condição necessária óbvia é que todo conjunto $U \subseteq V(G)$ induz no máximo $k(|U|-1)$ arestas, não mais que $|U|-1$ para cada árvore. Ou, expressando duplamente para a condição de empacotamento da árvore, que nenhuma 'deleção minor' (subgrafo) de $G$ tem arestas demais para serem cobertas por $k$ árvores.

Mais uma vez, esta condição acaba por ser suficiente também:

O menor número de árvores que podem cobrir as arestas de um grafo é a sua arboricidade. Pelo teorema da cobertura logo acima, a arboricidade de um grafo é uma medida para sua densidade local máxima: ele tem arboricidade pequena se, e somente se, 'não é denso em nenhum lugar' no sentido de que não possui subgrafo $H$ com $\varepsilon (H)$ grande.

Finalmente chegamos ao teorema da empacotamento-cobertura. Lembre-se que quando formamos uma contração minor $G/P$ de um multigrafo $G$, mantemos todas as arestas de $G$ entre diferentes classes de partição: arestas entre as mesmas duas classes $U,U' \in P$ tornam-se arestas paralelas de $G/P$.

Antes de provarmos o teorema do empacotamento-cobertura, vamos deduzir, pelo teorema do empacotamento-cobertura enunciado acima, o teorema do empacotamento e o teorema da cobertura, respectivamente:

Dado o poder do teorema do empacotamento-cobertura, sua prova é surpreendentemente curta e elegante. Para preparar alguma notação, considere uma árvore geradora $T$ de $G$, uma corda $e$ e uma aresta $f \in T$ em seu ciclo fundamental $C_{e}$. Então $T' = T+e-f$ é outra árvore geradora: isso é imediato do Corolário, porque $T'$ ainda é coneco e tem o mesmo número de arestas que $T$. Diz-se que $T'$ é obtido de $T$ trocando $f$ por $e$.

Agora, seja $\mathcal{T} = (T_1, \dots, T_{k})$ uma família de árvores geradoras de $G$. Chame uma sequência $e_0, \dots, e_{n}$ de arestas de cadeia de troca para $\mathcal{T}$ iniciada por $e_0$ se $e_{n}$ não estiver em nenhuma dessas árvores, mas para todo $i < n$ existe $j =: j(i)$ tal que $e_{i} \in \mathcal{T}$ enquanto $e_{i+1}$ é uma corda de $\mathcal{T}_{j}$ cujo ciclo fundamental em relação a $\mathcal{T}_{j}$ contém $e_{i}$.

Vamos escrever $E(\mathcal{T}) := \bigcup \{E(T) \mid T \in \mathcal{T}\}$ para qualquer uma dessas famílias.

Agora sim podemos provar o Teorema do empacotamento-cobertura:

O teorema do empacotamento-cobertura difere do teorema do empacotamento da árvore e do teorema da cobertura da árvore de maneira fundamental. As direções não triviais dos dois últimos teoremas obtêm, cada uma, uma afirmação estrutural sobre um grafo, a existência de um empacotamento ou cobertura, como consequência de suposições quantitativas sobre todos os seus minores de certo tipo: minores de contração para o teorema do empacotamento e deleção minores, ou seja, subgrafos, para o teorema da cobertura. Esse formato os torna interessantes: eles oferecem informações estruturais valiosas para um grafo em troca de informações quantitativas menos valiosas sobre muitos grafos menores.

O teorema do empacotamento-cobertura, em contraste, faz uma afirmação estrutural sobre cada grafo: sem necessidade de quaisquer suposições, nem quantitativas nem qualitativas.