3.5. DEA para cliques
em ´arvore de G + (v, w) ´e tamb´em no m´aximo k. Al´em disso, qualquer decomposic¸˜ao
em ´arvore de G com largura no m´aximo k ´e tamb´em uma decomposic¸˜ao em ´arvore de
G + (v, w) com largura no m´aximo k, e vice-versa.
Prova. Seja D = (X , T ) uma decomposic¸˜ao em ´arvore de G com largura no m´aximo
k. Pela Propriedade 7, ou existe um i ∈ I com v, w ∈ X
i
— e logo a propriedade segue
diretamente pela Propriedade 5 — ou existe um i ∈ I com X
i
contendo o conjunto W
de todos os vizinhos em comum de v e w. Neste caso, poderiam ser adicionadas arestas
unindo todos os pares de v´ertices n˜ao adjacentes em W , resultando em pelo menos duas
cliques com k + 2 v´ertices, W + v e W + w. Novamente pela Propriedade 5, essa nova
decomposic¸˜ao em ´arvore D
deve ter a mesma largura de D, um absurdo j´a que nenhuma
decomposic¸˜ao em ´arvore com largura no m´aximo k pode conter uma clique com k + 2
v´ertices. Logo, por contradic¸˜ao, o primeiro caso vale, e a propriedade segue.
Com a ajuda da Propriedade 7, tem-se mais ferramentas para encontrar uma
caracterizac¸ ˜ao de uma nova classe de grafos de largura pequena e limitada.
Teorema 3.6. A classe dos grafos com largura em
´
arvore no m
´
aximo 2
´
e exatamente a
classe de grafos que tem K
4
como menor proibido, Proib
({K
4
}).
Prova. O teorema equivale a dizer que um grafo G tem largura em ´arvore no m´aximo
2 se e somente se G n˜ao possui K
4
como menor. A condic¸ ˜ao necess´aria ´e imediata, j´a que
se G tem largura em ´arvore no m´aximo 2 ent˜ao a maior clique de G tem tamanho 3, e
uma clique de tamanho 4 resultaria numa largura no m´ınimo 3 para G.
Suponha ent˜ao, s.p.d.g., que G = MK
4
e, no pior caso, ´e maximal em arestas. Pela
Proposic¸˜ao 2.7, se G = MK
4
ent˜ao G = T K
4
, j´a que ∆(K
4
) = 3, e logo, G n˜ao possuir
K
4
como menor ´e equivalente a G n˜ao possuir uma subdivis˜ao de K
4
como subgrafo. A
id´eia da prova ´e mostrar, por induc¸ ˜ao, que G pode ser montado por colagem de K
2
a partir
de triˆangulos, e logo, claramente LA(G) ≤ 2, j´a que desta forma a maior clique de G ´e
um K
3
.
Se G = K
3
, tem-se a base da induc¸ ˜ao, e suponha ent˜ao |G| ≥ 4 como passo. Como
G n˜ao ´e completo, sejam S um separador em G tal que |S| = κ(G), C
1
e C
2
componentes
de G − S, e G
1
= G[C
1
∪ S] e G
2
= G[C
2
∪ S]. Como S ´e um separador minimal,
todo v´ertice em S possui um vizinho em C
1
e outro em C
2
. Se |S| ≥ 3, ent˜ao G possui
pelo menos 3 caminhos disjuntos em v´ertices entre v
1
∈ C
1
e v
2
∈ C
2
, P
1
, P
2
e P
3
. Como
κ(G) ≥ 3, existe um outro caminho P entre u e v em G\{v
1
, v
2
} tais que u e v pertencem
a caminhos diferentes entre P
1
, P
2
e P
3
e possam, desta forma, ter pelo menos 3 caminhos
independentes entre si. Na Figura 3.11, u ∈ P
1
e v ∈ P
2
, e logo P ´e um terceiro caminho
unindo u a v.
Mas P ∪ P
1
∪ P
2
∪ P
3
= T K
4
, um absurdo, e logo κ(G) ≤ 2. Logo, |S| ≤ 2 e, pela
maximalidade de G, G[S] = K
2
. Como G
1
∩ G
2
= S e G
1
∪ G
2
= G, G pode ser obtido
a partir de G
1
e G
2
por colagem ao longo de S = K
2
, o resultado segue por induc¸˜ao.
Como ilustrado pelos lemas sobre caracterizac¸ ˜ao de grafos com largura em ´arvore
limitada, uma boa abordagem ´e considerar sub-estruturas proibidas em um determinado
grafo e ent˜ao classific´a-lo. Infelizmente, esta abordagem pode n˜ao ser eficiente a medida
31