Download PDF
ads:
Universidade Federal de Pernambuco
Centro de Ci
ˆ
encias Exatas e da Natureza
Departamento de Matem
´
atica
Programa de P
´
os-Graduac¸
˜
ao em Matem
´
atica
Jos´e Laudelino de Menezes Neto
CIRCUITOS REMOV
´
IVEIS EM GRAFOS
Recife
2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Jos´e Laudelino de Menezes Neto
CIRCUITOS REMOV
´
IVEIS EM GRAFOS
Disserta¸c˜ao apresentada ao Departamento de Matem´atica
da Universidade Federal de Pernambuco, como parte dos
requisitos para obten¸c˜ao do t´ıtulo de Mestre em Matem´atica.
Orientador: Manoel Lemos
Recife
2008
ads:
Menezes Neto, Jos´e Laudelino de
Circuitos remov´ıveis em grafos / Jos´e Laudelino de
Menezes Neto. - Recife: O autor, 2008.
39 folhas : il., fig.
Disserta¸cao (mestrado) - Universidade Federal de
Pernambuco. CCEN. Matem´atica, 2008.
Inclui bibliografia.
1. Teoria dos grafos. I. T´ıtulo.
511.5 CDD (22.ed.) MEI2008-084
Para Raquel, Mozart e Maria Rita.
AGRADECIMENTOS
Agrade¸co a toda minha fam´ılia, tios, tias, primos, primas, avˆos e av´os.
Grato ao CNPq pelo apoio financeiro.
Agrade¸co ao Professor Mano el Lemos pela orienta¸c˜ao.
Agrade¸co a toda turma do Departamento de Matem´atica da UFPE, Lucas “haoli”
Lapa, Tarciana Maria, Eudes “t´ıpico americano” Naziazeno, Gigi, Adecarlos, Zaqueu,
Marcelo, Jo´ılson, Vovˆo Allyson, Jesus, B´arbara,
´
Eder, Tiago, Karla, J´ulio, Ricardo, Anete
e Wilberclay; aos que me ajudaram a pagar o aluguel, Andr´e, Manass´es e Wagner; aos
companheiros de sala, Ademakson, Liliam, Davis e Isabelle; aos professores, Cuevas,
Brito, Aron, Lucas e S´ostenes pelos cursos ministrados; a Tˆania Maranh˜ao pelo trabalho
desenvolvido na secretaria da P´os-Gradua¸c˜ao.
Agrade¸co aos demais amigos.
Jos´e Laudelino de Menezes Neto
RESUMO
Descreve-se a demonstra¸c˜ao do Teorema de Lemos e Oxley, o qual garante que,
sobre certas condi¸c˜oes, ao remover as arestas de um circuito de um grafo 2-conexo, o
mesmo continua 2-conexo. O comprimento do circuito retirado pode ser maior do que o
que ´e estipulado no Teorema de Jackson.
Palavras-chave: Grafo. 2-conexo. Circuito.
ABSTRACT
Describe the proof of a Theorem by Lemos and Oxley, which guarantees, under
certain conditions, that when deleted the edges of a circuit from a 2-connected graph,
the graph stills 2-connected. The length of the circuit, that could be removed, could be
greater than the one mentioned in Jackson’s Theorem.
Keywords: Graph. 2-connected. Circuit.
Sum´ario
1 Introdu¸c˜ao 7
2 Preliminares 9
2.1 V´ertices e arestas, temos um grafo . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Passeios, trilhas, caminhos e circuitos . . . . . . . . . . . . . . . . . . . . . 10
2.3 Conexidade e blocos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Ordem lexicogr´afica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Demonstra¸c˜ao do Teorema de Lemos e Oxley 17
3.1 G\C ´e conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Redu¸c˜ao ao caso que |E(H)| = 1 . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 E(H) ´e vazio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Exemplos 36
Referˆencias Bibliogr´aficas 38
Cap´ıtulo 1
Introdu¸c˜ao
Em 1974, foi provado por Mader [5] que todo grafo simples k-conexo com grau, no
m´ınimo, k + 2 possui um ciclo C tal que G\C ´e k-conexo. Independente disto, em 1985,
Jackson [4] provou um resultado mais forte que o de Mader para o caso 2-conexo.
Teorema 1.1 (Jackson) Seja G um grafo simples 2-conexo com grau, no m´ınimo, k,
onde k ≥ 4, e seja e uma aresta de G. Ent˜ao, G tem um circuito C, de comprimento no
m´ınimo k − 1, tal que e ∈ C e G\C ´e 2-conexo.
Em 1999, Lemos e Oxley [7] aprimoraram o Teorema 1.1.
Teorema 1.2 (Lemos e Oxley) Sejam G um grafo simples 2-conexo, H um subgrafo,
que ´e um bloco, de G e k um inteiro maior que trˆes. Suponhamos d
G
(v) ≥ k, para todo v
pertencente a V (G) − V (H). Ent˜ao,
1. G\C ´e 2-conexo para todo circuito C que ´e aresta-disjunta de H; ou
2. G tem um circuito C que ´e aresta-disjunta de H tal que G\C ´e 2-conexo e, quando
k ≥ 5, o comprimento de C ´e, no m´ınimo, k + 1.
Nosso objetivo ´e estudar a demonstra¸c˜ao do Teorema 1.2 apresentada pelos autores.
Para entender melhor o enunciado dos resultados citados acima e a demonstra¸c˜ao
do Teorema 1.2, no cap´ıtulo 2 descreveremos resultados e defini¸c˜oes b´asicas da teoria,
por exemplo, o que ´e um grafo k-conexo, um bloco, um circuito e o que significam as
nota¸c˜oes d
G
(v) ≥ k e G\C. O final da demonstra¸c˜ao de cada Teorema ´e demarcado com
um quadrado preto: .
8
No cap´ıtulo 3, apresentaremos a demonstra¸c˜ao do Teorema de Lemos e Oxley.
No quarto cap´ıtulo exibiremos dois exemplos que justificam a melhoria que o
Teorema 1.2 traz para a teoria.
Cap´ıtulo 2
Preliminares
Como dito na Introdu¸c˜ao, neste cap´ıtulo relataremos as nota¸c˜oes e defini¸c˜oes que
ser˜ao utilizadas no decorrer do nosso trabalho, bem como enunciaremos alguns resultados
b´asicos.
2.1 V´ertices e arestas, temos um grafo
Um grafo G ´e um par (V (G), E(G)), onde V (G) ´e um conjunto finito e E(G) ´e um
conjunto composto de pares n˜ao-ordenados de elementos distintos de V (G). Diremos que
V (G) e E(G) s˜ao, respectivamente, o conjunto de v´ertices e arestas do grafo G.
Dois v´ertices v e w de G s˜ao adjacentes se o par formado por v e w ´e uma aresta
de G, esta aresta ´e dita incidente sobre v e tamb´em sobre w; v e w s˜ao os extremos
da aresta e, neste caso, denotamos e por vw. O grau d
G
(v) de um v´ertice v de G ´e a
quantidade de arestas de G incidentes a este v´ertice; o menor grau que um v´ertice de
G assume ´e denotado por δ(G), ou seja, δ(G) = min{d
G
(v); v ∈ V (G)}. A estrela de v
´e o conjunto de arestas de G incidentes ao v´ertice v. Um grafo G ´e chamado de grafo
completo quando todos os v´ertices de G s˜ao adjacentes entre si, um grafo completo com
n v´ertices ´e denotado por K
n
.
Entendemos por subgrafo de um grafo G, como sendo um grafo H = (V (H), E(H))
tal que V (H) ⊆ V (G) e E(H) ⊆ E(G).
Se W ´e um conjunto qualquer n˜ao-vazio de v´ertices de G, ent˜ao o subgrafo induzido
por W , denotado por G[W ], ´e o subgrafo de G que tem W como conjunto de v´ertices e
cujas arestas s˜ao as arestas de G com extremos pertencentes a W . Seja V
⊆ V (G), o
10
subgrafo induzido G[V (G)\V
] ´e denotado por G − V
, este ´e o subgrafo obtido a partir
de G p ela dele¸c˜ao dos v´ertices pertencentes a V
e das arestas incidentes a estes v´ertices.
Se V
= {v}, escrevemos, por simplicidade, G − v.
Caso tenhamos um subconjunto n˜ao-vazio, F , de arestas de G, ent˜ao o subgrafo
induzido por F , G[F ], ´e o subgrafo de G cujo conjunto de arestas ´e F e o conjunto
de v´ertices s˜ao os extremos das arestas de F . Seja E
⊆ E(G), o subgrafo induzido
G[E(G)\E
] ´e denotado por G − E
, este ´e o subgrafo obtido a partir de G pela dele¸c˜ao
das arestas de E
. Se E
= {e}, escrevemos G − e.
Sejam G
1
e G
2
dois grafos. A uni˜ao G
1
∪ G
2
de G
1
e G
2
´e o grafo com conjunto
de v´ertices V (G
1
) ∪ V (G
2
) e conjunto de arestas E(G
1
) ∪ E(G
2
).
Exemplo 2.1 A Figura 2.1(1) representa o grafo G = K
4
com conjunto de v´ertices
V (G) = {v
1
, v
2
, v
3
, v
4
} e conjunto de arestas E(G) = {a, b, c, d, e, f}, onde e = v
1
v
3
e
f = v
2
v
4
. J´a na Figura 2.1(2), temos o grafo G
= G − v
3
.
v
1
v
2
v
3
v
4
a
b
c
d
e
f
(1)
v
1
v
2
v
4
a
f
d
(2)
Figura 2.1: G e G
2.2 Passeios, trilhas, caminhos e circuitos
Um passeio em um grafo G ´e uma sequˆencia finita, n˜ao-nula, P = v
0
e
1
v
1
...e
k
v
k
cujos termos s˜ao v´ertices e arestas postos de forma alternada e tais que, para 1 ≤ i ≤ k,
os extremos de e
i
s˜ao os v´ertices v
i−1
e v
i
. Chamamos v
0
de v´ertice inicial e v
k
de v´ertice
terminal do passeio P , os v´ertices v
1
, v
2
, ..., v
k−1
s˜ao conhecidos por v´ertices interiores do
passeio P . O inteiro k ´e o comprimento do passeio P . Em um grafo simples, um passeio
v
0
e
1
v
1
...e
k
v
k
´e determinado apenas pela sequˆencia de v´ertices v
0
v
1
...v
k
.
Se as arestas e
1
, e
2
, ..., e
k
de um passeio P s˜ao distintas, ent˜ao chamamos P de
trilha e, neste caso, o comprimento de P ´e |E(P )|. Se, al´em das arestas, os v´ertices
v
0
, v
1
, ..., v
k
tamb´em s˜ao distintos, dizemos que P ´e um caminho. Quando for conveniente,
11
chamaremos um caminho de v´ertice inicial v
0
e v´ertice terminal v
k
de v
0
v
k
-caminho. Um
caminho em G ´e Hamiltoniano quando cont´em todos os v´ertices de G.
Uma fam´ılia de caminhos em G ´e internamente-disjunta se nenhum v´ertice de G
´e um v´ertice interno de mais do que um caminho desta fam´ılia.
Um passeio ´e fechado se tem comprimento positivo e o v´ertice inicial ´e tamb´em o
v´ertice terminal. Um caminho fechado ´e chamado de circuito.
Sejam G um grafo e E
as arestas de um circuito C de G, ou seja, E
= E(C) ⊆
E(G). O subgrafo induzido G[E(G)\E
] ´e denotado por G\C.
Exemplo 2.2 A Figura 2.2(1) representa um grafo G com conjunto de v´ertices V (G) =
{v
1
, v
2
, v
3
, v
4
, v
5
, v
6
} e conjunto de arestas E(G) = {a, b, c, d, e, f, v
6
v
7
, v
5
v
7
}. A Figura
2.2(2) representa o grafo G
= G\C, onde C ´e um circuito de G com conjunto de arestas
E(C) = {a, b, c, d, e, f} ⊂ E(G).
(1)
v
1
v
2
v
3
v
4
v
5
v
6
v
7
a
b
cd
e
f
(2)
v
1
v
2
v
3
v
4
v
5
v
6
v
7
Figura 2.2: G e G\C
Proposi¸c˜ao 2.3 Se G ´e um grafo com δ(G) ≥ 2, ent˜ao G tem um circuito.
Demonstra¸c˜ao: Seja P um caminho de comprimento m´aximo em G com v sendo o
v´ertice inicial. Sab emos, por hip´otese, que d
G
(v) ≥ 2, logo v possui no m´ınimo duas
arestas incidentes, uma delas faz parte do caminho P e a outra tamb´em deve estar ligada a
outro v´ertice do caminho P , pois, caso contr´ario, existiria um caminho P
de comprimento
maior do que P . Portanto, G possui um circuito.
2.3 Conexidade e blocos
Dois v´ertices u e v de G est˜ao conectados se existe um caminho em G cujo v´ertice
inicial ´e u e o v´ertice terminal ´e v. Conectividade ´e uma rela¸c˜ao de equivalˆencia no
12
conjunto de v´ertices de G. Assim, existe uma parti¸c˜ao de V (G) em subconjuntos n˜ao-
vazios e disjuntos V
1
, V
2
, ..., V
l
tais que u e v s˜ao conectados se, e somente se, ambos u
e v pertencem ao mesmo conjunto V
i
. Os subgrafos G[V
1
], G[V
2
], ..., G[V
l
] s˜ao chamados
componentes conexas de G. Se G p ossui apenas uma componente conexa, ent˜ao dizemos
que G ´e conexo; caso contr´ario, G ´e desconexo. Denotaremos o n´umero de componentes
conexas de G por ω(G).
Se dois v´ertices u e v est˜ao conectados em um grafo G, definimos a distˆancia entre
u e v em G, d
G
(u, v), como sendo o menor comprimento dos uv-caminhos em G; caso n˜ao
exista caminho que conecte u e v, definimos d
G
(u, v) como sendo infinito.
Um v´ertice v de um grafo conexo G ´e separador se E(G) pode ser particionado em
dois subconjuntos E
1
e E
2
de E(G) tais que G[E
1
] e G[E
2
] tem somente o v´ertice v em
comum.
Um conjunto separador de um grafo conexo G ´e um subconjunto V
de V (G) tal
que G − V
´e desconexo. Um k-conjunto separador de G ´e um conjunto separador de G
com k elementos.
Entendemos por um grafo trivial, como sendo o grafo formado apenas por um ´unico
v´ertice.
Se G tem pelo menos um par de v´ertices n˜ao-adjacentes, a conexidade κ(G) de G
´e o menor k tal que G tem um k-conjunto separador; caso contr´ario, κ(G) ´e o n´umero de
v´ertices de G menos 1, ou seja, κ(G) = |V (G)| − 1. Como consequˆencia da defini¸c˜ao, se
G ´e trivial ou desconexo, ent˜ao κ(G) = 0. Dizemos que G ´e k-conexo se κ(G) ≥ k. Todos
os grafos conexos n˜ao-triviais s˜ao 1-conexo.
Proposi¸c˜ao 2.4 Se k ´e o menor n´umero de v´ertices que deve ser retirado para tornarmos
um grafo
G
desconexo, ent˜ao
G
´e
k
-conexo.
Demonstra¸c˜ao: Se k ´e o menor n´umero de v´ertices que deve ser retirado para tornarmos
o grafo G desconexo, ent˜ao G possui um k-conjunto separador e, portanto, κ(G) ≥ k
implicando G k-conexo.
Seja e uma aresta de um grafo G, dizemos que e ´e ponte quando ω(G − e) > ω(G).
Um grafo conexo que n˜ao possui v´ertices separadores ´e chamado de bloco. Um
bloco de um grafo simples G ´e um conjunto de arestas B ⊆ E(G) tal que B ´e uma ponte
13
ou um subgrafo maximal 2-conexo de G. Todo bloco com pelo menos trˆes v´ertices ´e
2-conexo.
Sejam G um grafo n˜ao-trivial e S e S
subconjuntos de V (G), onde S
= V (G)\S,
um subconjunto de arestas E
⊆ E(G) ´e chamado conjunto aresta-separador de G se cada
aresta de E
possui um extremo em S e o outro em S
. Se E
⊆ E(G) ´e um conjunto
aresta-separador, ent˜ao G − E
´e desconexo; caso E
= {e}, ent˜ao e ´e uma ponte do grafo
G. Um k-conjunto aresta-separador ´e um conjunto aresta-separador com k elementos.
Definimos a aresta conectividade de um grafo G, κ
(G), como sendo o menor k para o
qual G possui um k-conjunto aresta-separador. Se G ´e trivial, κ
(G) ´e, por defini¸c˜ao, zero.
Logo, pela defini¸c˜ao, κ
(G) ´e zero se G ´e trivial ou desconexo e, κ
(G) = 1 se G ´e um grafo
conexo com uma ponte. Dizemos que um grafo G ´e k-aresta-conexo quando κ
(G) ≥ k.
Todos os grafos n˜ao-triviais s˜ao 1-aresta-conexo.
Abaixo, resultados que caracterizam grafos 2-conexos. Alguns destes resultados
foram citados apenas para nos familiarizarmos com as teorias de 2-conexidade e blocos.
Lema 2.5 Seja G um grafo, ent˜ao κ(G) ≤ κ
(G) ≤ δ(G).
Lema 2.6 Uma aresta e de um grafo G ´e uma ponte de G se, e somente se, n˜ao existe
circuito de G que cont´em a aresta e.
Teorema 2.7 (Whitney, 1932) Um grafo G com |V (G)| ≥ 3 ´e 2-conexo se, e somente
se, quaisquer dois v´ertices de G est˜ao conectados por, pelo menos, dois caminhos internos-
disjuntos.
Demonstra¸c˜ao: (⇐) Suponhamos que quaisquer dois v´ertices de G est˜ao conectados
por, pelo menos, dois caminhos internos-disjuntos. Ent˜ao, G ´e conexo e n˜ao possui v´ertice
separador. Logo, G ´e 2-conexo, pois κ(G) ≥ 2.
(⇒) Provaremos por indu¸c˜ao sobre a distˆancia d
G
(u, v). Caso d
G
(u, v) = 1 e, sendo G
2-conexo, temos, pelo Lema 2.5, que a aresta uv n˜ao ´e uma ponte e, pelo Lema 2.6, uv
pertence a algum circuito de G. Logo, u e v est˜ao conectados por, pelo menos, dois
caminhos internamente-disjuntos.
Suponhamos d
G
(u, v) = k ≥ 2 e consideremos um uv-caminho de comprimento
k. Seja w o v´ertice que precede v neste caminho. Como d
G
(u, w) = k − 1, ent˜ao, pela
hip´otese indutiva, existem dois uw-caminhos internamente-disjuntos P e Q em G. Sendo
14
G 2-conexo, temos que G − w ´e conexo e cont´em um caminho P
que conecta u e v. Seja
x o ´ultimo v´ertice de P
que tamb´em est´a em P ∪ Q, existe a possibilidade x ser igual a
v.
Sem perda de generalidade, suponhamos x ∈ P . Logo, G possui dois caminhos
internamente-disjuntos que conectam u e v: um composto da se¸c˜ao de P de u a x junto
com a se¸c˜ao de P
de x para v e o outro composto de Q junto com o caminho wv.
Corol´ario 2.8 Seja G um grafo 2-conexo. Dados dois v´ertices quaisquer de G, existe um
circuito que os cont´em.
Corol´ario 2.9 Se G ´e um bloco com |V (G)| ≥ 3, ent˜ao quaisquer duas arestas de G
est˜ao em um mesmo circuito.
Dado um grafo G, dizemos que P ´e um G-caminho se P ´e um caminho n˜ao-trivial
e intercepta G exatamente nos seus v´ertices terminais.
Teorema 2.10 Um grafo ´e 2-conexo se, e somente se, pode ser constru´ıdo a partir de
um circuito pela adi¸c˜ao sucessiva de G-caminhos em grafos G previamente constru´ıdos.
Demonstra¸c˜ao: (⇐) Todo grafo constru´ıdo como descrito acima ´e 2-conexo, pois para
quaisquer dois v´ertices neste grafo, existe um circuito que os cont´em.
(⇒) Seja G um grafo 2-conexo. Ent˜ao, G cont´em um circuito e, portanto, tem um
subgrafo maximal H constru´ıdo como descrito no enunciado. Como qualquer aresta
xy ∈ E(G) − E(H) com x, y ∈ V (H) define um H-caminho, temos que H ´e um subgrafo
induzido de G. Assim, se H = G, ent˜ao, pela conexidade de G, existe uma aresta
vw ∈ E(G) tal que v ∈ V (G) − V (H) e w ∈ V (H). Sendo G 2-conexo, G − w ´e conexo e
cont´em um caminho P cujo v´ertice inicial ´e v e o ´unico v´ertice em comum com H ´e seu
v´ertice terminal. Logo, o caminho formado por P mais a aresta wv, denotado por wvP , ´e
um H-caminho em G e
˜
H = G[H ∪ wvP ] ´e um subgrafo de G, constru´ıdo como descrito
no enunciado, maior do que H, o que ´e uma contradi¸c˜ao.
Teorema 2.11 Seja w um v´ertice separador de um grafo G. Se H ´e um grafo conexo tal
que V (H) ∩ V (G) est´a contido em um ´unico bloco de G, ent˜ao w ´e v´ertice separador de
H ∪ G.
15
Demonstra¸c˜ao: Suponhamos, por absurdo, que w n˜ao seja v´ertice separador de H ∪ G.
Sejam B
o bloco de G tal que V (H) ∩ V (G) ⊂ V (B
), B um bloco de G tal que
V (B)\{w} est´a em uma componente conexa de G−w diferente da que cont´em V (B
)\{w}
e u ∈ V (B)\{w} e v ∈ V (B
)\{w}.
N˜ao existe uv-caminho em G − w, entretanto existe uv-caminho em (G ∪ H) − w.
Pelo menos uma das arestas do uv-caminho em ( G ∪ H) − w deve pertencer a H, caso
contr´ario u e v estariam na mesma componente conexa de G − w, uma contradi¸c˜ao. Seja
u
w
a primeira aresta no uv-caminho em (G ∪ H) − w que pertence a H com u
v´ertice
mais pr´oximo de u. Assim, existe um uu
-caminho contido em G − w, implicando que
u
∈ V (G), o que ´e uma contradi¸c˜ao, porque, neste caso, u
∈ V (H) ∩ (V (G) − V (B
)).
Portanto, w ´e v´ertice separador de G ∪ H.
As demonstra¸c˜oes dos resultados a seguir ser˜ao omitidas, as mesmas podem ser
encontradas na disserta¸c˜ao de Oliveira [6], mais precisamente na se¸c˜ao 1.3, intitulada A
´
Arvore dos Blocos.
Lema 2.12 Sejam G um grafo e X e Y subconjuntos de E(G) tais que |V (X)∩V (Y )| ≥ 2.
Se G[X] e G[Y ] s˜ao 2-conexos, ent˜ao G[X ∪ Y ] ´e 2-conexo.
Lema 2.13 Dois blocos quaisquer em um grafo possuem, no m´aximo, um v´ertice em
comum.
Lema 2.14 Se G ´e um grafo conexo e v ´e um v´ertice separador de G, ent˜ao v ´e incidente
a pelo menos dois blocos de G.
Lema 2.15 Seja G um grafo conexo. Se B e B
s˜ao blocos distintos de G tais que
min{|V (B)|, |V (B
)|} ≥ 2 e v ∈ V (B) ∩ V (B
),
ent˜ao v ´e v´ertice separador de G.
Para um grafo conexo G, vamos associar um grafo T
, conhecido como a ´arvore
dos blocos de G, tendo como conjunto de v´ertices
V (T
) = {B ⊆ E(G); B ´e bloco de G} ∪ {v ∈ V (G); v ´e v´ertice separador de G}
e como arestas o conjunto
E(T
) = {vB; v ´e v´ertice separador de G, B ´e um bloco de G e v ∈ V (B)}.
16
Lema 2.16 T
´e uma ´arvore.
Teorema 2.17 Sejam G um grafo 2-conexo e e uma aresta de G. Se G − e n˜ao ´e 2-
conexo, ent˜ao a ´arvore dos blocos de G − e ´e um caminho e a aresta e liga v´ertices n˜ao
separadores dos blocos terminais.
2.4 Ordem lexicogr´afica
No conjunto N × N × ... × N = N
n
podemos definir v´arias ´ordens totais, em
particular, temos uma chamada de ordem lexicogr´afica, a qual ´e definida da seguinte
maneira: para α = (a
1
, a
2
, ..., a
n
) e β = (b
1
, b
2
, ..., b
n
) pertencentes a N
n
, dizemos que
α < β quando a
i
< b
i
para o primeiro ´ındice i com a
i
= b
i
. Por exemplo, para
α = (9, 2, 12, 3), β = (9, 2, 5, 10) ∈ N
4
, temos que α > β, pois o primeiro ´ındice i tal
que a
i
= b
i
´e i = 3 e a
3
= 12 > 5 = b
3
. Nesta disserta¸c˜ao, iremos utilizar a ordem
lexicogr´afica apenas para o caso N × N = N
2
.
Cap´ıtulo 3
Demonstra¸c˜ao do Teorema de Lemos
e Oxley
Com o intu´ıto de facilitar o acompanhamento da demonstra¸c˜ao do Teorema 1.2,
destacamos trˆes se¸c˜oes: G\ C ´e conexo, redu¸c˜ao ao caso que |E(H)| = 1 e quando E(H)
´e vazio.
O final da prova de cada Afirma¸c˜ao, que aparece no decorrer do texto, ´e demarcado
com um quadrado branco: ✷.
Antes, vejamos dois Lemas:
Lema 3.1 (Egawa e Miyamoto, 1989) Seja G um grafo simples 2-conexo e A um
subconjunto n˜ao-vazio de V (G). Assumimos que d
G
(x) + d
G
(y) ≥ m para todo par de
v´ertices distintos e n˜ao-adjacentes em V (G)\A. Ent˜ao,
1. G tem um circuito de comprimento no m´ınimo m − |A | + 1; ou
2. G tem um circuito que cont´em todos os v´ertices de V (G)\A e, pelo menos, um
v´ertice de A.
Lema 3.2 Seja G um grafo simples 2-conexo e seja u um v´ertice de G tal que d
G
(v) ≥ k
para todo v em V (G)\{u} e algum k ≥ 3. Ent˜ao,
1. G tem um circuito de comprimento, no m´ınimo, k + 1; e
2. G tem um circuito de comprimento, no m´ınimo, k + 3 a menos que G
∼
=
K
k+1
, ou
G
∼
=
K
k+2
\(T ∪ S), onde T ´e um emparelhamento, S um subconjunto de v´ertice
estrela e cont´em, no m´aximo, k − 1 arestas e V (T ) ∩ V (S) = ∅
18
Agora, vamos a demonstra¸c˜ao do Teorema de Lemos e Oxley.
Demonstra¸c˜ao do Teorema 1.2: Primeiro, consideraremos o caso que |E(H)| ≥ 1, ou
seja, o bloco H possui pelo menos uma aresta. Assumiremos que o Teorema 1.2 falhe e seja
G um contra-exemplo escolhido de tal forma que |E(G)| ´e minimal e |E(H)| ´e maximal.
Esclarecemos que, sendo |E(H)| maximal, temos −|E(H)| minimal e, portanto, o par
(|E(G)|, −|E(H)|) ´e minimal.
Seja C um circuito de G tal que C ´e aresta-disjunta de H e G\C n˜ao ´e 2-conexo.
Quando k ≥ 5, escolhemos C com |C| ≥ k + 1 se tal escolha ´e poss´ıvel sobre as condi¸c˜oes
previamente impostas. Sendo H 2-conexo, em G\C existe um ´unico bloco B que cont´em
E(H).
Afirma¸c˜ao 3.3 B = H
Se B = H, ent˜ao, como B cont´em E(H), temos que |E(B)| > |E(H)| e, pela
ordem lexicogr´afica, (|E(G)|, −|E(B)|) < (|E(G)|, −|E(H)|). Logo, devido a escolha de
H, o resultado deve valer para o par (G, B). J´a sabemos que G\C n˜ao ´e 2-conexo, assim,
(i) falha para (G, B), ent˜ao (ii) tem que valer. Logo, existe C
tal que G\C
´e 2-conexo e
C
´e aresta-disjunta de B, mas E(B) ⊇ E(H) e o resultado valer´a para o par (G, H), o
que ´e absurdo. Portanto, s´o nos resta a op¸c˜ao de que B = H. ✷
Um bloco B
de um grafo ´e especial se B
cont´em, no m´aximo, um v´ertice separador
do grafo.
Afirma¸c˜ao 3.4 Todo bloco especial B
de G\C que ´e distinto de B cont´em um circuito.
Seja C
B
o circuito de comprimento m´aximo. Ent˜ao, quando k ≥ 5, uma das seguintes
propriedades vale
(3.4.1) |C
B
| ≥ k + 1; ou
(3.4.2) B
∼
=
K
k−1
; ou
(3.4.3) B
∼
=
K
k
\(T ∪ S) para algum emparelhamento T e algum subconjunto S de uma
estrela de algum v´ertice tal que |S| ≤ k − 3 e V (S) ∩ V (T ) = ∅
A exclus˜ao das arestas de C em G reduz o grau de cada v´ertice por no m´aximo 2.
Assim, todo v´ertice de B
que n˜ao ´e um v´ertice separador de G\C est´a em V (G) − V (H)
19
e tem grau pelo menos k − 2, que ´e maior ou igual a 2 em B
, pois k > 3. Portanto, pela
Proposi¸c˜ao 2.3, B
cont´em um circuito.
Seja u o v´ertice separador de G\C que est´a em B
. Ent˜ao, k ≥ 5, implica que,
quando excluimos as arestas de C, temos d
B
(v) ≥ k − 2 ≥ 3, ∀v ∈ V (B
) − {u}, e, pelo
Lema 3.2,
1. |C
B
| ≥ (k − 2) + 3 = k + 1; ou
2. B
∼
=
K
(k−2)+1
= K
k−1
; ou
3. B
∼
=
K
(k−2)+2
\(T ∪ S) = K
k
\(T ∪ S), para algum emparelhamento T e algum
subconjunto S de algum v´ertice estrela tal que |S| ≤ (k − 2) − 1 = k − 3 e
V (S) ∩ V (T ) = ∅. ✷
3.1 G\C ´e conexo
Com o aux´ılio da Afirma¸c˜ao 3.4, iremos provar a seguinte afirma¸c˜ao.
Afirma¸c˜ao 3.5 G\C ´e conexo.
Observa¸c˜ao 3.6 Os v´ertices do circuito C interceptam todas as componentes conexas de
G\C. Al´em disso, para que G seja 2-conexo, os v´ertices do circuito C devem interceptar,
pelo menos, dois v´ertices de cada componente conexa de G\C.
Suponhamos, por absurdo, que G\C n˜ao ´e conexo. Sejam D a componente conexa
de G\C que cont´em E(H), G
= G[E(D) ∪ C] e D

uma componente conexa distinta de
D. Sendo H bloco de G\C, implica H bloco da componente conexa D. Se H continua
sendo bloco de G
, ent˜ao C est´a em outro bloco de G
, caso contr´ario, H sendo subgrafo
2-conexo maximal de G
, teriamos que C estaria completamente contido em H, o que ´e
absurdo, pois E(H) ∩ C = ∅. Logo, H sendo bloco de G
e C estando em outro bloco de
G
, temos que G
possui, no m´ınimo, um v´ertice separador. Desta forma, quando unimos
G
a D

, temos, pelo Teorema 2.11, que todo v´ertice separador de G
continua sendo
v´ertice separador de G[G
∪ D

], logo repetindo este procedimento, ou seja, acrescentando
as demais componentes conexas, concluiremos que G possui um v´ertice separador, o que
´e uma contradi¸c˜ao, pois G ´e 2-conexo. Portanto, H est´a contido em bloco maior de G
,
20
digamos B
1
, e C tamb´em est´a neste bloco B
1
, se n˜ao, concluiriamos da mesma forma que
G possui, pelo menos, um v´ertice separador.
Escolhemos uma aresta e de H e uma aresta f de C, como C e H est˜ao no mesmo
bloco B
1
de G
, existe, pelo Corol´ario 2.9, um circuito C
1
em B
1
que cont´em as arestas e
e f. Este circuito C
1
cont´em arestas de H e C. Sendo assim, C
1
cont´em um caminho P
0
tal que P
0
est´a contido em C e os ´unicos v´ertices em comum com a componente conexa
D s˜ao seus v´ertices terminais v
1
e v
2
. Olhando para o peda¸co do circuito C
1
que est´a em
D, temos que este peda¸co ´e um caminho P
3
em D que intercepta E(H) e tem extremos
v
1
e v
2
.
Consideremos B
um bloco especial em uma componente conexa D
de G\C
diferente da componente conexa D e suponhamos k = 4, ou k ≥ 5 e (3.4.1) vale. Devido
ao fato do bloco B
pertencer a uma componente conexa D
diferente de D, o circuito
C
B
´e aresta-disjunto de H. Assim, como (ii) do Teorema 1.2 falha, temos que G\C
B
n˜ao ´e 2-conexo e G\C
B
tem um ´unico bloco que cont´em H. Este bloco tamb´em cont´em
E(H) ∪ P
0
, contrariando o fato de H ser maximal. Portanto, a condi¸c˜ao (3.4.1) n˜ao pode
ocorrer.
Afirma¸c˜ao 3.7 Seja J um subgrafo conexo de uma componente conexa de G\C diferente
da que cont´em E(H), ou seja, diferente da componente conexa D. Ent˜ao, G n˜ao tem
circuito C
que satisfaz todas as condi¸c˜oes a seguir:
(i) C
⊆ E(J) ∪ C;
(ii) v
1
e v
2
est˜ao na mesma componente conexa de G[E(J) ∪ C]\C
; e
(iii) |C
| ≥ k + 1, quando k ≥ 5.
Suponhamos, por absurdo, que exista um circuito C
satisfazendo a todas estas
condi¸c˜oes. Ent˜ao, como (ii) do Teorema 1.2 falha, G\C
n˜ao ´e 2-conexo e G\C
tem
um ´unico bloco que cont´em H. O fato de, por hip´otese, v
1
e v
2
pertencerem `a mesma
componente conexa de G[E(J) ∪ C]\C
, implica que existe um caminho ligando v
1
e v
2
e
este caminho ´e aresta-disjunta do caminho P
3
que est´a na componente conexa D. Assim,
pela constru¸c˜ao destes dois caminhos, a uni˜ao deles cont´em um circuito C
2
que encontra
E(H) e E(G) − E(H). O circuito C
2
est´a em G\C
e, portanto, o bloco de G\C
que
21
cont´em E(H) tamb´em cont´em E(H) ∪ C
2
implicando que este bloco tem mais do que
|E(H)| arestas, o que ´e uma contradi¸c˜ao `a maximilidade de E(H). ✷
Seja B
um bloco especial de G\C. O circuito C induz uma ordem c´ıclica, a qual
chamaremos de ordem C-induzida, nos v´ertices de V (B
) ∩ V (C). Um caminho em C
que une dois v´ertices consecutivos em V (B
) ∩ V (C) ´e chamado de B
-segmento de C, ou
simplesmente o chamaremos de B
-segmento.
Consideraremos o caso que k ≥ 5 e (3.4.2) vale, provaremos que, nestas condi¸c˜oes,
a seguinte afirma¸c˜ao ´e v´alida.
Afirma¸c˜ao 3.8 Se B
´e um bloco especial de uma componente conexa de G\C diferente
da componente conexa que cont´em E(H) e B
∼
=
K
k−1
, ent˜ao k = 5, o bloco B
cont´em
um v´ertice separador de G\C que n˜ao ´e v´ertice de C e v
1
e v
2
est˜ao em B
-segmentos
diferentes de C.
O bloco B
de G\C cont´em, no m´aximo, um v´ertice separador de G\C. Como
B
∼
=
K
k−1
, todo v´ertice de B
que n˜ao ´e v´ertice separador de G\C tem grau k−2 em G\C,
mas, por hip´otese, tem grau, pelo menos, k em G, logo, os v´ertices de B
, com a poss´ıvel
exce¸c˜ao do v´ertice separador, devem pertencer a C, portanto |V (B
) ∩ V (C)| ≥ k − 2.
Como |V (B
) ∩ V (C)| ≥ k − 2, existem, pelo menos, k − 2 B
-segmentos. Al´em
disso, sendo B
completo e G simples, todo B
-segmento de C tem comprimento, pelo
menos, dois. Desta maneira, uma das duas condi¸c˜oes abaixo ´e satisfeita,
(a) existem dois B
-segmentos distintos de C, P
1
e P
2
, que n˜ao passam por {v
1
, v
2
}; ou
(b) estes dois B
-segmentos n˜ao existem.
No caso (a), seja P
i
um caminho com u
i
e w
i
sendo seus v´ertices terminais. Ent˜ao,
assumimos que u
1
∈ {u
2
, w
2
} e w
1
= w
2
. Como B
´e completo, ent˜ao B
cont´em
caminhos v´ertices-disjuntos R
1
e R
2
unindo u
1
e w
2
e u
2
e w
1
, respectivamente, tais
que V (R
1
) ∪ V (R
2
) = V (B
). A uni˜ao de R
1
, P
1
, R
2
e P
2
´e um circuito C
que est´a em
E(B
) ∪ C e cont´em, pelo menos, (k − 1) + 2 v´ertices, implicando |C
| ≥ k + 1. Al´em
disso, como P
1
∪ {u
1
w
1
} ´e um circuito, u
1
w
1
∈ E(C
). Segue que, em G[E(B
) ∪ C]\C
, os
v´ertices v
1
e v
2
est˜ao na mesma componente conexa, Figura 3.1. Portanto, encontramos
um circuito C
que satisfaz as condi¸c˜oes (i), (ii) e (iii) da Afirma¸c˜ao 3.7, o que ´e um
22
absurdo. Logo, o caso (a) n˜ao pode ocorrer, ou seja, n˜ao existem dois B
-segmentos que
evitam {v
1
, v
2
}.
v
1
v
2
w
2
u
2
w
1
u
1
u
1
w
1
R
1
R
2
P
2
P
1
Figura 3.1: v
1
e v
2
est˜ao na mesma componente conexa
Sendo assim, o caso (b) deve ser v´alido. Como k ≥ 5, para que n˜ao existam dois
B
-segmentos que evitam {v
1
, v
2
}, k deve ser igual a 5, B
cont´em um v´ertice separador
de G\C que n˜ao ´e v´ertice de C, implicando que |V (B
) ∩ V (C)| = 3, v
1
e v
2
devem estar
em B
-segmentos diferentes de C e existe apenas um B
-segmento que evita {v
1
, v
2
}. ✷
A Afirma¸c˜ao 3.8 ser´a utilizada mais adiante para concluirmos que G\C deve ser
conexo.
Suponhamos que k ≥ 5 e (3.4.3) vale, que ´e B
∼
=
K
k
\(T ∪ S) onde T ´e um
conjunto de arestas, S um conjunto de, no m´aximo, k − 3 arestas, todas dividindo um
v´ertice em comum, v
S
, e as arestas de S s˜ao v´ertices disjuntos dos v´ertices de T . Neste
caso, usaremos a seguinte afirma¸c˜ao.
Afirma¸c˜ao 3.9 Se w
1
e w
2
s˜ao v´ertices distintos de B
, ent˜ao existe um caminho
Hamiltoniano unindo w
1
e w
2
, a menos que |S| = k − 3 e v
S
w
1
e v
S
w
2
sejam as ´unicas
arestas incidentes a v
S
que n˜ao est˜ao em S.
Observa¸c˜ao 3.10 Como |S| ´e menor ou igual a k − 3, temos que o grau de v
S
´e, no
m´ınimo, dois em B
, d
B
(v
S
) ≥ 2, ou seja, existem, pelo menos, dois v´ertices adjacentes
a v
S
em B
∼
=
K
k
\(T ∪ S).
Observa¸c˜ao 3.11 Seja v ∈ V (B
). Pelo fato de V (S) ∩ V (T ) = ∅, temos as seguintes
conclus˜oes, se a aresta v
S
v existe, ou seja, v
S
v ∈ E(B
), ent˜ao v pode n˜ao ser adjacente
a um outro v´ertice de B
; se a aresta v
S
v n˜ao existe, ent˜ao, com exce¸c˜ao do v´ertice v
S
, v
´e adjacente a todos os v´ertices de B
.
23
A demonstra¸c˜ao da Afirma¸c˜ao 3.9 ser´a feita por indu¸c˜ao sobre k. Para
k = 5, consideraremos primeiro o caso que v
S
∈ {w
1
, w
2
}, seja V (B
) =
{w
1
, w
2
, v
S
, a, b}. Se as arestas w
1
v
S
e w
2
v
S
n˜ao pertencem a E(B
), ent˜ao as arestas
w
1
a, w
1
b, w
1
w
2
, w
2
a, w
2
b, v
S
a, v
S
b ∈ E(B
), implicando que w
1
av
S
bw
2
´e um w
1
w
2
-caminho
Hamiltoniano em B
.
Se a aresta w
1
v
S
∈ E(B
), mas w
2
v
S
, v
S
a ∈ E(B
), ent˜ao caso ab ∈ E(B
),
temos que w
1
bav
S
w
2
´e um w
1
w
2
-caminho Hamiltoniano em B
; caso ab ∈ E(B
), ent˜ao
v
S
b, bw
2
∈ E(B
) e w
1
av
S
bw
2
´e um w
1
w
2
-caminho Hamiltoniano em B
. O caso de
w
1
v
S
∈ E(B
), mas w
2
v
S
∈ E(B
) ´e an´alogo.
Consideremos o caso que w
1
v
S
, w
2
v
S
∈ E(B
). Se |S| = 2, ent˜ao n˜ao existe w
1
w
2
-
caminho Hamiltoniano em B
. Se |S| < 2, ent˜ao d
B
(v
S
) ≥ 3 e, portanto, v
S
a ou v
S
b
pertence a E(B
). Digamos que v
S
a ∈ E(B
). Se w
1
a ∈ E(B
), ent˜ao w
1
w
2
ab, w
1
b ∈ E(B
)
e w
1
bav
S
w
2
´e um w
1
w
2
-caminho Hamiltoniano em B
. Se w
1
w
2
, w
1
a ∈ E(B
), ent˜ao
ab, ou w
2
b, n˜ao pertence a E(B
); caso ab ∈ E(B
), temos que w
2
b, v
S
b ∈ E(B
)
e w
1
av
S
bw
2
´e um w
1
w
2
-caminho Hamiltoniano em B
; caso w
2
b ∈ E(B
), temos que
v
S
b, ab ∈ E(B
) e w
1
abv
S
w
2
´e um w
1
w
2
-caminho Hamiltoniano em B
. Se w
1
w
2
∈ E(B
),
ent˜ao w
1
a, w
1
b, w
2
a, w
2
b ∈ E(B
) e ab, ou v
S
b, n˜ao pertence a E(B
); caso ab ∈ E(B
),
temos que v
S
b ∈ E(B
) e w
1
bv
S
aw
2
´e um w
1
w
2
-caminho Hamiltoniano em B
; caso
v
S
b ∈ E(B
), temos que ab ∈ E(B
) e w
1
bav
S
w
2
´e um w
1
w
2
-caminho Hamiltoniano em
B
. Encerramos o caso que v
S
∈ {w
1
, w
2
}.
Consideremos v
S
∈ {w
1
, w
2
}, digamos w
1
= v
S
, e seja V (B
) = {w
1
, w
2
, a, b, c}.
Suponhamos |S| = 2. Se w
1
w
2
, w
1
a ∈ E(B
), ent˜ao w
1
b, w
1
c ∈ E(B
), mas ab, bc, w
2
c ∈
E(B
), implicando que w
1
abcw
2
´e um w
1
w
2
-caminho Hamiltoniano em B
. Se w
1
w
2
∈
E(B
), ent˜ao w
1
a, w
1
b, w
2
a, w
2
b, w
2
c, ac, bc ∈ E(B
) e, portanto, w
1
acbw
2
´e um w
1
w
2
-
caminho Hamiltoniano em B
.
Suponhamos |S| < 2, ent˜ao, d
B
(w
1
) ≥ 3, digamos, que w
1
a, w
1
b ∈ E(B
). Se
w
1
w
2
∈ E(B
), ent˜ao w
1
c, w
2
a, w
2
b, w
2
c ∈ E(B
) e ab, ou bc, ou ac, pode n˜ao pertencer
a E(B
). Se ab ∈ E(B
), temos que bc, ac ∈ E(B
) e w
1
bcaw
2
´e um w
1
w
2
-caminho
Hamiltoniano em B
; o caso que bc, ou ac, n˜ao pertence a E(B
) ´e an´alogo.
Ainda supondo que |S| < 2, digamos que, desta vez, w
1
w
2
∈ E(B
), al´em de w
1
a
e w
1
b. Se ab ∈ E(B
) e w
1
c ∈ E(B
), ent˜ao w
1
abcw
2
´e um w
1
w
2
-caminho Hamiltoniano
em B
. Se ab ∈ E(B
), temos que bc, w
2
b, ac ∈ E(B
) e w
1
acbw
2
´e um w
1
w
2
-caminho
24
Hamiltoniano em B
.
Suponhamos que w
1
w
2
, w
1
a, w
1
b, w
1
c ∈ E(B
). Se aw
2
∈ E(B
), ent˜ao w
1
bacw
2
´e
um w
1
w
2
-caminho Hamiltoniano em B
. Se aw
2
∈ E(B
), ent˜ao ac, ou ab, ou cw
2
, ou
bw
2
, n˜ao pertence a E(B
); caso ac ∈ E(B
), ent˜ao ab, bc, cw
2
∈ E(B
) e w
1
abcw
2
´e um
w
1
w
2
-caminho Hamiltoniano em B
; o caso que ab, ou bc, ou cw
2
, n˜ao pertence a E(B
)
´e an´alogo. Concluimos o caso que k = 5.
Agora, consideraremos k > 5. Se |S| = k − 3 e v
S
w
1
, v
S
w
2
∈ E(B
), ent˜ao n˜ao ´e
poss´ıvel construir um w
1
w
2
-caminho Hamiltoniano em B
. Caso contr´ario, retiramos um
v´ertice v diferente de w
1
, w
2
e v
S
e obtemos o grafo K
k−1
\(T
∪S
), onde T
e S
s˜ao obtidos
a partir de T e S, respectivamente. Pela hip´otese indutiva, existe um w
1
w
2
-caminho
Hamiltoniano, P
4
, em K
k−1
\(T
∪ S
). Colocamos de volta o v´ertice v e recuperamos o
grafo B
∼
=
K
k
\(T ∪ S). Resta encaixarmos o v´ertice v no caminho P
4
para obtermos um
w
1
w
2
-caminho Hamiltoniano em B
. Escolhemos duas arestas em sequˆencia no caminho
P
4
, ab e bc. Existe a possibilidade de a = w
1
, b = v
S
e c = w
2
; o caso que a = v
S
, implica
que a = w
1
= v
S
e; o caso que c = v
S
, implica que c = w
2
= v
S
.
Se av, bv ∈ E(B
), ent˜ao adicionamos as arestas av e bv e removemos a aresta ab
do caminho P
4
, obtendo um w
1
w
2
-caminho Hamiltoniano em B
.
Caso av ∈ E(B
), ent˜ao, pela Observa¸c˜ao 3.11, cv, bv ∈ E(B
) e, com estas arestas,
fazemos um procedimento an´alogo ao descrito no par´agrafo anterior. Se bv ∈ E(B
), ent˜ao
pegamos o outro v´ertice adjacente a c em P
4
, d, adicionamos as arestas cv e dv, retiramos
a aresta cd do caminho P
4
e obtemos um w
1
w
2
-caminho Hamiltoniano em B
. ✷
Como todo v´ertice v em V (G) − V (H) deve ter grau maior ou igual a k, ent˜ao
todo v´ertice de B
, com a poss´ıvel exce¸c˜ao do v´ertice separador, ´e tamb´em v´ertice de
C, desta forma, |V (B
) ∩ V (C)| ≥ k − 1. Assim, o n´umero de B
-segmentos de C ´e k
ou k − 1 e, por conta disto, para alguns v´ertices distintos w
1
e w
2
em V (B
) ∩ V (C),
existe um B
-segmento C[w
1
, w
2
] de C com extremos w
1
e w
2
tal que C[w
1
, w
2
] n˜ao passa
por v
1
e v
2
. Escolha tal B
-segmento de tal maneira que seu comprimento ´e m´aximo e,
depois, escolha um caminho de comprimento m´aximo B
[w
1
, w
2
] em B
ligando w
1
e w
2
.
Ent˜ao, a uni˜ao de B
[w
1
, w
2
] e C[w
1
, w
2
] ´e um circuito C
⊆ E(B
) ∪ C e v
1
e v
2
est˜ao na
mesma componente conexa de G[E(B
) ∪ C]\C
, Figura 3.2. Teremos uma contradi¸c˜ao
`a Afirma¸c˜ao 3.7 a menos que |C
| seja menor ou igual a k. Iremos analisar este caso
excepcional. Ent˜ao, quando |C
| ≤ k, uma das duas condi¸c˜oes acontece:
25
v
1
v
2
w
1
w
2
C[w
1
, w
2
]
B
[w
1
, w
2
]
Figura 3.2: Constru¸c˜ao do circuito C
(a) C[w
1
, w
2
] tem comprimento pelo menos dois, |C[w
1
, w
2
]| ≥ 2; ou
(b) C[w
1
, w
2
] tem comprimento um, |C[w
1
, w
2
]| = 1 < 2.
Suponhamos que a condi¸c˜ao (a) vale. Ent˜ao, B
[w
1
, w
2
] n˜ao pode ser um caminho
Hamiltoniano em B
. Se B
[w
1
, w
2
] fosse um caminho Hamiltoniano em B
, ent˜ao C
teria comprimento maior ou igual a k + 1, contradizendo as condi¸c˜oes (i), (ii) e (iii) da
Afirma¸c˜ao 3.7. Logo, pela Afirma¸c˜ao 3.9, w
1
e w
2
s˜ao os ´unicos v´ertices que est˜ao ligados
a v
S
em B
.
Observa¸c˜ao 3.12 Ainda pela Afirma¸c˜ao 3.9, para todo B
-segmento C[u
1
, u
2
] que n˜ao
passa por v
1
e v
2
e ´e diferente de C[w
1
, w
2
], o caminho de comprimento m´aximo B
[u
1
, u
2
]
em B
com extremos u
1
e u
2
´e Hamiltoniano. Assim, C[u
1
, u
2
] tem somente uma aresta,
porque, caso contr´ario, a uni˜ao B
[u
1
, u
2
] com C[u
1
, u
2
] ´e um circuito C
3
satisfazendo
|C
3
| ≥ k + 1, C
3
⊆ E(B
) ∪ C e v
1
e v
2
est˜ao na mesma componente conexa de
G[E(B
) ∪ C]\C
3
, o que contradiz a Afirma¸c˜ao 3.7.
Observa¸c˜ao 3.13 Como B
∼
=
K
k
\(T ∪ S), onde T = {w
1
w
2
} ou T = ∅, ent˜ao B
−{v
S
}
´e um grafo completo ou um grafo completo com a aresta w
1
w
2
deletada, segue que os
´unicos B
-segmentos de C de comprimento um devem interceptar v
S
.
Observa¸c˜ao 3.14 Se existem, pelo menos, trˆes B
-segmentos diferentes de C[w
1
, w
2
] que
n˜ao passam por
v
S
, ent˜ao, existe, no m´ınimo, um
B
-segmento que evita
{
v
1
, v
2
}
. Pela
Observa¸c˜ao 3.12, este B
-segmento deve ter comprimento um e, pela Observa¸c˜ao 3.13,
deve interceptar v
S
, o que ´e uma contradi¸c˜ao. Portanto, existem, no m´aximo, dois B
-
segmentos de comprimento maior ou igual a dois, diferentes de C[w
1
, w
2
] e que n˜ao passam
por v
S
.
26
Contando com C[w
1
, w
2
], existem, no m´aximo, trˆes B
-segmentos distintos com
comprimento maior ou igual a dois. Ora, existem, pelo menos, k − 1 B
-segmentos, sendo
assim, os k − 1 − 3, ou k − 3, B
-segmentos restantes devem ter comprimento um e, pela
Observa¸c˜ao 3.13, todos devem passar por v
S
, logo v
S
deve pertencer a V (C).
Lembrando que, como |S| = k − 3, w
1
e w
2
s˜ao os ´unicos v´ertices adjacentes a v
S
em B
e k ≥ 5, temos que d
B
(v
S
) = 2. Se v
S
n˜ao ´e o v´ertice separador de B
, ent˜ao,
como C s´o acrescenta mais duas arestas incidentes a v
S
, teremos, no grafo original, que
d
G
(v
S
) = 4 ≤ 5 ≤ k, uma contradi¸c˜ao. Logo, v
S
deve ser o v´ertice separador de B
.
Pela Observa¸c˜ao 3.14 e o par´agrafo anterior, k n˜ao pode ser maior que 5, pois, neste
caso, existir˜ao, pelo menos, trˆes B
-segmentos distintos de C[w
1
, w
2
] que n˜ao passam por
v
S
.
Resumindo, devemos assumir que v
S
∈ V (C) e k = 5. Portanto, existem quatro
B
-segmentos diferentes de C[w
1
, w
2
]. Destes, no m´aximo um cont´em v
1
, no m´aximo
um cont´em v
2
e no m´aximo dois tem comprimento um. Para satisfazer as condi¸c˜oes
descritas nas Observa¸c˜oes 3.12, 3.13 e 3.14, a igualdade deve valer em cada um destes
limites, ou seja, existem um B
-segmento que cont´em v
1
, um outro contendo v
2
e dois de
comprimento um. Logo, B
´e igual ao grafo da Figura 3.3. Al´em disso, v
S
a e v
S
b est˜ao
em C e, sem perda de generalidade, determinamos a ordem C-induzida em V (B
) como
sendo w
1
, w
2
, a, v
S
, b. Ent˜ao, v
1
e v
2
est˜ao, em alguma ordem, nos B
-segmentos C[w
2
, a] e
C[b, w
1
]. Seja C
a uni˜ao de C[w
1
, w
2
] com o caminho w
1
bv
S
aw
2
em G[E(B
) ∪ C], vemos
que C
tem comprimento seis, o que contradiz a Afirma¸c˜ao 3.7. Isto exclui o caso (a).
a b
w
2
v
S
w
1
Figura 3.3: B
Suponhamos que a condi¸c˜ao (b) vale, ent˜ao temos que w
1
w
2
∈ T e tamb´em
w
1
w
2
∈ C. Pela Observa¸c˜ao 3.11, as arestas w
1
v
S
e w
2
v
S
pertencem a B
. Pela Afirma¸c˜ao
27
3.9, temos que para todo B
-segmento C[u
1
, u
2
] que n˜ao passa por v
1
e v
2
, o caminho
de comprimento m´aximo B
[u
1
, u
2
] ´e Hamiltoniano, ent˜ao C[u
1
, u
2
] deve ter comprimento
um. Como B
−{v
S
} ´e um grafo completo menos um emparelhamento, dois B
-segmentos
de C consecutivos podem ter comprimento um somente se ambos interceptam o v´ertice
v
S
, sendo assim, s´o existem, no m´aximo, dois B
-segmentos consecutivos de comprimento
um. Para satisfazer a estas condi¸c˜oes, segue que k = 5. Se v
S
∈ V (C), ent˜ao B
´e como na
Figura 3.4(1), onde as arestas 12 e 34 est˜ao em C, os v´ertices v
1
e v
2
est˜ao em diferentes
B
-segmentos de C e v
S
, para satisfazer d
G
(v
S
) ≥ 5 = k, ´e um v´ertice separador de G\C.
Se v
S
∈ V (C), ent˜ao existem v´ertices 3 e 4 de B
tais que v
S
3 e v
S
4 s˜ao arestas de C e,
consequentemente, n˜ao s˜ao arestas de B
. Al´em disso, para que d
G
(v
S
) seja maior ou igual
a cinco, v
S
deve ser um v´ertice separador de G\C. Logo, B
´e como mostrado na Figura
3.4(2), onde 12 ∈ C e, mais uma vez, v
1
e v
2
est˜ao em diferentes B
-segmentos de C.
3 4
2
v
S
1
(1)
3 4
2
v
S
1
(2)
Figura 3.4: B
Mostraremos que, se (2) vale, ent˜ao podemos modificar C e B
de tal forma que
(1) em detrimento de (2) valha. Para tanto, basta trocar C por C
1
e B
por B
1
, onde
C
1
= (C ∪ {34}) − {v
S
3, v
S
4}, V (B
1
) = V (B) e E(B
1
) = (E(B
) − {34}) ∪ {v
S
3, v
S
4}.
Ent˜ao, C
1
´e um circuito tendo, pelo menos, seis arestas, pois C
1
cont´em os B
-segmentos
C[2, 4], C[3, 1], C[1, 2] e C[3, 4] com |C[2, 4]| ≥ 2 e |C[3, 1]| ≥ 2. Os conjuntos de v´ertices
das componentes e blocos de G\C
1
e G\C s˜ao idˆenticos.
Combinando a Afirma¸c˜ao 3.8 com o resultado do ´ultimo par´agrafo, deduzimos que
se G\C ´e desconexo, ent˜ao k = 5 e devemos assumir que, para todo bloco especial B
de
G\C que est´a em uma componente conexa diferente de E(B), as seguintes afirma¸c˜oes s˜ao
verdadeiras:
(i) B
cont´em v´ertice separador u de G\C e {u} = V (B
) − V (C); e
28
(ii) B
´e um grafo completo de quatro v´ertices, ou o grafo obtido do grafo completo de
cinco v´ertices pela exclus˜ao de duas arestas emparelhadas, onde ambas arestas est˜ao
em C; e
(iii) v
1
e v
2
est˜ao em diferentes B
-segmentos de C.
Ent˜ao, (i) garante que podemos escolher blocos especiais B
1
e B
2
distintos que
est˜ao na mesma componente conexa D

de G\C com E(D

) ∩ E(B) = ∅. Por (iii),
ambos os caminhos que ligam v
1
e v
2
em C cont´em v´ertices de ambos B
1
e B
2
. Assim,
C cont´em um caminho P ligando um v´ertice x
1
de V (B
1
) a um v´ertice x
2
de V (B
2
) que
evita {v
1
, v
2
} e ´e internamente disjunto de ambos V (B
1
) e V (B
2
). Para i ∈ {1, 2}, existe
um caminho Hamiltoniano P
i
em B
i
de x
i
ao v´ertice separador u
i
de G\C que est´a em
B
i
. Seja G
1
a uni˜ao de P, P
1
, P
2
e um caminho Q em D

ligando u
1
e u
2
. Ent˜ao G
1
cont´em um circuito C
1
cujo conjunto de arestas cont´em propriamente E(P
1
). Al´em disso,
v
1
e v
2
est˜ao na mesma componente conexa de G[E(D

) ∪ C]\C
1
. Assim, temos uma
contradi¸c˜ao `a Afirma¸c˜ao 3.7 a menos que |C
1
| = 5 e B
1
∼
=
K
4
. No caso excepcional,
V (C
1
) = V (B
1
) ∪ {y
1
}, onde u
1
y
1
∈ E(D

) e y
1
∈ V (P ) ∩ V (Q). Mas, no v
1
v
2
-caminho
em C que evita {x
1
, x
2
}, existe um caminho P
que liga um v´ertice w
1
∈ V (B
1
) a um
v´ertice w
2
∈ V (B
2
) e ´e internamente disjunto de ambos V (B
1
) e V (B
2
). Na uni˜ao de
P
, P
1
, P
2
e Q, existe um circuito contendo E(P
1
) que tem comprimento seis e, p ortanto,
contradiz a Afirma¸c˜ao 3.7, ou tem comprimento cinco e, implica que, y
1
∈ V (P
). Como
P e P
s˜ao v´ertices disjuntos, temos uma contradi¸c˜ao.
A ´ultima contradi¸c˜ao completa a prova de que ´e um absurdo assumir que G\C ´e
desconexo. Portanto, temos que, de fato, G\C ´e conexo. ✷
Afirma¸c˜ao 3.15 Se k ≥ 5, ent˜ao todo bloco terminal de G\C tem, pelo menos, k + 1
v´ertices.
Observa¸c˜ao 3.16 Sendo G\C conexo, todo bloco terminal de G\C ´e, por defini¸c˜ao, um
bloco especial e, pela Afirma¸c˜ao 3.4, tem, no m´ınimo, k − 1 v´ertices.
Sejam B
um bloco terminal de G\C e u o v´ertice separador de G\C pertencente a
B
. Assumimos que |V (B
)| ∈ {k−1 , k}. Pela compara¸c˜ao de graus em B
e G, deduzimos
imediatamente que V (C) ⊇ V (B
)−{u}, ou seja, C poder´a conter todos os v´ertices de B
,
29
a poss´ıvel exce¸c˜ao ´e o v´ertice separador. Al´em disso, se um v´ertice de B
n˜ao ´e adjacente
a dois ou mais v´ertices em B
, ent˜ao este v´ertice deve ser u.
Sejam P um caminho que est´a propriamente contido em C e {B
1
, B
2
, . . . , B
S
}
um conjunto de blocos de G\C, dizemos que P cruza este conjunto de blocos quando a
interse¸c˜ao de V (P ) e V (B
1
) ∪ V (B
2
) ∪ V (B
1
) ∪ ... ∪ V (B
S
) consiste dos v´ertices terminais
de P e G[E(B
1
) ∪ E(B
2
) ∪ ... ∪ E(B
S
) ∪ E(P )] ´e 2-conexo, ou seja, P pode ser visto como
um G\ C-caminho.
Consideremos os B
-segmentos de C. Existe um B
-segmento C[v
1
, v
2
] que cont´em
um caminho que cruza algum conjunto de blocos contendo B = H. Chamamos um
B
-segmento de n˜ao-trivial se ele cont´em, pelo menos, duas arestas; caso contr´ario,
chamaremos de trivial.
Observa¸c˜ao 3.17 Por constru¸c˜ao, C[v
1
, v
2
] ´e um B
-segmento n˜ao-trivial.
Afirma¸c˜ao 3.18 G n˜ao possui circuito C
com pelo menos k + 1 arestas para as quais
todas as condi¸c˜oes a seguir s˜ao v´alidas:
(3.18.1) E(C[v
1
, v
2
]) ∩ C
= ∅;
(3.18.2) V (C
) ⊇ V (C) ∩ V (B
); e
(3.18.3) C
´e obtido a partir de C pela dele¸c˜ao de alguns B
-segmentos de C e inserindo
algum subconjunto X de E(B
) tal que B
\X ´e conexo.
Suponhamos que G tenha tal circuito C
. Consideremos G\C
. Ora, G\C
cont´em
C[v
1
, v
2
] e, consequentemente, cont´em um caminho P
0
que cruza um conjunto de blocos
contendo B. Como B
\X ´e conexo, segue que G\C
cont´em um circuito que cont´em P
0
e
intercepta E(B). Pela Afirma¸c˜ao 3.3, o bloco de G\C
cont´em E(H) propriamente, uma
contradi¸c˜ao. Portanto, a Afirma¸c˜ao 3.18 ´e verdade. ✷
A prova da Afirma¸c˜ao 3.15 ser´a dividida em v´arios casos, em cada um deles devemos
construir um circuito C
obedecendo (3.18.1) a (3.18.3) com, pelo menos, k + 1 arestas.
Um circuito C
obedecendo (3.18.1) a (3.18.3) tem comprimento, no m´ınimo,
|V (C) ∩ V (B
)| + n, onde n ´e o n´umero de B
-segmentos n˜ao-triviais de C que est˜ao
contidos em C
.
Suponhamos |V (B
)| = k − 1. Ent˜ao, pela Afirma¸c˜ao 3.4, B
∼
=
K
k−1
e, pela
Observa¸c˜ao 3.17, v
1
v
2
∈ E( B
). Seja C
= (C − C[v
1
, v
2
]) ∪ {v
1
v
2
}. Todo B
-segmento
30
de C cont´em pelo menos duas arestas. O n´umero de tais B
-segmentos, diferentes de
C[v
1
, v
2
], ´e no m´ınimo |V (B
) ∩ V (C)| − 1. Assim,
|C
| ≥ |V (B
) ∩ V (C)| + |V (B
) ∩ V (C)| − 1 = 2(|V (B
) ∩ V (C)| − 1) + 1,
mas, para n˜ao contradizer a Afirma¸c˜ao 3.18, |C
| deve ser menor ou igual a k, logo,
k ≥ |C
| ≥ 2(|V (B
) ∩ V (C)| − 1) + 1 ⇒
k + 1
2
≥ |V (B
) ∩ V (C)|.
Mas, |V (B
) ∩ V (C)| ´e k − 1 ou k − 2. Para que |V (B
) ∩ V (C)| seja igual a k − 1, u deve
pertencer a C. Neste caso,
k+1
2
≥ k − 1, logo, k ≤ 3, uma contradi¸c˜ao. Portanto, devemos
assumir que u ∈ V (C). Ent˜ao,
k+1
2
≥ k − 2, logo, k ≤ 5 e, portanto, k = 5. Neste caso,
alteramos a escolha de C
para (C − C[v
1
, v
2
]) ∪ {uv
1
, uv
2
} e, consequentemente, V (C
)
cont´em todos os v´ertices de B
. Sendo assim, |C
| ≥ k−1+[(k−2)−1] = 2+2(k−3) ≥ k+1,
uma contradi¸c˜ao. Logo, |V (B
)| deve ser maior que k − 1.
Suponhamos |V (B
)| = k. Ent˜ao, pela Afirma¸c˜ao 3.4, B
∼
=
K
k
\(T ∪ S), onde T
´e um emparelhamento e S ´e um subconjunto de arestas incidentes ao v´ertice u tal que
|S| ≤ k − 3 e V (S) ∩ V (T ) = ∅. Dois B
-segmentos de C consecutivos n˜ao podem ser
triviais, a menos que cada um contenha o v´ertice separador u.
Suponhamos que u ∈ V (C). Seja v
1
, v
2
, . . . , v
k−1
a ordem C-induzida em V (B
).
Sem perda de generalidade, devemos assumir que um dos seguintes casos acontece:
(a) {uv
1
, uv
2
} ⊆ E(B
) e d
B
(u) ≥ 3;
(b) {uv
1
, uv
2
} ⊆ E(B
) e d
B
(u) = 2;
(c) uv
2
∈ E(B
).
Se (a) acontece, seja C
= (C − C[v
1
, v
2
]) ∪ {uv
1
, uv
2
}. Como u ∈ V (C), ent˜ao n˜ao
existem dois B
-segmentos triviais consecutivos. Sendo k ≥ 5, existir´a, pelo menos, um
B
-segmento n˜ao-trivial diferente de C[v
1
, v
2
], logo |C
| ≥ k + 1 e B
\{uv
1
, uv
2
} ´e conexo,
portanto, temos uma contradi¸c˜ao a Afirma¸c˜ao 3.18.
Se (b) acontece, ent˜ao seja C
= (C − C[v
1
, v
2
] − C[v
3
, v
4
]) ∪ {v
1
v
3
, v
2
v
4
}. Como
B
− {u} ´e completo, exceto pela poss´ıvel ausˆencia da aresta v
1
v
2
, todo B
-segmento de C
´e n˜ao-trivial. Assim, |C
| ≥ k +1. Como B
\{v
1
v
3
, v
2
v
4
} ´e conexo, temos uma contradi¸c˜ao
`a Afirma¸c˜ao 3.18.
31
Se (c) acontece, ent˜ao v
2
´e adjacente em B
a todo v´ertice em V (B
) − {u}. Em
particular, v
1
v
2
∈ E(B
). Seja C
= (C − C[v
1
, v
2
]) ∪ {v
1
v
2
}. Como v
2
v
3
∈ E(B
), o
segmento C[v
2
, v
3
] ´e n˜ao-trivial. Al´em disso, pelo menos, um entre C[v
3
, v
4
] e C[v
4
, v
5
] ´e
n˜ao-trivial, onde, possivelmente, v
5
= v
1
. Assim, C tem, pelo menos, dois B
-segmentos
n˜ao-triviais, diferentes de C[v
1
, v
2
], logo, |C
| ≥ |V (C) ∩ V (B
)| + 2 = (k − 1) + 2 = k + 1,
uma contradi¸c˜ao.
Sendo assim, ´e necess´ario assumir que u pertence a V (C). Seja v
1
, v
2
, . . . , v
k
a
ordem C-induzida em V (B
). Sem perda de generalidade, devemos assumir tamb´em que
uma das seguintes condi¸c˜oes acontece:
(a) v
1
v
2
∈ E(B
);
(b) v
1
v
2
∈ E(B
) e u ∈ {v
1
, v
2
};
(c) v
1
v
2
∈ E(B
) e u = v
2
.
No caso (a), seja C
= (C −C[v
1
, v
2
])∪{v
1
v
2
}. Observamos que B
\{v
1
v
2
} ´e conexo.
Como k ≥ 5 e s´o podem existir apenas dois B
-segmentos triviais consecutivos, temos que
existir´a, pelo menos, um B
-segmento n˜ao-trivial diferente de C[v
1
, v
2
], implicando que
|C
| ≥ k + 1, uma contradi¸c˜ao.
No caso (b), ambos v
1
e v
2
s˜ao adjacentes em B
a todos os v´ertices de
V (B
) − {v
1
, v
2
}. Ent˜ao, como v
2
v
3
∈ E(B
), o segmento C[v
2
, v
3
] ´e n˜ao-trivial. Seja
C
= (C − C[v
1
, v
2
] − C[v
3
, v
4
]) ∪ {v
1
v
3
, v
2
v
4
}. Como C
cont´em todos os v´ertices de
B
e tamb´em cont´em o B
-segmento n˜ao-trivial C[v
2
, v
3
], ent˜ao C
tem comprimento, no
m´ınimo, k + 1. Al´em disso, B
\{v
1
v
3
, v
2
v
4
} ´e conexo, uma contradi¸c˜ao.
No caso (c), seja C
= (C − C[v
1
, v
2
] − C[v
2
, v
3
]) ∪ {v
1
v
3
}. Ent˜ao, v
2
v
1
∈ E(B
),
logo, v
1
v
k
∈ E(B
) e, consequentemente, C[v
1
, v
k
] ´e n˜ao-trivial. Pelo menos, um dos B
-
segmentos C[v
3
, v
4
] ou C[v
4
, v
5
] ´e n˜ao-trivial, porque ou a aresta v
3
v
4
pertence a E(B
),
ou a aresta v
4
v
5
ir´a pertencer a E(B
). Assim, C
cont´em pelo menos dois B
-segmentos
n˜ao-triviais de C, logo, |C
| ≥ k + 1, o que contradiz a Afirma¸c˜ao 3.18.
Portanto, quando k ≥ 5, todo bloco terminal de G\C tem, no m´ınimo, k + 1
v´ertices. ✷
Combinando as Afirma¸c˜oes 3.4 e 3.15 e a defini¸c˜ao de C, obtemos:
32
Afirma¸c˜ao 3.19 Se B
´e um bloco terminal de G\C distinto de B, ent˜ao B ´e um bloco
de G\C
B
. Al´em disso, se k ≥ 5, ent˜ao |C
B
| ≥ k + 1.
Afirma¸c˜ao 3.20 G\C tem exatamente dois blocos terminais e toda aresta de C satisfaz
a uma destas condi¸c˜oes:
(i) intercepta dois v´ertices pertencentes ao mesmo bloco terminal de G\C; ou
(ii) intercepta dois v´ertices em diferentes blocos terminais de G\C tal que nenhum destes
dois v´ertices ´e um v´ertice-separador de G\C.
Seja u um v´ertice separador de G\C que pertence ao bloco B e seja B
1
outro bloco
de G\C tal que u pertence a V (B
1
). Ent˜ao, em (G\C) − u, os conjuntos V (B) − {u} e
V (B
1
) − {u} est˜ao contidos em diferentes componentes conexas D e D
1
, respectivamente.
Como G − u ´e conexo, existe um caminho em C de D para D
1
e, consequentemente,
existe um tal caminho minimal P . Este caminho cruza um conjunto S de blocos de G\C
tal que B ∈ S. Al´em disso, todo conjunto de blocos de G\C que cont´em B e ´e cruzado
por um caminho em C, deve conter todos os blocos terminais de G\C, caso contr´ario,
B = H estaria contido em um bloco maior de G\C
B
, onde B
´e bloco terminal de G\ C e
B
∈ S, ou seja, ter´ıamos uma contradi¸c˜ao `a Afirma¸c˜ao 3.19. Portanto, como o caminho
que cruza S s´o intercepta os blocos de S em dois v´ertices, G\C tem exatamente dois
blocos terminais.
Ambos blocos terminais devem interceptar uma aresta de C. Assim, existe um
caminho em C que liga um v´ertice em um bloco terminal a um v´ertice do outro. Todo tal
caminho minimal tem no m´aximo uma aresta, caso contr´ario, C teria um caminho que
cruza algum conjunto S de blocos de G\C tal que B ∈ S, mas S n˜ao cont´em ambos os
blocos terminais, uma contradi¸c˜ao a escolha de C. Logo, toda aresta de C ou intercepta
dois v´ertices no mesmo bloco terminal de G\C, ou intercepta v´ertices em dois blocos
terminais distintos de G\C. Pela Afirma¸c˜ao 3.19, uma aresta de C que tem dois v´ertices
adjacentes em diferentes blocos terminais n˜ao intercepta v´ertice separador de G\C. ✷
Afirma¸c˜ao 3.21 B e C tem, no m´aximo, um v´ertice em comum.
Seja B
um bloco terminal de G\C diferente de B. Se B e C tˆem mais do que um
v´ertice em comum, ent˜ao G[E(B) ∪ C] est´a propriamente contido em um bloco de G\C
B
,
contradizendo a Afirma¸c˜ao 3.19. ✷
33
3.2 Redu¸c˜ao ao caso que |E(H)| = 1
Distinguiremos os casos quando:
(i) B n˜ao ´e bloco terminal de G\C; e
(ii) B ´e um bloco terminal de G\C.
No caso de (i) ser verdade, sejam v e w os v´ertices separadores de G\C pertencentes
aos blocos terminais B
v
e B
w
de G\C, respectivamente. Seja G
obtido a partir de G pela
exclus˜ao da uni˜ao de todos os blocos de G\C, com exce¸c˜ao de B
v
e B
w
, e adicionando
uma aresta ligando v e w. Seja H
o grafo G
[{vw}]. Suponhamos que |E(G
)| < |E(G)|.
Ent˜ao, d
G
(v) ≥ k, para todo v em V (G
) − V (H
), e C ´e um circuito de G
que ´e aresta
disjunta de H
e, quando k ≥ 5, |C| ≥ k +1. Como o |E(G)| ´e minimal tal que o Teorema
1.2 falha, temos que o Teorema 1.2 vale para o grafo G
, ent˜ao G
tem um circuito C
que ´e aresta disjunta de H
tal que G
\C
´e 2-conexo e, quando k ≥ 5, |C
| ≥ k + 1.
Evidentemente, C
´e um circuito de G. Al´em disso, como G\C
pode ser escrito como a
2-soma com ponto base vw de G
\C
e outro grafo 2-conexo, segue que G\C
´e 2-conexo,
uma contradi¸c˜ao. Concluimos que |E(G
)| = |E(G)|. Portanto, se B n˜ao ´e bloco terminal
de G\C, ent˜ao G\C tem exatamente trˆes blocos e B, que ´e igual a H, consiste de uma
´unica aresta.
No caso de (ii) ser verdade, segue, pela Afirma¸c˜ao 3.21, que B e C tem exatamente
um v´ertice em comum, digamos w. Seja v o v´ertice separador de G \C que pertence ao
outro bloco terminal B
de G\C. Seja G
obtido a partir de G pela dele¸c˜ao da uni˜ao de
todos os blocos de G\C diferentes de B
e adicionando uma aresta ligando v a w. Pela
Afirma¸c˜ao 3.20, tal aresta vw n˜ao existe em C. Seja H
= G
[{vw}]. Se |E(G
)| < |E(G)|,
ent˜ao, como no caso (i), obtemos uma contradi¸c˜ao. Portanto, se B ´e um bloco terminal
de G\ C, ent˜ao G\C tem exatamente dois blocos e B ´e apenas uma aresta.
O Teorema 1.2 vale, a menos que G\C tenha no m´aximo trˆes blocos, onde dois
deles s˜ao blocos terminais e B, que ´e igual a H, ´e uma ´unica aresta. Al´em disso, se
G\C tem exatamente trˆes blocos, B n˜ao ´e bloco terminal. Suponhamos que G\C tenha
exatamente trˆes blocos. Devemos refinar a escolha de C para que, dentre os poss´ıveis
candidatos de C, escolhemos o que faz com que o n´umero m´aximo de arestas de um
bloco de G\C seja o maior poss´ıvel. Seja B
2
o bloco com o n´umero m´aximo de arestas
alcan¸cado. Ent˜ao, B
2
´e um bloco terminal de G\C. Seja B
1
o outro bloco terminal de
34
G\C. O terceiro bloco de G\C ´e B. Pelas Afirma¸c˜oes 3.4 e 3.15, B
1
cont´em um circuito
C
1
de G\C tal que, quando k ≥ 5, |C
1
| ≥ k + 1. Pela Afirma¸c˜ao 3.5, G\C
1
´e conexo e,
claramente, tem um bloco B
2
que cont´em B
2
. Pela escolha de B
2
, segue que B
2
= B
2
.
Logo, B
2
tem um ´unico v´ertice u em comum com C e u deve ser um v´ertice separador de
G\C
1
, caso contr´ario, a escolha de B
2
´e contrariada, pois B
2
deixaria de ser maximal. O
´unico v´ertice em V (B) ∩ V (B
2
) ´e tamb´em um v´ertice separador de G\C
1
, que ´e diferente
de u. Assim, B
2
´e um bloco de G\C
1
contendo, pelo menos, dois v´ertices separadores
distintos deste grafo. Logo, em G\C
1
, existem, no m´ınimo, trˆes blocos incluindo B e B
2
.
Como B
2
n˜ao ´e um bloco terminal, deduzimos que G\C
1
tem um outro bloco distinto de
B, que n˜ao ´e bloco terminal, portanto, o Teorema 1.2 vale para G, uma contradi¸c˜ao.
Assumimos que G\C tem exatamente dois blocos, um deles ´e B e consiste apenas
de uma ´unica aresta e = vw. Seja B
o outro bloco de G\C e suponhamos que w ´e o
v´ertice em comum entre B e B
. Ent˜ao, C tem exatamente duas arestas interceptando
v. Pelo fato de |C| > |E(H)|, o Teorema 1.2 vale para G e seu subgrafo C. Assim, G\C
´e 2-conexo para todos os circuitos C
de G que s˜ao arestas-disjuntas de C, ou G\C
´e
2-conexo para algum circuito C
com |C
| ≥ k + 1 quando k ≥ 5. Como d
G
(v) = 3,
um circuito que ´e aresta disjunta de C em G, ´e tamb´em aresta disjunta de H. Devemos
estabelecer uma contradi¸c˜ao proveniente do fato de que podemos mostrar que o grafo G
tem um circuito que ´e aresta disjunta de C e que, quando k ≥ 5, este circuito pode ser
escolhido de tal forma que tenha comprimento maior ou igual a k + 1.
Consideremos
B
. Todo v´ertice deste grafo simples 2-conexo, exceto, p ossivelmente,
w, tem grau, no m´ınimo, k − 2. Se k = 4, ent˜ao G certamente tem um circuito que
´e aresta disjunta de C, temos uma contradi¸c˜ao. Assim, devemos assumir que k ≥ 5.
Ent˜ao, pelas Afirma¸c˜oes 3.4 e 3.21, obtemos uma contradi¸c˜ao, que ´e B
ter um circuito
de comprimento maior ou igual a k + 1, a menos que |V (B
)| ∈ {k − 1, k}. No caso
excepcional, |V (G)| ∈ {k, k + 1}. Como todo v´ertice de G, diferente de v e w, tem
grau, pelo menos, k, todo tal v´ertice ´e adjacente a v. Mas, v tem grau 3 em G, logo
5 ≤ k ≤ |V (G)| ≤ 4. Esta contradi¸c˜ao completa a prova de que o Teorema 1.2 vale
quando |E(H)| ≥ 1.
35
3.3 E(H) ´e vazio
Assumimos que o Teorema 1.2 falha quando H n˜ao possui arestas. Neste caso, H
´e apenas um ´unico v´ertice u. Seja e uma aresta incidente com u. Como o Teorema 1.2
vale quando H = G[{e}], mas falha quando E(H) = ∅, deduzimos que G\C ´e 2-conexo
para todo circuito C tal que e ∈ C. Fazendo e variar sobre todas as arestas incidentes
a u, deduzimos que G\C ´e 2-conexo para todos os circuitos C que n˜ao cont´em o v´ertice
estrela u. Sendo assim, devemos assumir que d
G
(u) = 2. Consideremos G − {u} e seja G
1
um bloco especial deste grafo. Seja A = {w}, onde, se G
1
= G − {u}, ent˜ao w ´e o ´unico
v´ertice separador de G − {u} em G
1
e, se G
1
= G − {u}, ent˜ao w ´e um v´ertice adjacente
de u em G
1
. Ent˜ao, d
G
1
(x) + d
G
1
(y) ≥ 2k − 1 para todos os v´ertices x e y n˜ao adjacentes
em V (G
1
) − A. Usando o Lema 3.1, como k ≥ 3, segue que G
1
tem um circuito C
1
de
comprimento, no m´ınimo, k + 1. Mas, C
1
´e um circuito de G que ´e aresta disjunto do
v´ertice estrela de u. Logo, G\C
1
´e 2-conexo e, portanto, o Teorema 1.2 vale quando E(H)
´e vazio, uma contradi¸c˜ao.
Com isso, concluimos a prova do Teorema 1.2.
Cap´ıtulo 4
Exemplos
Quando k ≥ 5, o limite inferior de k + 1 no comprimento de C em (ii) do Teorema
1.2 melhora o limite de k − 1 no Teorema de Jackson. O exemplo a seguir nos mostra que
este aprimoramento falha quando k = 4.
Exemplo 4.1 Seja G
1
um bloco com, pelo menos, dois v´ertices e G
2
uma c´opia do K
2,3
com classe de v´ertices {u
1
, u
2
} e {w
1
, w
2
, w
3
}. Criamos G adicionando as arestas u
1
u
2
e, para cada i ∈ {1, 2, 3}, adicionamos duas arestas de w
i
para v´ertices distintos w
i
e w

i
de G
1
. Seja H o subgrafo induzido de G por E(G
1
) ∪ {w
i
w
i
, w
i
w

i
; 1 ≤ i ≤ 3}. Ent˜ao,
d
G
(v) ≥ 4 para todo v em V (G) − V (H), mas o maior ciclo C de G que evita E(H) e
deixa G\C 2-conexo ´e um ciclo de comprimento trˆes.
G
2
u
1
u
2
w
1
w
2
w
3
w
w

G
1
Figura 4.1: G
O pr´oximo exemplo nos revela que o limite de k + 1 v´ertices em (ii) do Teorema
1.2 ´e o melhor poss´ıvel.
Exemplo 4.2 Seja H um grafo simples, que ´e um bloco. Para cada i ∈ {1, 2}, sejam
u
i
, v
i
e w
i
v´ertices distintos em uma c´opia G
i
de K
k+1
. Se |V (H)| = 1, ent˜ao G ´e formado
37
pela identifica¸c˜ao de w
1
e w
2
com os ´unicos v´ertices de H e adicionando a aresta u
1
u
2
.
Se |V (H)| > 1, ent˜ao G ´e formado a partir de G
1
e G
2
pela identifica¸c˜ao de w
1
e w
2
com
dois v´ertices distintos de H e adicionando as arestas v
1
v
2
e u
1
u
2
. Em cada caso, G n˜ao
tem ciclo de comprimento maior do que k + 1 para o qual G\ C ´e 2-conexo e C ∩ E(H) ´e
vazio.
K
k+1
G
1
K
k+1
G
2
u
1
w
1
u
2
w
2
H
|E(H)| = 1
K
k+1
G
1
K
k+1
G
2
u
1
w
1
u
2
w
2
H
v
1
v
2
|E(H)| > 1
Figura 4.2: G
Referˆencias Bibliogr´aficas
[1] BONDY, J. A.; MURTY, U. S. R. Graph theory with applications. New York:
North-Holland, 1976.
[2] DIESTEL, R. Graph Theory. New York: Springer, 1997.
[3] EGAWA, Y. e MIYAMOTO, T. The longest cycles in a graph G with minimum
degree at least |G|/k, J. Combin. Theory Ser B, v. 46, p. 356-362, 1980.
[4] JACKSON, B. Removable cycles in 2-connected graphs of minimum degree at least
four. J London Math Soc (2), v. 21, p. 385-392, 1980.
[5] MADER, W. Kreuzungfreie a, b-Wege in endlichen Graphen. Abh Math Sem,
Hamburg, v. 42, p. 187-204, 1974.
[6] OLIVEIRA, M. G. C. de. Decomposicao de grafos planares em circuitos pares. 1999.
Disserta¸c˜ao (Mestrado em Matem´atica) - Centro de Ciˆencias Exatas e da Natureza,
Universidade Federal de Pernambuco.
[7] OXLEY, J.; LEMOS, M. On Removable Circuits in Graphs and Matroids. Journal
of Graph Theory, v. 30, p. 51-66, 1999.
[8] WILSON, R. J., Introduction to graph theory. Edinburgh: Oliver & Boyd, 1972.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo