Fabio Protti - Notas de Aula de Teoria dos Grafos (UFF)

Prévia do material em texto

Instituto de Computac¸a˜o
Universidade Federal Fluminense
Notas de Aula de Teoria dos Grafos
Prof. Fa´bio Protti
Nitero´i, agosto de 2015.
Conteu´do
1 Conceitos Ba´sicos 5
1.1 Grafos, ve´rtices, arestas . . . . . . . . . . . . . . . . . . . . . 5
1.2 Vizinhanc¸a e grau . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Unia˜o, intersec¸a˜o, complemento . . . . . . . . . . . . . . . . . 8
1.5 Grafo completo, clique, conjunto independente . . . . . . . . . 9
1.6 Passeios, trilhas, caminhos, ciclos . . . . . . . . . . . . . . . . 9
1.7 Distaˆncia, excentricidade, diaˆmetro . . . . . . . . . . . . . . . 11
1.8 Isomorfismo de grafos . . . . . . . . . . . . . . . . . . . . . . . 11
1.9 Maximalidade e minimalidade . . . . . . . . . . . . . . . . . . 11
1.10 Grafos conexos e desconexos . . . . . . . . . . . . . . . . . . . 12
1.11 Grafos bipartidos . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.12 Propriedades heredita´rias . . . . . . . . . . . . . . . . . . . . . 14
1.13 Grafos como estruturas de dados . . . . . . . . . . . . . . . . 14
1.14 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 A´rvores 18
2.1 Conceito de a´rvore . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Folhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Centro de uma a´rvore . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Pontes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 A´rvores geradoras . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Conectividade 24
3.1 Cortes de ve´rtices . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1 Articulac¸o˜es e blocos . . . . . . . . . . . . . . . . . . . 24
3.1.2 Conectividade de ve´rtices . . . . . . . . . . . . . . . . 25
3.1.3 Caminhos internamente disjuntos em ve´rtices . . . . . 25
3.2 Cortes de arestas . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Ligac¸o˜es (ou co-ciclos) . . . . . . . . . . . . . . . . . . 27
3.2.2 Conectividade de arestas . . . . . . . . . . . . . . . . . 27
3.2.3 Caminhos disjuntos em arestas . . . . . . . . . . . . . 29
3.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 Grafos Eulerianos e Hamiltonianos 31
4.1 Grafos Eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.1 Passeios Eulerianos abertos . . . . . . . . . . . . . . . 33
4.2 Grafos Hamiltonianos . . . . . . . . . . . . . . . . . . . . . . . 33
4.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 Emparelhamentos 40
5.1 Definic¸a˜o de emparelhamento . . . . . . . . . . . . . . . . . . 40
5.2 Teorema de Berge . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3 Teorema de Tutte . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.4 Teorema de Hall . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.5 Teorema de Ko¨nig . . . . . . . . . . . . . . . . . . . . . . . . 43
5.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6 Colorac¸a˜o de Ve´rtices 45
6.1 Grafos k-color´ıveis . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 Grafos cr´ıticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.3 Cotas para o nu´mero croma´tico . . . . . . . . . . . . . . . . . 46
6.3.1 Construc¸a˜o de Mycielski . . . . . . . . . . . . . . . . . 46
6.3.2 Teorema de Brooks . . . . . . . . . . . . . . . . . . . . 47
6.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
7 Colorac¸a˜o de Arestas 49
7.1 Grafos k-color´ıveis em arestas . . . . . . . . . . . . . . . . . . 49
7.2 Teorema de Vizing . . . . . . . . . . . . . . . . . . . . . . . . 49
7.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
8 Planaridade 51
8.1 Definic¸a˜o de grafo planar . . . . . . . . . . . . . . . . . . . . . 51
8.2 Fo´rmula de Euler . . . . . . . . . . . . . . . . . . . . . . . . . 51
8.3 Caracterizac¸o˜es de grafos planares . . . . . . . . . . . . . . . . 52
8.4 Mapas e o Teorema das Quatro Cores . . . . . . . . . . . . . . 53
8.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
9 Grafos Direcionados 55
9.1 Conceitos ba´sicos sobre digrafos . . . . . . . . . . . . . . . . . 55
9.2 Teorema de Gallai-Hasse-Roy-Vitaver . . . . . . . . . . . . . . 56
9.2.1 Torneios . . . . . . . . . . . . . . . . . . . . . . . . . . 58
9.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
1 Conceitos Ba´sicos
Neste cap´ıtulo forneceremos todas as definic¸o˜es e resultados fundamentais
que sera˜o utilizados ao longo de todo o texto.
1.1 Grafos, ve´rtices, arestas
Um grafo (simples) G e´ formado por um conjunto de ve´rtices, denotado por
V (G), e um conjunto de arestas, denotado por E(G). Cada aresta e´ um par
(na˜o ordenado) de ve´rtices distintos. Se xy e´ uma aresta, enta˜o os ve´rtices x e
y sa˜o os extremos desta aresta. Dizemos tambe´m que x e y esta˜o conectados,
ou que sa˜o adjacentes ou vizinhos.
Um grafo pode ser representado geometricamente como um conjunto de
pontos no plano (representando os ve´rtices) e linhas que ligam estes pontos
(representando as arestas). Observamos que o mesmo grafo pode ter va´rias
representac¸o˜es geome´tricas diferentes.
Exemplo 1.1. Seja G o grafo tal que V (G) = {a, u, v, w, x, y, z} e E(G) =
{uv, vw, wx, xy, yz, zu, av, ax, az}. Na Figura 1.1 temos duas representac¸o˜es
geome´tricas diferentes para G.
u v
z a w
y x
w
u
y
a
v
x
z
Figura 1.1: Duas representac¸o˜es geome´tricas diferentes para o mesmo grafo.
A ordem de um grafo e´ G e´ o nu´mero de ve´rtices de G. Utilizamos a
seguinte notac¸a˜o: n = |V (G)| e m = |E(G)|. O tamanho de um grafo G e´ a
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
soma n +m. Um grafo trivial e´ aquele com um u´nico ve´rtice (n = 1). Um
grafo nulo e´ aquele com V (G) = ∅ (isto e´, n = 0).
Um multigrafo e´ uma generalizac¸a˜o do conceito de grafo simples. Em
um multigrafo podem existir arestas paralelas (arestas que compartilham
os mesmos extremos) e lac¸os (um lac¸o e´ uma aresta da forma xx). Lac¸os
tambe´m sa˜o chamados de loops.
1.2 Vizinhanc¸a e grau
A vizinhanc¸a aberta de um ve´rtice v e´ o conjunto de seus vizinhos. Utilizamos
a notac¸a˜o N(v) para designar a vizinhanc¸a aberta de v. A vizinhanc¸a fechada
de um ve´rtice v e´ definida como N [v] = N(v) ∪ {v}.
O grau de um ve´rtice e´ o nu´mero de vezes em que ele ocorre como ex-
tremo de uma aresta. (Esta definic¸a˜o se aplica tanto para grafos como para
multigrafos.) Utilizamos a notac¸a˜o d(v) para designar o grau do ve´rtice v.
Em um grafo simples, o grau de um ve´rtice e´ igual ao nu´mero de vizinhos
que ele possui, isto e´, d(v) = |N(v)|.
Um grafo e´ regular quando todos os seus ve´rtices teˆm o mesmo grau. Um
grafo e´ k-regular quando todos os seus ve´rtices teˆm grau igual a k.
O grau ma´ximo de G e´ definido como ∆(G) = max{d(v) | v ∈ V (G)}. O
grau mı´nimo de G e´ definido como δ(G) = min{d(v) | v ∈ V (G)}.
Dado um grafo G tal que V (G) = {v1, v2, . . . , vn−1, vn} e os graus dos
ve´rtices satisfazem d(v1) ≤ d(v2) ≤ · · · ≤ d(vn−1) ≤ d(vn), a sequeˆncia de
graus de G e´ precisamente a sequeˆncia
( d(v1), d(v2), . . . , d(vn−1), d(vn) ).
Exemplo 1.2. A sequeˆncia de graus do grafo G definido anteriormente no
Exemplo 1.1 e´ (2, 2, 2, 3, 3, 3, 3). Temos que δ(G) = 2 e ∆(G) = 3.
Um ve´rtice e´ isolado quando tem grau zero (na˜o possui vizinhos). Um
ve´rtice v e´ universal quando esta´ conectado por arestas a todos os demais
ve´rtices, isto e´, N(v) = V (G) \ {v}. Se v e´ um ve´rtice universal enta˜o
d(v) = n−1.
O seguinte teorema e´ conhecido como Teorema do Aperto de Ma˜os:
6
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Teorema 1.1. Em qualquer grafo simples G,
∑
v∈V (G)
d(v) = 2m.
Demonstrac¸a˜o. Observe que cada aresta xy e´ contada duas vezes na soma∑
v∈V (G) d(v) – uma vez na parcela d(x) e outra na parcela d(y).
1.3 Subgrafos
Um subgrafo de um grafo G e´ um grafo H tal que V (H) ⊆ V (G) e E(H) ⊆
E(G). H e´ um subgrafo pro´prio de G quando H e´ um subgrafo de G que na˜o
e´ o pro´prio G.
Um subgrafo gerador (“spanning subgraph”) de G e´ um subgrafo H de G
tal que V (H) = V (G). Em outras palavras, H tem os mesmos ve´rtices de
G, mas na˜o necessariamente todas as arestas de G.
Um subgrafo H de G e´ um subgrafo induzido por um conjunto de ve´rtices
X ⊆ V (G) se V (H) = X e vale a seguinte propriedade: se xy ∈ E(G) e
x, y ∈ X enta˜o xy ∈ E(H). Neste caso, utilizamos a notac¸a˜o H = G[X ].
Informalmente, um subgrafo induzido por um conjunto de ve´rtices X mante´m
todas as arestas originais de G que possuem seus dois extremos em X .
Um subgrafo H de G e´ um subgrafo induzido por um conjunto de arestas
E ′ ⊆ E(G) se:
• E(H) = E ′;
• V (H) = {x | x e´ extremo de alguma aresta de E ′}.
Utilizamos a notac¸a˜o H = G[E ′] para designar que H e´ um subgrafo
induzido por um conjunto de arestas E ′.
A seguinte notac¸a˜o e´ bastante u´til. Se S e´ um subconjunto de ve´rtices de
G, enta˜o G−S = G[V (G)\S]. Se v e´ um ve´rtice de G enta˜o G−v = G−{v}.
Se E ′ e´ um subconjunto de arestas de G, enta˜o o grafo G−E ′ e´ definido
da seguinte forma: V (G−E ′) = V (G) e E(G−E ′) = E(G) \E ′. Se e e´ uma
aresta de G enta˜o G− e = G− {e}.
7
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
1.4 Unia˜o, intersec¸a˜o, complemento
A unia˜o de dois grafos G e H e´ o grafo denotado por G ∪H tal que:
V (G ∪H) = V (G) ∪ V (H) e E(G ∪H) = E(G) ∪ E(H).
A intersec¸a˜o de dois grafos G e H e´ o grafo denotado por G∩H tal que:
V (G ∩H) = V (G) ∩ V (H) e E(G ∩H) = E(G) ∩ E(H).
Dois grafos G e H sa˜o disjuntos em ve´rtices se V (G) ∩ V (H) = ∅. Dois
grafos G e H sa˜o disjuntos em arestas se E(G) ∩ E(H) = ∅. Se G e H sa˜o
disjuntos em ve´rtices, enta˜o e´ claro que sa˜o tambe´m disjuntos em arestas.
Pore´m, G e H podem ser disjuntos em arestas tendo alguns ve´rtices em
comum.
O complemento de um grafo G e´ o grafo G tal que V (G) = V (G) e
E(G) = {xy | xy /∈ E(G)}. Note que G e seu complemento sa˜o grafos
disjuntos em arestas. Portanto, G ∩ G e´ um grafo sem arestas. Ale´m disso,
G ∪G e´ um grafo completo.
Exemplo 1.3. Se G e´ o grafo do Exemplo 1.1, enta˜o G e´ o grafo representado
na Figura 1.2.
u v
z
a
w
y x
Figura 1.2: Representac¸a˜o geome´trica de G, onde G e´ o grafo do Exemplo 1.1.
8
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
1.5 Grafo completo, clique, conjunto independente
Um grafo G e´ um grafo completo se quaisquer dois ve´rtices de G sa˜o vizinhos.
O nu´mero de arestas de um grafo completo e´ n(n − 1)/2. Denotamos por
Kn um grafo completo com n ve´rtices. O grafo K1 e´ o grafo trivial, o grafo
K2 e´ formado por dois ve´rtices e uma aresta, e o grafo K3 e´ o triaˆngulo. A
Figura 1.3 exibe os grafos K3, K4 e K5.
Figura 1.3: Da esquerda para a direita: grafos K3, K4 e K5.
Uma clique em um grafo G e´ um conjunto de ve´rtices K ⊆ V (G) tal que
G[K] e´ completo. Em outras palavras, quaisquer dois ve´rtices distintos de
uma clique sa˜o adjacentes.
Um conjunto esta´vel ou independente em um grafo G e´ um subconjunto de
ve´rtices S ⊆ V (G) tal que G[S] e´ um grafo sem arestas. Em outras palavras,
qualquer par de ve´rtices de um conjunto independente e´ formado por ve´rtices
na˜o adjacentes.
Um grafo com n ve´rtices formando um conjunto independente e´ denotado
por In.
1.6 Passeios, trilhas, caminhos, ciclos
Um passeio (“walk”) e´ uma sequeˆncia de ve´rtices v1, v2, . . . , vk−1, vk tal que
vj−1vj ∈ E(G) para j = 2, . . . , k. Note que em um passeio pode haver
repetic¸a˜o de ve´rtices e arestas. Se v1 = vk, dizemos que o passeio e´ fechado;
caso contra´rio, o passeio e´ aberto. Um passeio fechado e´ tambe´m denominado
circuito por alguns autores.
Uma trilha (“trail”) e´ um passeio v1, v2, . . . , vk−1, vk cujas arestas sa˜o
todas distintas. Em uma trilha pode haver repetic¸a˜o de ve´rtices, mas na˜o
9
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
de arestas. Assim como no caso dos passeios, as trilhas tambe´m podem ser
classificadas em fechadas e abertas.
Um caminho (“path”) e´ um passeio v1, v2, . . . , vk−1, vk onde os ve´rtices
sa˜o todos distintos. Note que em um caminho, como na˜o pode haver re-
petic¸a˜o de ve´rtices, na˜o ha´ repetic¸a˜o de arestas. Portanto, todo caminho e´
uma trilha (mas nem toda trilha e´ um caminho). O comprimento de um
caminho e´ o nu´mero de arestas neste caminho. Observe que na˜o pode haver
“caminho fechado”, pois em um caminho na˜o ha´ repetic¸a˜o de ve´rtices. Se
P e´ um caminho e u, v sa˜o ve´rtices deste caminho, denotamos por P [u, v] o
subcaminho de P que vai de u ate´ v.
Um ciclo (“cycle”) e´ um passeio v1, v2, . . . , vk−1, vk tal que v1, v2, . . . , vk−1
e´ um caminho e v1 = vk. Por definic¸a˜o, em um ciclo devemos ter k ≥ 3. O
comprimento de um ciclo e´ o nu´mero de ve´rtices (ou arestas) presentes no
ciclo. Um ciclo de comprimento treˆs e´ tambe´m chamado de triaˆngulo. Um
ciclo de comprimento ı´mpar [par] e´ chamado simplesmente de ciclo ı´mpar
[ciclo par].
Uma corda e´ uma aresta que liga dois ve´rtices na˜o consecutivos de um
ciclo (ou caminho). Um ciclo (resp., caminho) induzido em um grafo G e´ um
ciclo (resp., caminho) sem cordas. Um ciclo induzido de comprimento pelo
menos quatro e´ chamado de buraco (“hole”). Utilizamos a notac¸a˜o Ck para
designar um ciclo induzido com k ve´rtices, e a notac¸a˜o Pk para designar um
caminho induzido com k ve´rtices.
De forma ana´loga, um caminho induzido e´ um caminho sem cordas. Uti-
lizamos a notac¸a˜o Pk para designar um caminho induzido com k ve´rtices.
Exemplo 1.4. Considere novamente o grafo G do Exemplo 1.1. Enta˜o:
W1 = u, v, a, z, y, x, a, z e´ um passeio aberto;
W2 = u, v, a, z, y, x, a, z, u e´ um passeio fechado;
T = a, v, w, x, a, z, y e´ uma trilha aberta;
P1 = u, v, w, x, a, z, y e´ um caminho;
P2 = u, v, w, x, y e´ um caminho induzido;
C1 = u, v, w, x, y, z, u e´ um ciclo;
C2 = u, v, a, z, u e´ um ciclo induzido.
Observac¸a˜o 1.1. Muitas vezes, sera´ u´til considerar passeios, trilhas, cami-
nhos e ciclos como grafos (ou subgrafos), em vez de considera´-los simples-
mente como sequeˆncias de ve´rtices. Assim, por exemplo, podemos nos referir
10
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
a um caminho P com k ve´rtices como um grafo P tal que V (P ) = {v1, . . . , vk}
e E(P ) = {vj−1vj | 2 ≤ j ≤ k}.
1.7 Distaˆncia, excentricidade, diaˆmetro
A distaˆncia entre dois ve´rtices x e y e´ o comprimento do menor caminho de
x a y no grafo. Utilizamos a notac¸a˜o dist(x, y) para representar a distaˆncia
entre x e y. Para qualquer ve´rtice x, vale dist(x, x) = 0.
A excentricidade de um ve´rtice v em um grafo G e´ definida como:
exc(v) = max{dist(v, x) | x ∈ V (G)}.
Ja´ o diaˆmetro de um grafo G define-se do seguinte modo:
diam(G) = max{exc(v) | v ∈ V (G)}.
O centro de um grafo G e´ o conjunto de ve´rtices de G com excentricidade
mı´nima.
1.8 Isomorfismo de grafos
Dois grafos G e H sa˜o isomorfos se existe uma bijec¸a˜o f : V (G) → V (H)
tal que xy ∈ E(G) se e somente se f(x)f(y) ∈ E(H). Informalmente, G
e H sa˜o o “mesmo” grafo, a menos de rotulac¸o˜es distintas para os ve´rtices.
Utilizamos a notac¸a˜o G ∼= H para designar que G e H sa˜o isomorfos.
Sejam G e H grafos quaisquer. Se existir algum subgrafo G′ de G que seja
isomorfo a H , dizemos que G conte´m H . Se existiralgum subgrafo induzido
G′ de G que seja isomorfo a H , dizemos que G conte´m H como subgrafo
induzido. Se nenhum subgrafo induzido de G e´ isomorfo a H , dizemos que
G e´ livre de H .
1.9 Maximalidade e minimalidade
Um conjunto S e´ maximal em relac¸a˜o a uma propriedade P se: (i) S satisfaz
P ; (ii) na˜o existe conjunto S ′ que satisfac¸a P e que contenha S propriamente.
11
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Um conjunto S e´ ma´ximo em relac¸a˜o a uma propriedade P se: (i) S
satisfaz P ; (ii) na˜o existe conjunto S ′ que satisfac¸a P e que possua mais
elementos do que S.
Todo conjunto ma´ximo e´ tambe´m maximal, mas nem todo conjunto ma-
ximal e´ ma´ximo.
Exemplo 1.5. Considere o grafoG do Exemplo 1.1. Os conjuntos de ve´rtices
S1 = {u, w, y} e S2 = {a, v, x, z} sa˜o ambos conjuntos independentes maxi-
mais de G, mas apenas S2 e´ um conjunto independente ma´ximo de G.
De forma ana´loga, um conjunto S e´ minimal em relac¸a˜o a uma propri-
edade P se: (i) S satisfaz P ; (ii) na˜o existe conjunto S ′ que satisfac¸a P e
que esteja propriamente contido em S. Um conjunto S e´ mı´nimo em relac¸a˜o
a uma propriedade P se: (i) S satisfaz P ; (ii) na˜o existe conjunto S ′ que
satisfac¸a P e que possua menos elementos do que S. Todo conjunto mı´nimo
e´ tambe´m minimal, mas nem todo conjunto minimal e´ mı´nimo.
Exemplo 1.6. Seja G um grafo qualquer. Um subconjunto C ⊆ V (G) e´
uma cobertura (por ve´rtices) de G se toda aresta de G tem pelo menos um de
seus extremos em C. Considerando os mesmos conjuntos S1 e S2 do exemplo
anterior, temos que S1 e S2 sa˜o coberturas minimais de G, mas apenas S1 e´
uma cobertura mı´nima de G.
Os conceitos maximal/ma´ximo e minimal/mı´nimo tambe´m se aplicam a
grafos e subgrafos.
1.10 Grafos conexos e desconexos
Um grafo G e´ conexo se existe caminho entre qualquer par de ve´rtices de G.
Caso contra´rio, G e´ desconexo.
Uma componente conexa de um grafo G e´ um subgrafo conexo maximal
de G. Denotamos por w(G) o nu´mero de componentes conexas de G. E´ claro
que G e´ conexo se e somente se w(G) = 1.
12
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
1.11 Grafos bipartidos
Um grafo G e´ bipartido se V (G) pode ser particionado em conjuntos X e Y
de modo que toda aresta de G tem um extremo em X e outro em Y . Como
consequeˆncia desta definic¸a˜o, X e Y sa˜o conjuntos independentes.
Exemplo 1.7. O grafo G do Exemplo 1.1 e´ um grafo bipartido, onde X =
{a, v, x, z} e Y = {u, w, y}.
Um grafo bipartido G sera´ bipartido completo se, para qualquer par de
ve´rtices x, y com x ∈ X e y ∈ Y , vale que xy ∈ E(G). Denotamos por
Kp,q um grafo bipartido completo com p ve´rtices em X e q ve´rtices em Y .
Obviamente, Kp,q tem pq arestas.
O seguinte teorema e´ uma caracterizac¸a˜o de grafos bipartidos.
Teorema 1.2. Um grafo G e´ bipartido se e somente se G na˜o conte´m ciclos
ı´mpares.
Demonstrac¸a˜o. Suponha por absurdo que G e´ um grafo bipartido contendo
um ciclo ı´mpar C = v1, v2, . . . , v2k, v2k+1, v1 , para algum inteiro k ≥ 1. Seja
X ∪ Y uma bipartic¸a˜o de V (G), e suponha sem perda de generalidade que
v1 ∈ X . Temos enta˜o que v2 ∈ Y , v3 ∈ X , . . ., v2k ∈ Y e v2k+1 ∈ X .
Mas isto implica que a aresta v1v2k+1 possui seus dois extremos em X , uma
contradic¸a˜o. Isto completa a prova da necessidade.
Suponha agora que G na˜o contenha ciclos ı´mpares. Vamos provar que G
e´ bipartido. E´ fa´cil ver que um grafo e´ bipartido se e somente se todas as
suas componentes conexas sa˜o grafos bipartidos. Assim, basta considerar o
caso em que G e´ conexo.
Considere um ve´rtice v0 qualquer de G. Defina os seguintes conjuntos:
X = {v ∈ V (G) | dist(v0, v) e´ par},
Y = {v ∈ V (G) | dist(v0, v) e´ ı´mpar}.
Para completar a demonstrac¸a˜o, vamos mostrar que X e´ um conjunto
independente. (A prova de que Y e´ um conjunto independente e´ similar.)
Observe inicialmente que dois ve´rtices v1, v2 ∈ X que esta˜o a distaˆncias
distintas de v0 na˜o podem ser adjacentes, caso contra´rio a distaˆncia entre eles
13
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
diferiria no ma´ximo em uma unidade. Considere enta˜o que ambos estejam a
uma mesma distaˆncia d de v0. Sejam P1 e P2 caminhos com comprimento d
de v0 a v1 e v2, respectivamente. Seja z o ve´rtice mais pro´ximo de v1 tal que
z ∈ V (P1) ∩ V (P2). (Eventualmente, podemos ter z = v0.) E´ fa´cil ver que
dist(z, v1) = dist(z, v2). Sejam P1[z, v1] e P2[z, v2] os subcaminhos de P1 e P2
que va˜o de z a v1 e v2, respectivamente. Conclu´ımos que estes subcaminhos
teˆm o mesmo comprimento. Assim, v1 e v2 na˜o podem ser adjacentes, caso
contra´rio haveria um ciclo ı´mpar em G, a saber (P1[z, v1] ∪ P2[z, v2]) + v1v2.
Isto completa a prova da suficieˆncia.
Observac¸a˜o 1.2. Uma generalizac¸a˜o da definic¸a˜o de grafo bipartido com-
pleto e´ a definic¸a˜o de grafo k-partido completo, que e´ aquele cujo conjunto
de ve´rtices esta´ particionado em conjuntos independentes V1, V2, . . . , Vk, e
tal que existe uma aresta entre dois ve´rtices u e w se e somente se u e w
pertencem a conjuntos distintos desta partic¸a˜o.
1.12 Propriedades heredita´rias
Dado um grafo G, uma propriedade e´ heredita´ria por subgrafos [induzidos]
se, quando ela e´ va´lida para G, e´ va´lida tambe´m para todos os subgrafos
[induzidos] de G.
Exemplo 1.8. Se o grafo G e´ livre de triaˆngulos, enta˜o “ser livre de triaˆngu-
los” e´ uma propriedade heredita´ria por subgrafos e por subgrafos induzidos.
Exemplo 1.9. Se o grafo G possui um ve´rtice universal, enta˜o “possuir um
ve´rtice universal” na˜o e´ uma propriedade heredita´ria por subgrafos, nem por
subgrafos induzidos.
Exemplo 1.10. Se o grafo G e´ completo, enta˜o “ser completo” na˜o e´ uma
propriedade heredita´ria por subgrafos, mas e´ uma propriedade heredita´ria
por subgrafos induzidos.
Obviamente, toda propriedade heredita´ria por subgrafos quaisquer tam-
be´m e´ heredita´ria por subgrafos induzidos.
1.13 Grafos como estruturas de dados
A matriz de adjaceˆncias de um grafo G e´ uma matriz An×n onde:
14
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
A[i, j] =


1, se ij ∈ E(G);
0, se ij /∈ E(G).
A matriz de adjaceˆncias e´ sime´trica e possui zeros na sua diagonal prin-
cipal. Utilizando a matriz de adjaceˆncias como estrutura de dados, basta
armazenar o triaˆngulo superior da matriz.
A matriz de adjaceˆncias gasta memo´ria quadra´tica (O(n2)), mas o tempo
de acesso e´ constante – gasta-se tempo O(1) para decidir se dois ve´rtices sa˜o
vizinhos.
A lista de adjaceˆncias de um grafo G e´ um outro tipo de estrutura de
dados para armazenar G. Neste tipo de representac¸a˜o, utiliza-se um vetor
de ponteiros, onde cada ponteiro esta´ associado a um ve´rtice de G e aponta
para uma lista encadeada contendo os vizinhos deste ve´rtice.
O nu´mero de ce´lulas de memo´ria em uma lista de adjaceˆncias e´ n + 2m.
Utilizando esta estrutura, gasta-se tempo O(n) no pior caso para decidir se
dois ve´rtices sa˜o vizinhos.
1.14 Exerc´ıcios
1.1. Prove o Teorema da Amizade: em qualquer festa com pelo menos seis
pessoas, ou treˆs se conhecem mutuamente, ou treˆs na˜o se conhecem
mutuamente.
1.2. Prove ou refute: se G e´ um grafo conexo, enta˜o dois caminhos de
comprimento ma´ximo de G possuem necessariamente pelo menos um
ve´rtice em comum.
1.3. Prove ou refute: se G e´ um grafo contendo exatamente dois ve´rtices
de grau ı´mpar, enta˜o existe necessariamente um caminho ligando estes
dois ve´rtices em G.
1.4. Prove ou refute: se δ(G) > 1
2
(n− 2) enta˜o G e´ conexo.
1.5. Mostre que em uma festa com n ≥ 2 pessoas, existem pelo menos duas
pessoas com o mesmo nu´mero de conhecidos.
15
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
1.6. Um grafo k-partido e´ tal que seus ve´rtices podem ser particionados emk conjuntos V1, V2, .., Vk, de tal maneira que dois ve´rtices pertencentes
um mesmo subconjunto Vi sa˜o sempre na˜o adjacentes. Um grafo k-
partido completo e´ aquele em que todo par de ve´rtices pertencentes a
partes distintas e´ adjacente. Um grafo k-partido completo em que cada
parte possua ⌊n/k⌋ ou ⌈n/k⌉ ve´rtices e´ denominado grafo de Tura´n e
denotado por Tk,n.
(a) Determinar o nu´mero de arestas de Tk,n
(b) Mostrar que se G e´ um grafo k-partido completo enta˜o |E(G)| ≤
|Tk,n|.
1.7. Prove que para todo grafo G vale δ(G) ≤ 2m/n ≤ ∆(G).
1.8. Resolva os itens abaixo.
(a) Existe um multigrafo com a seguinte sequ¨eˆncia de graus:
(3,3,3,3,5,6,6,6,6)?
(b) Existe um multigrafo com a seguinte sequ¨eˆncia de graus:
(1,1,3,3,3,3,5,6,8,9)?
(c) Existe um grafo (simples) com a sequ¨eˆncia de graus do item an-
terior?
(d) Demonstre que a sequ¨eˆncia (d1, d2, . . . , dn) de inteiros na˜o negati-
vos e´ uma sequ¨eˆncia de graus de algum multigrafo se e somente
se
∑n
i=1 di e´ par.
1.9. Um grafo (simples) e´ auto-complementar se G ∼= G.
(a) Deˆ dois exemplos de pares de grafos auto-complementares.
(b) Prove que um grafo auto-complementar tem 4k ou 4k+1 ve´rtices,
para k inteiro na˜o negativo.
1.10. Sejam u e v dois ve´rtices em um grafo G. Mostre que existe um passeio
entre u e v se e somente se existe um caminho entre u e v.
1.11. Seja G um grafo satisfazendo uma propriedade P . Classifique (se hou-
ver) o tipo de hereditariedade de P (por subgrafos quaisquer e/ou por
subgrafos induzidos), nos seguintes casos:
16
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
(a) G e´ bipartido.
(b) G e´ auto-complementar.
(c) G e´ conexo.
(d) G e´ k-regular.
(e) ∆(G) = k.
(f) G na˜o conte´m ciclos.
17
2 A´rvores
As a´rvores constituem uma das mais importantes famı´lias de grafos devido
a suas inu´meras aplicac¸o˜es em Cieˆncia da Computac¸a˜o e outras a´reas em
Cieˆncias Exatas e Engenharias. Neste cap´ıtulo estudaremos os principais
resultados sobre a estrutura das a´rvores.
2.1 Conceito de a´rvore
Dizemos que um grafo e´ ac´ıclico se na˜o possui ciclos. Uma a´rvore e´ um grafo
ac´ıclico e conexo.
Um grafo ac´ıclico na˜o necessariamente conexo tambe´m e´ chamado de
floresta. Cada componente conexa de uma floresta e´ uma a´rvore.
O teorema a seguir e´ a primeira caracterizac¸a˜o de a´rvores que estudare-
mos.
Teorema 2.1. Um grafo T e´ uma a´rvore se e somente se existe um u´nico
caminho entre cada par de ve´rtices de T .
Demonstrac¸a˜o. Suponha inicialmente que exista um u´nico caminho entre
cada par de ve´rtices de T . Isto implica claramente que T e´ um grafo conexo.
Ale´m do mais, se T contivesse um ciclo, haveria pelo menos dois caminhos
entre qualquer par de ve´rtices distintos neste ciclo, contrariando a hipo´tese
assumida. Logo, ale´m de conexo, T e´ ac´ıclico, isto e´, T e´ uma a´rvore.
Suponha agora que T seja uma a´rvore. Como T e´ conexo, existe pelo
menos um caminho entre cada par de ve´rtices de T . Suponha por absurdo
que existam dois caminhos diferentes P1 e P2 entre um certo par de ve´rtices
u, v ∈ V (T ). Seja w o ve´rtice de T com as seguintes propriedades: (a)
w ∈ V (P1) ∩ V (P2); (b) P1[u, w] = P2[u, w]; (c) P1[u, w] e P2[u, w] teˆm o
maior comprimento poss´ıvel. Seja agora x ∈ V (P1) ∩ V (P2) o ve´rtice de T
tal que P1[w, x] e P2[w, x] sa˜o caminhos internamente disjuntos em ve´rtices
(isto e´, possuem apenas os extremos em comum). Observe que o subgrafo
P1[w, x]∪P2[w, x] e´ claramente um ciclo, e isto contradiz a hipo´tese de T ser
uma a´rvore. Portanto, existe necessariamente um u´nico caminho entre cada
par de ve´rtices de T .
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
2.2 Folhas
Uma folha e´ um ve´rtice de grau um. As folhas desempenham um papel
importante nos teoremas a seguir.
Teorema 2.2. Toda a´rvore na˜o trivial tem pelo menos duas folhas.
Demonstrac¸a˜o. Seja T uma a´rvore na˜o trivial e considere um caminho
P em T de comprimento ma´ximo. Sejam u e v os ve´rtices inicial e final de
P . E´ claro que u tem um vizinho x em P . Se u tiver outro vizinho y 6= x,
temos dois casos: y ∈ V (P ) e y /∈ V (P ). O primeiro caso e´ imposs´ıvel, pois o
grafo P [u, y] + uy seria um ciclo. O segundo caso tambe´m e´ imposs´ıvel, pois
contradiz o fato de P ser um caminho de comprimento ma´ximo. Logo x e´ o
u´nico vizinho de u em T , isto e´, u e´ uma folha. O racioc´ıcio para mostrar
que v tambe´m e´ uma folha e´ ideˆntico.
Teorema 2.3. Se T e´ uma a´rvore enta˜o m = n− 1.
Demonstrac¸a˜o. Faremos a demonstrac¸a˜o por induc¸a˜o em n. Para a base
da induc¸a˜o, consideramos o caso n = 1. Nesta situac¸a˜o, T e´ um grafo trivial,
e portanto vale m = 0 = 1 − 1 = n − 1. Para o passo da induc¸a˜o, seja
T uma a´rvore com n > 1 ve´rtices e m arestas, e suponha que qualquer
a´rvore T ′ com n′ < n ve´rtices tem exatamente m′ = n′ − 1 arestas. Pelo
Teorema 2.2, T possui uma folha x. Observe que o grafo T − x e´ claramente
uma a´rvore com n′ = n−1 < n ve´rtices. Pela hipo´tese de induc¸a˜o, T −x tem
n′ − 1 = (n− 1)− 1 = n− 2 arestas. Como T tem exatamente uma aresta a
mais do que T − x, segue que T tem m = (n− 2) + 1 = n− 1 arestas.
2.3 Centro de uma a´rvore
Nesta sec¸a˜o veremos que o centro de uma a´rvore pode ser determinado algo-
ritmicamente de modo bastante simples.
Lema 2.4. Seja T uma a´rvore com pelo menos treˆs ve´rtices. Seja F o
conjunto das folhas de T . Seja T ′ = T − F . Enta˜o, T e T ′ teˆm o mesmo
centro.
Demonstrac¸a˜o. Sejam T e T ′ como no enunciado. Denote por exc(u,G)
a excentricidade do ve´rtice u no grafo G. A demonstrac¸a˜o se baseia nos
seguintes fatos, de verificac¸a˜o simples:
19
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
(a) Nenhuma folha de T pertence ao seu centro;
(b) Se v ∈ V (T ′) enta˜o exc(v, T ′) = exc(v, T )− 1.
Pelo item (a), os ve´rtices do centro de T esta˜o em T ′. Pelo item (b), um
ve´rtice de excentridade mı´nima em T tambe´m e´ um ve´rtice de excentricidade
mı´nima em T ′, e vice-versa. Logo, o lema segue.
Teorema 2.5. (Jordan 1869) O centro de uma a´rvore ou e´ formado por
apenas um ve´rtice ou por dois ve´rtices vizinhos.
Demonstrac¸a˜o. Seja T uma a´rvore. O lema anterior sugere um algoritmo
para encontrar o centro de T :
Algoritmo 1: Algoritmo para encontrar o centro de uma a´rvore T
Entrada: Uma a´rvore T
Sa´ıda: O centro de T
T ′ ← T
enquanto |V (T ′)| ≥ 3 fac¸a
F ← conjunto das folhas de T ′
T ′ ← T ′ − F
retornar V (T ′)
Pelo Lema 2.4, as sucessivas a´rvores referenciadas pela varia´vel T ′, gera-
das ao longo das iterac¸o˜es do comando enquanto no Algoritmo 1, possuem
todas o mesmo centro. Ao final das iterac¸o˜es, e´ claro que T ′ possuira´ um ou
dois ve´rtices. Isto completa a demonstrac¸a˜o.
2.4 Pontes
Uma ponte ou aresta de corte de um grafoG e´ uma aresta e tal que w(G−e) >
w(G). Uma caracterizac¸a˜o alternativa de a´rvores pode ser formulada por
meio de pontes, como veremos a seguir.
Teorema 2.6. Uma aresta e e´ uma ponte de G se e somente se na˜o existe
ciclo contendo e em G.
Demonstrac¸a˜o. Suponha por absurdo que e e´ uma ponte de G e que
exista um ciclo C contendo e. Se existe um caminho P entre dois ve´rtices u
20
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
e v contendo a aresta e, enta˜o P ∪ (C − e) e´ um passeio entre u e v. Pelo
Exerc´ıcio 1.10, existe um caminho P ′ entre u e v que na˜o conte´m a aresta e.
Portanto, apo´s a remoc¸a˜o de e, continua havendo caminho entre todo par de
ve´rtices pertencentes a` componente conexa de G que continha e. Isto implica
w(G− e) = w(G), o que contradiz a hipo´tese de e ser uma ponte.
Suponha agora que na˜o exista ciclo contendo e em G. Escreva e = xy. Se
existisse algum caminho P entre x e y no grafo G − e, P + e seria um ciclo
em G contendo e, uma contradic¸a˜o.Logo, x e y pertencem a componentes
conexas distintas no grafo G− e, o que implica w(G− e) > w(G); em outras
palavras, e e´ uma ponte.
Teorema 2.7. Um grafo conexo T e´ uma a´rvore se e somente se toda aresta
de T e´ uma ponte.
Demonstrac¸a˜o. Suponha que T e´ uma a´rvore. Como T e´ um grafo ac´ıclico,
e´ claro que nenhuma aresta de T pode pertencer a um ciclo. Logo, pelo
Teorema 2.6, toda aresta de T e´ uma ponte.
Reciprocamente, se toda aresta de um grafo T e´ uma ponte, pelo Te-
orema 2.6 nenhuma delas pertence a um ciclo. Logo o grafo T e´ ac´ıclico.
Como por hipo´tese T e´ conexo, segue que T e´ uma a´rvore.
2.5 A´rvores geradoras
Uma a´rvore geradora de um grafo G e´ um subgrafo gerador conexo e ac´ıclico
de G.
Proposic¸a˜o 2.8. Todo grafo conexo possui uma a´rvore geradora.
Demonstrac¸a˜o. Seja G um grafo conexo. O seguinte algoritmo constro´i
uma a´rvore geradora de G.
Algoritmo 2: Algoritmo para determinar uma a´rvore geradora
Entrada: Um grafo conexo G
Sa´ıda: Uma a´rvore geradora T de G
T ← G
enquanto existe aresta e tal que T − e e´ conexo fac¸a T ← T − e
retornar T
21
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Observe que o grafo T retornado pelo Algoritmo 2 satisfaz V (T ) = V (G),
isto e´, T e´ um subgrafo gerador de G. Ale´m do mais, as sucessivas remoc¸o˜es
de arestas no comando enquanto preservam a conexidade de T ; logo, ao
final das iterac¸o˜es, T sera´ um subgrafo conexo. Finalmente, quando o teste
do comando enquanto falhar, todas as arestas remanescentes em T sera˜o
pontes; pelo Teorema 2.7, o grafo T retornado e´ uma a´rvore. Isto conclui a
demonstrac¸a˜o.
Teorema 2.9. Se G e´ conexo, enta˜o m ≥ n− 1.
Demonstrac¸a˜o. Pela Proposic¸a˜o 2.8, G possui uma a´rvore geradora T .
Obviamente, |V (T )| = n e |E(T )| = n − 1. Como |E(G)| = m e E(T ) ⊆
E(G), segue o resultado.
Conclu´ımos pelos Teoremas 2.3 e 2.9 que as a´rvores sa˜o os grafos conexos
que atingem o limite mı´nimo n− 1 para o nu´mero de arestas, no sentido de
que todo grafo com menos do que n−1 arestas e´ necessariamente desconexo.
Pode-se mostrar (Exerc´ıcio 2.8) que toda floresta e´ um subgrafo gerador
de uma a´rvore. Este resultado, juntamente com o Teorema 2.3, permite
enunciar:
Teorema 2.10. Se G e´ ac´ıclico, enta˜o m ≤ n− 1.
Pelos Teoremas 2.3 e 2.10, as a´rvores sa˜o os grafos ac´ıclicos que atingem
o limite ma´ximo n − 1 para o nu´mero de arestas, no sentido de que todo
grafo com mais do que n− 1 arestas conte´m pelo menos um ciclo.
Corola´rio 2.11. Seja G um grafo qualquer com n ve´rtices e m arestas.
Enta˜o:
(a) Se m < n− 1 enta˜o G e´ desconexo;
(b) Se m = n− 1 e G e´ conexo ou ac´ıclico enta˜o G e´ uma a´rvore;
(c) Se m > n− 1 enta˜o G conte´m pelo menos um ciclo.
Encerramos esta sec¸a˜o com este importante teorema:
Teorema 2.12. Seja T uma a´rvore geradora de um grafo conexo G, e seja
e ∈ E(G)\E(T ). Enta˜o, T + e conte´m um u´nico ciclo.
22
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Demonstrac¸a˜o. Escreva e = xy. Pelo Teorema 2.1, em T existe um u´nico
caminho P entre x e y. Logo, o subgrafo P + e e´ um ciclo em T + e. Se C e´
um outro ciclo em T +e, e´ claro que C conte´m a aresta e. Assim, C−e e´ um
caminho entre x e y em T , donde conclu´ımos que C − e e´ o pro´prio caminho
P , isto e´, os ciclos C e P + e sa˜o na verdade o mesmo ciclo.
2.6 Exerc´ıcios
2.1. Mostre que se G e´ uma a´rvore com ∆(G) ≥ k, enta˜o G conte´m pelo
menos k folhas.
2.2. Desenhe todas as a´rvores na˜o isomorfas com 7 ve´rtices.
2.3. Prove que um grafo e´ uma floresta se e somente se o seu nu´mero de
arestas e´ igual ao seu nu´mero de ve´rtices menos o seu nu´mero de com-
ponentes conexas.
2.4. Prove ou refute: Se G e´ ac´ıclico enta˜o G possui no mı´nimo 2(w(G)−
i(G)) ve´rtices de grau um, onde w(G) e´ o nu´mero de componentes
conexas de G e i(G) e´ o nu´mero de ve´rtices isolados de G.
2.5. Seja G um grafo conexo e e uma aresta de G. Mostre que e esta´ em
toda a´rvore geradora de G se e somente se e e´ uma ponte de G.
2.6. Mostre que se G tem exatamente uma a´rvore geradora T enta˜o G = T .
2.7. Mostre que qualquer grafo G = (V,E) conte´m pelo menos m − n + w
ciclos distintos, onde |V | = n, |E| = m e w e´ o nu´mero de componentes
conexas de G.
2.8. Mostre que toda floresta e´ um subgrafo gerador de uma a´rvore.
2.9. A cintura de um grafo G e´ o comprimento de seu menor ciclo. Se G
for ac´ıclico, sua cintura e´ infinita. Mostre que um grafo k-regular de
cintura 4 possui pelo menos 2k ve´rtices.
23
3 Conectividade
Neste cap´ıtulo estudaremos conjuntos especiais de ve´rtices e arestas cuja
remoc¸a˜o desconecta o grafo, no sentido de que o nu´mero de componentes
conexas aumenta apo´s a remoc¸a˜o.
3.1 Cortes de ve´rtices
Dado um grafo G, um conjunto de ve´rtices V ′ ⊆ V (G) e´ um separador ou
corte de ve´rtices de G se w(G− V ′) > w(G).
Observe que um grafo completo na˜o admite cortes de ve´rtices.
3.1.1 Articulac¸o˜es e blocos
Um caso especial importante ocorre quando o corte de ve´rtices e´ um con-
junto unita´rio. Um ve´rtice v e´ chamado de articulac¸a˜o ou ve´rtice de corte
quando w(G − v) > w(G). A seguir, vamos estudar algumas propriedades
relacionadas ao conceito de articulac¸a˜o.
Lema 3.1. Um ve´rtice v e´ uma articulac¸a˜o de um grafo se e somente se
existem dois ve´rtices distintos x, y tais que: (a) v /∈ {x, y}; (b) x, y e v esta˜o
na mesma componente conexa; (c) todo caminho entre x e y conte´m v.
Teorema 3.2. Em uma a´rvore T na˜o trivial, um ve´rtice v e´ uma articulac¸a˜o
se e somente se v na˜o e´ folha.
Corola´rio 3.3. Todo grafo conexo G na˜o trivial possui pelo menos dois
ve´rtices que na˜o sa˜o articulac¸o˜es.
Passemos agora ao estudo dos blocos. Um bloco de um grafo G e´ um
subgrafo B de G tal que B e´ maximal conexo sem articulac¸o˜es.
Observac¸a˜o 3.1. Um bloco B sempre contera´ uma ou mais articulac¸o˜es de
G, mas por definic¸a˜o elas na˜o sera˜o articulac¸o˜es em B.
Note que dois blocos distintos em um grafo teˆm no ma´ximo um ve´rtice
em comum; no caso de compartilharem um ve´rtice, tal ve´rtice sera´ necessa-
riamente uma articulac¸a˜o.
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Note tambe´m que cada aresta de um grafo G esta´ em um u´nico bloco.
Portanto, os blocos determinam uma partic¸a˜o de E(G).
Um bloco B de um grafo G e´ chamado de bloco folha se B conte´m uma
u´nica articulac¸a˜o de G.
3.1.2 Conectividade de ve´rtices
A conectividade de ve´rtices κ(G) de um grafo conexo G e´ a cardinalidade de
um corte de ve´rtices mı´nimo de G, desde que G na˜o seja completo.
Definimos κ(G) = n − 1 se G e´ um grafo completo com n ve´rtices, e
κ(G) = 0 se G e´ desconexo. Observe que, se G e´ trivial, κ(G) = 0.
Dizemos que G e´ p-conexo em ve´rtices para todo p ≤ κ(G). E´ claro que
todo grafo conexo e na˜o trivial e´ 1-conexo em ve´rtices. Ale´m disso, se G e´
conexo, e´ fa´cil ver que κ(G) = 1 se e somente se G conte´m pelo menos uma
articulac¸a˜o. Alternativamente, podemos enunciar:
Proposic¸a˜o 3.4. Um grafo G conexo com pelo menos treˆs ve´rtices e´ biconexo
se e somente se G na˜o possui articulac¸o˜es.
3.1.3 Caminhos internamente disjuntos em ve´rtices
Sejam u e v ve´rtices distintos de um grafo G. Dois caminhos de u a v
sa˜o chamados de internamente disjuntos (em ve´rtices) se eles teˆm apenas os
extremos u e v em comum.
Teorema 3.5. (Whitney, 1932) Seja G um grafo com pelo menos treˆs ve´rti-
ces. Enta˜o, G e´ biconexo se e somente se para quaisquer dois ve´rtices de G
existem dois caminhos internamente disjuntos entre eles.
Corola´rio 3.6. Um grafo G com pelo menos treˆs ve´rtices e´ biconexo se e
somente se existe um ciclo que passa por cada par de ve´rtices arbitra´rios de
G.
O seguinte teorema e´ uma generalizac¸a˜o do Teorema 3.5. Sua demons-
trac¸a˜o sera´ omitida.25
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Teorema 3.7. (Menger) Um grafo com pelo menos k+1 ve´rtices e´ k-conexo
em ve´rtices se e somente se para quaisquer dois ve´rtices de G existem k
caminhos internamente disjuntos entre eles.
3.2 Cortes de arestas
Um conjunto desconectante (de arestas) e´ um conjunto E ′ ⊆ E(G) tal que
w(G− E ′) > w(G).
Observe que toda ponte define um conjunto desconectante de arestas. E´
fa´cil ver que se e e´ uma ponte de um grafo G enta˜o w(G− e) = w(G) + 1.
Iremos estudar agora conjuntos desconectantes especiais, os cortes de
arestas. Para isso, precisamos da seguinte definic¸a˜o: Se S e T sa˜o subcon-
juntos de ve´rtices de um grafo, enta˜o [S, T ] e´ o conjunto de todas as arestas
de G que teˆm um extremo em S e outro em T .
Seja G um grafo. Um corte de arestas de G e´ qualquer conjunto na˜o vazio
da forma [S, S], onde S e´ um subconjunto pro´prio e na˜o vazio de ve´rtices de
G e S = V (G)\S.
E´ fa´cil ver que todo corte de arestas e´ um conjunto desconectante, mas
nem todo conjunto desconectante e´ um corte de arestas. O teorema a seguir
nos aponta conjuntos desconectantes especiais que sa˜o cortes de arestas.
Teorema 3.8. Todo conjunto desconectante minimal em um grafo G e´ um
corte de arestas.
Demonstrac¸a˜o. Assuma que G e´ conexo. Seja F um conjunto desconec-
tante minimal de G, e seja e ∈ F . Defina Fe = F \{e}. Pela minimalidade de
F , w(G−Fe) = w(G). Logo, e e´ uma ponte de G−Fe. Escreva e = xy. Sejam
Gx e Gy as componentes conexas de (G−Fe)− e contendo x e y, respectiva-
mente. Como a aresta e foi tomada genericamente e (G− Fe)− e = G− F ,
segue que para qualquer aresta e ∈ F as componentes conexas de (G−Fe)−e
sa˜o sempre as mesmas. Fazendo S = V (Gx) e S = V (Gy), segue que toda
aresta e ∈ F tem um extremo em S e outro em S. Logo, F = [S, S], isto e´,
F e´ um corte. A demonstrac¸a˜o se adapta facilmente para o caso em que G
e´ desconexo.
Note que toda ponte define um conjunto desconectante minimal de ares-
tas, e portanto um corte.
26
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
3.2.1 Ligac¸o˜es (ou co-ciclos)
Um corte de arestas minimal e´ tambe´m chamado de ligac¸a˜o (“bond”) ou
co-ciclo. Observe que toda ponte de um grafo G e´ um co-ciclo. A proposic¸a˜o
abaixo caracteriza co-ciclos em grafos conexos.
Proposic¸a˜o 3.9. Se G e´ conexo e S e´ um subconjunto pro´prio e na˜o va-
zio de V (G), enta˜o F = [S, S] e´ co-ciclo se e somente se G − F tem dois
componentes conexos.
Observac¸a˜o 3.2. Seja G um grafo qualquer. Denotemos por D(G) a famı´lia
de todos os conjuntos desconectantes de G, D′(G) a famı´lia de todos os
conjuntos desconectantes minimais de G, C(G) a famı´lia de todos os cortes
de arestas de G, e C′(G) a famı´lia de todas os co-ciclos de G. Vale enta˜o que:
D′(G) = C′(G) ⊆ C(G) ⊆ D(G).
Para a sequeˆncia desta sec¸a˜o, necessitamos das definic¸o˜es a seguir.
Seja H um subgrafo de um grafo G. O complemento de H em relac¸a˜o a
G e´ o grafo G− E(H).
Seja T uma a´rvore geradora de um grafo conexo G. A co-a´rvore de T e´
o complemento de T em relac¸a˜o a G. Denotamos por T a co-a´rvore de uma
a´rvore geradora T .
O teorema a seguir e´ o ana´logo do Teorema 2.12 aplicado a co-a´rvores e
co-ciclos:
Teorema 3.10. Seja T uma a´rvore geradora de um grafo conexo G. Enta˜o:
(a) T na˜o conte´m co-ciclos de G;
(b) Se e e´ uma aresta de T enta˜o T + e conte´m um u´nico co-ciclo de G.
3.2.2 Conectividade de arestas
A conectividade de arestas κ′(G) de um grafo conexo e na˜o trivial G e´ a
cardinalidade de um corte de arestas mı´nimo de G. Definimos κ′(G) = 0 se
G e´ trivial ou desconexo.
Assim como para ve´rtices, dizemos que um grafo G e´ p-conexo em arestas
para todo p ≤ κ′(G). Obviamente, todo grafo conexo na˜o trivial e´ 1-conexo
em arestas.
27
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Teorema 3.11. (Whitney, 1932) Seja G um grafo qualquer. Enta˜o,
κ(G) ≤ κ′(G) ≤ δ(G).
Demonstrac¸a˜o. Se G e´ desconexo ou trivial, κ(G) = κ′(G) = 0, e portanto
o teorema e´ va´lido. Assuma enta˜o que G e´ conexo e na˜o trivial.
Demonstremos inicialmente a desigualdade κ′(G) ≤ δ(G). Observe que
as arestas incidentes a um ve´rtice v de grau mı´nimo definem um corte de
arestas F = [S, S] onde S = {v} e |F | = δ(G). Logo, κ′(G) ≤ |F | = δ(G).
Passemos agora a` demonstrac¸a˜o da desigualdade κ(G) ≤ κ′(G). Seja
F = [S, S] um corte de arestas mı´nimo de G, isto e´, |F | = κ′(G). Como
F e´ um corte mı´nimo, F e´ um co-ciclo de G, e pela Proposic¸a˜o 3.9 o grafo
G−F tem exatamente duas componentes conexas, a saber, G[S] e G[S]. Seja
S1 = {x ∈ S | x e´ extremo de alguma aresta de F}. Analogamente, seja
S2 = {x ∈ S | x e´ extremo de alguma aresta de F}. A seguir, analisaremos
alguns casos.
Se S \ S1 conte´m algum ve´rtice y1, e´ fa´cil ver que no grafo G − S1 o
ve´rtice y1 encontra-se num componente conexa diferente de G[S] (observe
que a remoc¸a˜o de S1 acarreta a remoc¸a˜o de todas as arestas de F ). Logo, S1 e´
um corte de ve´rtices. Como |S1| ≤ |F |, segue que κ(G) ≤ |S1| ≤ |F | = κ
′(G).
No caso em que S \ S2 conte´m algum ve´rtice y2, a desigualdade κ(G) ≤
κ′(G) prova-se de maneira ana´loga.
Resta agora analisar o caso S = S1 e S = S2. Se existem y1 ∈ S1 e y2 ∈ S2
na˜o adjacentes, segue que o conjunto R = (S1 \ {y1})∪N(y1, S2) e´ um corte
de ve´rtices, pois sua remoc¸a˜o acarreta a remoc¸a˜o de todas as arestas de F
e deixa y1 e y2 em componentes conexas diferentes. Como |R| ≤ |F |, segue
que κ(G) ≤ |R| ≤ |F | = κ′(G).
Finalmente, se todos os ve´rtices de S1 sa˜o adjacentes a todos os ve´rtices
de S2, suponha |S1| = n1 e |S2| = n2, e considere y1 ∈ S1. Observe que
as arestas incidentes a y1 definem um corte de arestas F1 cujo tamanho e´
d(y1) ≤ n1 − 1 + n2. Como neste caso |S| = n1n2 e S e´ um corte mı´nimo,
segue que n1n2 ≤ n1−1+n2. Resolvendo esta desigualdade, segue que n1 = 1
ou n2 = 1. Assuma sem perda de generalidade n1 = 1, e considere y2 ∈ S2.
Novamente, as arestas incidentes a y2 definem um corte de arestas, e segue
enta˜o que n2 = |S| ≤ d(y2). Conclu´ımos assim que, neste caso, G e´ um grafo
28
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
completo. Para concluir a demonstrac¸a˜o, basta recordar que a desigualdade
κ(G) ≤ κ′(G) vale trivialmente em um grafo completo.
3.2.3 Caminhos disjuntos em arestas
A caracterizac¸a˜o de grafos k-conexos em ve´rtices por meio de caminhos in-
ternamente disjuntos em ve´rtices (Teorema 3.7) admite uma versa˜o ana´loga
para arestas:
Teorema 3.12. (Menger - versa˜o arestas) Um grafo G e´ k-conexo em ares-
tas se e somente se para quaisquer dois ve´rtices de G existem k caminhos
disjuntos em arestas entre eles.
3.3 Exerc´ıcios
3.1. Prove: qualquer conjunto de 7 arestas no grafo K3,3 e´ um conjunto
desconectante, mas na˜o um corte.
3.2. Prove ou refute: O grafo K4,4 na˜o possui corte com exatamente 10
arestas.
3.3. Mostre que se G e´ conexo e na˜o trivial, qualquer a´rvore geradora T de
G e qualquer conjunto desconectante na˜o vazio F ⊆ E(G) tera˜o pelo
menos uma aresta em comum.
3.4. Determine κ(G) e κ′(G) para os grafos abaixo. Para cada p, que grafos
sa˜o p-conexos em ve´rtices? Que grafos sa˜o p-conexos em arestas?
3.5. Prove que se G e´ 3-regular, enta˜o κ(G) = κ′(G).
3.6. Existe algum grafo G que e´ 3-regular, 3-conexo em arestas e na˜o 3-
conexo em ve´rtices?
29
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
3.7. Prove que o grafo de Petersen e´ 3-conexo em ve´rtices.
3.8. Prove ou refute: Se G e´ conexo e possui exatamente dois ve´rtices que
na˜o sa˜o articulac¸o˜es, enta˜o G e´ um caminho.
3.9. Um cacto e´ um grafo conexo no qual todo bloco e´ uma aresta ou um
ciclo. Prove que o nu´mero ma´ximo de arestas num cacto com n ve´rtices
e´ ⌊3(n− 1)/2⌋. Dica: ⌊x⌋ + ⌊y⌋ ≤ ⌊x+ y⌋.30
4 Grafos Eulerianos e Hamiltonianos
Neste cap´ıtulo estudaremos dois tipos especiais de passeios em grafos. O
primeiro tipo e´ formado pelos passeios que visitam todas as arestas do grafo,
sem repetic¸o˜es, e o segundo pelos passeios fechados que visitam todos os
ve´rtices, tambe´m sem repetic¸o˜es (a menos dos ve´rtices inicial e final, claro).
Como nem todo grafo admitira´ tais tipos de passeios, veremos sob quais
condic¸o˜es garante-se sua existeˆncia.
4.1 Grafos Eulerianos
Um passeio Euleriano ou passeio de Euler ou trilha Euleriana ou trilha de
Euler de um grafo G e´ uma trilha fechada que conte´m cada aresta de G
exatamente uma vez.
Um grafo e´ Euleriano se ele possui uma trilha de Euler.
Teorema 4.1. (Euler, 1736) Um grafo G conexo e´ Euleriano se e somente
se todo ve´rtice de G possui grau par.
Demonstrac¸a˜o. Assuma que G na˜o e´ trivial. A demonstrac¸a˜o da ne-
cessidade e´ simples: numa trilha Euleriana, cada ocorreˆncia de um ve´rtice v
interno a` trilha acrescenta duas unidades ao grau de v. Ale´m disso, e´ fa´cil ver
que o ve´rtice inicial (e final) da trilha tambe´m tem grau par. A demonstrac¸a˜o
da suficieˆncia consiste em executar o Algoritmo de Tucker: particionar G em
ciclos e compor os ciclos ate´ formar uma trilha Euleriana. Este algoritmo e´
O(m). Estes sa˜o os passos do algoritmo:
(a) Se todos os ve´rtices de G teˆm grau par, G na˜o conte´m folhas. Logo, pelo
Teorema 2.2, G na˜o pode ser uma a´rvore. Como G e´ conexo, G deve conter
um ciclo C1. Note que todos os ve´rtices do grafo G1 = G − E(C1) tambe´m
possuem grau par. Eventualmente, G1 podera´ conter ve´rtices isolados, e ate´
ser um grafo sem arestas; mas, se E(G1) 6= ∅, nenhuma das componentes
conexas na˜o triviais de G1 sera´ a´rvore, e nesse caso G1 contera´ um ciclo
C2. O racioc´ıcio se aplica novamente ao grafo G2 = G1 − E(C2), e assim
sucessivamente. No final, para um certo valor de k, Gk sera´ um grafo sem
arestas e a colec¸a˜o C = {C1, C2, . . . , Ck} define uma partic¸a˜o das arestas de
G em ciclos.
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
(b) Como um ciclo e´ um caso particular de trilha fechada, a colec¸a˜o C pode
ser vista agora como uma colec¸a˜o de trilhas fechadas. Como G e´ conexo, se
k ≥ 2 e´ claro que existem duas trilhas desta colec¸a˜o que compartilham um
ve´rtice comum. Assuma sem perda de generalidade que Ck−1 e Ck possuam
um ve´rtice em comum. Estas trilhas podem ser facilmente concatenadas, re-
sultando numa u´nica trilha fechada C ′k−1. Novamente, se k−1 ≥ 2, deve ha-
ver duas trilhas na colec¸a˜o {C1, . . . , Ck−2, C
′
k−1} compartilhando um ve´rtice
comum, digamos Ck−2 e C
′
k−1. A concatenac¸a˜o destas duas trilhas numa
nova trilha fechada C ′k−2 resulta numa nova colec¸a˜o {C1, . . . , Ck−3, C
′
k−2}. O
processo continua ate´ que haja uma u´nica trilha fechada C ′1 contendo todas
as arestas de G, exatamente uma vez cada.
Observac¸a˜o 4.1. O Teorema 4.1 vale tambe´m para multigrafos.
Enunciamos a seguir um problema de log´ıstica bastante conhecido, que
pode ser resolvido por algoritmos de tempo polinomial no tamanho do grafo
de entrada.
Problema do Carteiro Chineˆs: Dado um grafoG com pesos na˜o negativos
nas arestas, deseja-se um passeio fechado de comprimento mı´nimo que passe
por todas as arestas de G.
Um algoritmo para a soluc¸a˜o do problema acima consiste em executar os
seguintes passos:
1. Localizar os ve´rtices de grau ı´mpar em G. Sejam v1, v2, . . . , vk estes
ve´rtices. Como o nu´mero de ve´rtices de grau ı´mpar em qualquer grafo e´ par,
k e´ par.
2. Construir um grafo auxiliar completo G′ tal que V (G′) = {v1, v2, . . . , vk}
e o peso de uma aresta vivj , i < j, e´ igual ao custo cij de um caminho de
custo mı´nimo Pij entre vi e vj em G.
3. Determinar um emparelhamento de custo mı´nimo M ′ em G′. (Para mais
informac¸o˜es sobre emparelhamentos, consultar o pro´ximo cap´ıtulo.)
4. Para cada aresta vivj ∈ M
′, acrescentar a G as arestas de Pij. E´ fa´cil
ver que o multigrafo resultante G+ e´ Euleriano. Uma trilha Euleriana de
G+, que pode ser obtida utilizando o algoritmo de Tucker, e´ uma soluc¸a˜o do
problema. O custo desta trilha sera´
∑
e∈E(G) custo(e) +
∑
vivj∈M ′
cij.
32
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Todas as estapas do algoritmo descrito acima podem ser executadas em
tempo polinomial. Portanto, o Problema do Carteiro Chineˆs pertence a` classe
P .
4.1.1 Passeios Eulerianos abertos
Um passeio Euleriano aberto e´ um passeio aberto em G tal que toda aresta
de G ocorre exatamente uma vez no passeio.
Corola´rio 4.2. Um grafo conexo G admite um passeio Euleriano aberto se
e somente se existem exatamente dois ve´rtices de grau ı´mpar em G.
Demonstrac¸a˜o. A demonstrac¸a˜o da necessidade e´ trivial. Para a de-
monstrac¸a˜o da suficieˆncia, sejam u e v os dois ve´rtices de grau ı´mpar em G.
Considere um grafo auxiliar G′ constru´ıdo a partir de G pelo acre´scimo de
um novo ve´rtice x e arestas ux, vx. E´ claro que G′ e´ Euleriano. Pelo Teo-
rema 4.1, seja T ′ uma trilha Euleriana de G′. A remoc¸a˜o de x da trilha T ′
(juntamente com as arestas ux e vx) resulta em um passeio Euleriano aberto
em G.
4.2 Grafos Hamiltonianos
Um ciclo [caminho] Hamiltoniano em um grafo G e´ um ciclo [caminho] que
conte´m todos os ve´rtices de G, uma vez cada. O grafo G e´ Hamiltoniano
quando possui um ciclo Hamiltoniano.
E´ fa´cil observar que todo grafo Hamiltoniano e´ biconexo.
O teorema a seguir fornece uma condic¸a˜o necessa´ria para a Hamiltonici-
dade de um grafo.
Teorema 4.3. Se G e´ um grafo Hamiltoniano enta˜o todo subconjunto
S ⊆ V (G) pro´prio e na˜o vazio satisfaz w(G− S) ≤ |S|.
Demonstrac¸a˜o. Considere um ciclo Hamiltoniano C em G. Seja S um sub-
conjunto de ve´rtices de G, pro´prio e na˜o vazio. Denotemos por G1, . . . , Gk as
componentes conexas de G − S, e sejam P1, . . . , Pk subcaminhos maximais
de C onde V (Pi) ⊆ V (Gi), 1 ≤ i ≤ k. Observe que o ve´rtice ui que imediata-
mente precede Pi em C na˜o pode pertencer a nenhuma componente conexa
33
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Gj, j 6= i, caso contra´rio haveria uma aresta conectando estas componentes.
Logo, {u1, . . . , uk} ⊆ S. Ale´m disso, os ui’s sa˜o mutuamente distintos. Logo
w(G− S) = k ≤ |S|.
Exemplo 4.1. Considere o grafo G na Figura 4.1. Este grafo e´ chamado
grafo de Petersen. Observe que para todo S ⊆ V (G), pro´prio e na˜o vazio,
vale w(G − S) ≤ |S|. No entanto, G na˜o e´ Hamiltoniano. Isto mostra que
a condic¸a˜o do Teorema 4.3, embora seja necessa´ria, na˜o e´ uma condic¸a˜o
suficiente para um grafo ser Hamiltoniano.
1
2
34
5
6
7
89
10
Figura 4.1: O grafo de Petersen na˜o e´ Hamiltoniano.
Veremos agora algumas condic¸o˜es suficientes para a Hamiltonicidade de
um grafo.
Teorema 4.4. (Dirac, 1952) Todo grafo com n ≥ 3 e δ(G) ≥ n/2 tem um
ciclo Hamiltoniano.
Teorema 4.5. (Ore, 1960) Se G e´ um grafo com n ≥ 3 e tal que para todo
par de ve´rtices distintos na˜o adjacentes u e v vale d(u) + d(v) ≥ n, enta˜o G
e´ Hamiltoniano.
Observe que o Teorema de Ore e´ mais forte do que o de Dirac, no sentido
de que o Teorema de Dirac e´ um corola´rio do Teorema de Ore. Demonstra-
remos enta˜o o Teorema de Ore.
Demonstrac¸a˜o do Teorema 4.5. Suponha o teorema falso. Seja G um
grafo com pelo menos treˆs ve´rtices e tal que d(u)+d(v) ≥ n para todo par u, v
de ve´rtices na˜o adjacentes, e suponha que G e´ na˜o Hamiltoniano maximal.
34
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
E´ claro que G na˜o e´ um grafo completo. Escolha um par u, v de ve´rtices
na˜o adjacentes de G, e considere o grafo G + uv. Pela maximalidade de G,
segue que G + uv e´ Hamiltoniano. Ale´m do mais, todo ciclo Hamiltoniano
de G+ uv conte´m uv.
Claramente, G conte´m um caminhoHamiltoniano v1, v2, . . . , vn com v1 =
u e vn = v. Sejam S = {vi | uvi+1 ∈ E(G)} e T = {vi | viv ∈ E(G)}.
Observe que vn 6∈ S e vn 6∈ T . Logo, |S ∪ T | < n. Ale´m disso, temos
que |S ∩ T | = 0, pois se existisse vi ∈ S ∩ T o grafo G conteria o ciclo
Hamiltoniano v1v2 . . . vivnvn−1 . . . vi+1v1. (Veja a Figura 4.2.) Assim,
d(u) + d(v) = |S|+ |T | = |S ∪ T |+ |S ∩ T | < n.
Mas isto contradiz a hipo´tese do teorema.
u = v1 v2 vi vi+1 vn−1 vn = v
Figura 4.2: Demonstrac¸a˜o do Teorema 4.5.
Um racioc´ınio alternativo para a demonstrac¸a˜o acima consiste em utilizar
o Princ´ıpio Combinato´rio da Casa de Pombo:
“Se existirem n pombos em m < n casas, enta˜o existe
pelo menos uma casa com no mı´nimo dois pombos.”
Observe que vn 6∈ S ∪ T , d(u) = |S|, d(v) = |T | e d(u) + d(v) ≥ n.
Temos assim n − 1 “casas” numeradas de 1 a n − 1 (´ındices), onde vamos
distribuir os elementos de S e T , em quantidade maior do que n−1 (levando
em conta poss´ıveis elementos repetidos). Um certo ı´ndice i devera´ estar
portanto associado a dois elementos ideˆnticos, um de S e outro de T . Isto e´,
devera´ existir vi ∈ S ∩ T . Mas vimos que isto gera uma contradic¸a˜o.
Descreveremos agora uma condic¸a˜o necessa´ria e suficiente para Hamil-
tonicidade. Antes, precisaremos de uma nova definic¸a˜o e dois lemas prepa-
rato´rios.
35
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
O fecho de um grafo G e´ o grafo C(G) obtido de G por sucessivas adic¸o˜es
de arestas ligando pares de ve´rtices na˜o adjacentes cuja soma de graus seja
maior ou igual a n.
Exemplo 4.2. Se G e´ o grafo formado pelo ciclo a, b, c, d, e, f, a acrescido das
cordas ac e ae enta˜o C(G) e´ o grafo K6. Uma poss´ıvel sequeˆncia de arestas
a serem acrescentadas na determinac¸a˜o do fecho e´: ad, ec, eb, cf, bf, df, bd.
Lema 4.6. C(G) e´ bem definido (u´nico).
Demonstrac¸a˜o. Sejam G1 = G+{e1, e2, . . . , ek} e G2 = G+{f1, f2, . . . , fl}
dois grafos obtidos pela aplicac¸a˜o exaustiva de adic¸o˜es de arestas de acordo
com a regra de construc¸a˜o do fecho de um grafo. Suponha que exista alguma
aresta em G1 que na˜o esteja em G2. Seja ej a primeira aresta da sequeˆncia
e1, e2, . . . , ek que na˜o pertence a G2. Escreva ej = uv, e defina H = G +
{e1, . . . , ej−1}. E´ claro que dH(u)+dH(v) ≥ n, pois ej devera´ ser acrescentada
a H . Observe tambe´m que H e´ um subgrafo de G2, pois por definic¸a˜o todas
as arestas e1, . . . , ej−1 esta˜o em G2. Logo, dG2(u) + dG2(v) ≥ n. Mas isto
implica que ej = uv deve ser acrescentada a G2, uma contradic¸a˜o. Logo toda
aresta de G1 esta´ em G2, e de modo ana´logo pode-se provar que toda aresta
de G2 esta´ em G1.
Lema 4.7. Seja G um grafo e a, b dois ve´rtices na˜o adjacentes de G satis-
fazendo d(a) + d(b) ≥ n. Enta˜o, G e´ Hamiltoniano se e somente se G + ab
e´ Hamiltoniano.
Demonstrac¸a˜o. A prova da necessidade e´ trivial. A prova da suficieˆncia
segue diretamente da demonstrac¸a˜o do Teorema de Ore: se G+ ab e´ Hamil-
toniano enta˜o G possui um caminho Hamiltoniano iniciando no ve´rtice a e
terminando no ve´rtice b. A partir da´ı podemos construir dois conjuntos S
e T exatamente como na demonstrac¸a˜o do Teorema 4.5, e concluir que G e´
Hamiltoniano.
Finalmente, podemos enunciar:
Teorema 4.8. (Bondy e Chva´tal, 1976) Um grafo G e´ Hamiltoniano se e
somente se C(G) e´ Hamiltoniano.
Demonstrac¸a˜o. A prova da necessidade e´ trivial. Ja´ a prova da su-
ficieˆncia consiste em sucessivas aplicac¸o˜es do Lema 4.7. Escreva C(G) =
36
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
G+{u1v1, u2v2, . . . , ukvk}. Defina G0 = G e Gj = G+{u1v1, u2v2, . . . , ujvj},
1 ≤ j ≤ k. Como dGk−1(uk) + dGk−1(vk) ≥ n e Gk e´ um grafo Hamilto-
niano, segue pelo Lema 4.7 que Gk−1 e´ Hamiltoniano. Da mesma forma,
como dGk−2(uk−1) + dGk−2(vk−1) ≥ n e Gk−1 e´ Hamiltoniano, segue que Gk−2
e´ Hamiltoniano. Aplicando sucessivamente este racioc´ıcio, conclu´ımos que
G0, G1, . . . , Gk sa˜o todos Hamiltonianos.
O seguinte corola´rio sera´ u´til em muitos casos:
Corola´rio 4.9. Se C(G) e´ completo enta˜o G e´ Hamiltoniano.
Conclu´ımos este cap´ıtulo enunciando um dos problemas mais importantes
da Cieˆncia da Computac¸a˜o, devido a suas va´rias aplicac¸o˜es. “E´ um problema
de otimizac¸a˜o NP-dif´ıcil inspirado na necessidade dos vendedores em realiza-
rem entregas em diversos locais (as cidades) percorrendo o menor caminho
poss´ıvel, reduzindo o tempo necessa´rio para a viagem e os poss´ıveis custos
com transporte e combust´ıvel.” (Fonte: Wikipedia)
Problema do Caixeiro Viajante: Dado um grafo completo G com pesos
nas arestas, deseja-se obter um ciclo Hamiltoniano de G com peso mı´nimo.
4.3 Exerc´ıcios
4.1. Existe algum grafo euleriano com n par e m ı´mpar? Em caso positivo,
descreva-o. Em caso negativo, justificar a na˜o existeˆncia.
4.2. Prove que se G e´ 4-regular enta˜o G na˜o conte´m pontes.
4.3. Verdadeiro ou Falso? Se G e´ bipartido e 3-regular enta˜o G na˜o conte´m
pontes.
4.4. Se G e´ um grafo euleriano com arestas e1 e e2 que teˆm um ve´rtice em
comum, enta˜o G tem uma trilha Euleriana no qual e1 e e2 aparecem
consecutivamente? Prove, se for verdadeiro. Caso contra´rio justifique
convenientemente.
4.5. Verdadeiro ou Falso? Se G e´ Euleriano, enta˜o todo bloco de G e´ Eule-
riano.
4.6. Verdadeiro ou Falso? Todo bloco de um grafo G possui caminho Ha-
miltoniano.
37
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
4.7. Uma grade de dimensa˜o p×q (onde p, q sa˜o inteiros tais que p, q ≥ 2) e´
um grafo G em que V (G) e´ o subconjunto dos pontos de coordenadas
inteiras (x, y), 1 ≤ x ≤ p e 1 ≤ y ≤ q, e tal que se dois ve´rtices sa˜o
adjacentes enta˜o a distaˆncia entre os pontos respectivos e´ um. Uma
grade completa conte´m todas as arestas poss´ıveis.
Mostre que uma grade completa e´ um grafo hamiltoniano se e somente
se p.q for par.
4.8. Um grafo G e´ hipo-hamiltoniano quando G − v e´ hamiltoniano para
todo ve´rtice v, mas G na˜o o e´. Justificar porque o grafo de Petersen e´
hipo-hamiltoniano.
4.9. O grafos abaixo sa˜o Hamiltonianos?
4.10. Proponha alterac¸o˜es mı´nimas no conjunto de arestas de cada grafo do
exerc´ıcio anterior de modo a converter sua Hamiltonicidade em na˜o-
Hamiltonicidade, ou o contra´rio.
4.11. Um passeio fechado de cavalo e´ uma sequeˆncia de movimentos de cavalo
em um tabuleiro com m linhas e n colunas, onde, partindo de uma casa
inicial e sem passar duas vezes pela mesma casa, o cavalo retorna a` casa
inicial apo´s visitar todas as casas do tabuleiro. Pergunta-se: o tabuleiro
4× 4 admite um passeio de cavalo fechado?
38
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
4.12. Estude o problema da questa˜o anterior, verificando para quais valores
de m e n o tabuleiro m× n admite um passeio de cavalo fechado.
39
5 Emparelhamentos
O conceito de emparelhamento e´ muito u´til para modelar problemas de
alocac¸a˜o em pares de objetos: opera´rios/ma´quinas, turmas/salas-de-aula,
professores/disciplinas, processadores pareados etc. Em muitas aplicac¸o˜es, o
grafo subjacente e´ naturalmente bipartido. Pore´m, iniciaremos nosso estudo
em grafos gerais.
5.1 Definic¸a˜o de emparelhamento
Dado um grafo G, um emparelhamento de G e´ um subconjunto M ⊆ E(G)
que na˜o conte´m arestas com extremos em comum. Em outras palavras, G[M ]
e´ um grafo 1-regular se M 6= ∅.
Um emparelhamento M satura um ve´rtice v se alguma aresta de M e´
incidente a v. Neste caso, v e´ ditoM-saturado, ou simplesmente emparelhado.
Caso contra´rio, v e´ M-insaturado.
Um emparelhamento M sera´ maximal se na˜o existir nenhum outro que
o contenha propriamente, e sera´ ma´ximo se na˜o existir nenhum outro de
cardinalidade maior. E´ claro que todo emparelhamento ma´ximo e´ maximal,
mas nem todo emparelhamento maximal e´ ma´ximo.
5.2 Teorema de Berge
Nesta sec¸a˜o estudaremosum modo de caracterizar emparelhamentos ma´xi-
mos em grafos gerais.
Seja M um emparelhamento em um grafo G. Um caminho M-alternante
em G e´ um caminho tal que suas arestas alternadamente pertencem a M ou
na˜o. Este caminho sera´ ditoM-aumentante se os seus extremos inicial e final
na˜o sa˜o M-saturados.
O comprimento de um caminho M-aumentante e´ sempre ı´mpar. Ale´m
disso, a existeˆncia de um caminho M-aumentante P indica uma forma de
construir um emparelhamento M ′ com |M ′| > |M |. Basta remover de M as
arestas de E(P ) ∩M , e a seguir acrescentar as arestas de E(P ) \M . Esta
operac¸a˜o pode ser melhor formalizada utilizando a diferenc¸a sime´trica de
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
conjuntos. A diferenc¸a sime´trica entre dois conjuntos A e B, denotada por
A△ B, e´ definida da seguinte forma:
A△ B = (A \B) ∪ (B \ A) = (A ∪B) \ (A ∩B).
Assim, utilizando a notac¸a˜o acima, o emparelhamento M ′ e´ definido pre-
cisamente como M ′ =M △ E(P ). Observe que |M ′| = |M |+ 1.
O teorema seguir relaciona o conceito de caminhos M-aumentantes com
emparelhamentos ma´ximos.
Teorema 5.1. (Berge, 1957) Um emparelhamento M em um grafo G e´
ma´ximo se e somente se G na˜o conte´m nenhum caminho M-aumentante.
5.3 Teorema de Tutte
Um emparelhamento e´ perfeito se satura todo ve´rtice do grafo. Obviamente,
todo emparelhamento perfeito e´ ma´ximo. Ale´m disso nem todo grafo ad-
mite emparelhamento perfeito; por exemplo, um grafo com nu´mero ı´mpar de
ve´rtices na˜o admite emparelhamento perfeito. O grafo K1,3, embora tenha
nu´mero par de ve´rtices, tambe´m na˜o admite emparelhamento perfeito.
O pro´ximo teorema fornece uma condic¸a˜o necessa´ria e suficiente para
a existeˆncia de um emparelhamento perfeito em um grafo. Mas antes e´
necessa´rio apresentar alguns conceitos.
Uma componente conexa H de um grafo G e´ uma componente ı´mpar
se o nu´mero de ve´rtices de H e´ ı´mpar. Denotamos por o(G) o nu´mero de
componentes ı´mpares de um grafo G.
Sejam S um subconjunto pro´prio de V (G) e M um emparelhamento de
G, e considere uma componente ı´mpar H de G − S. Observe que, se M
satura todos os ve´rtices de H , pelo menos um deles deve estar emparelhado
com algum ve´rtice de S. Obviamente, no ma´ximo |S| ve´rtices podem estar
emparelhados com ve´rtices de G − S. Logo, pelo menos o(G − S) − |S|
componentes ı´mpares conteˆm ve´rtices M-insaturados. Se UM e´ o conjunto
de ve´rtices M-insaturados, temos que
|UM | ≥ o(G− S)− |S|, para todo S ⊂ V (G).
41
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Note que |UM | = n − 2|M |. Se a igualdade for verificada na expressa˜o
acima para algum subconjunto pro´prio S = B, isto e´, |UM | = o(G−B)−|B|,
tal subconjunto B e´ precisamente um certificado de que o emparelhamento
M produz o menor nu´mero poss´ıvel de ve´rtices insaturados. Em outras
palavras, B e´ um certificado de que M e´ ma´ximo. Neste caso, dizemos que
B e´ uma barreira de G. Pode-se provar que qualquer grafo G possui uma
barreira. Este resultado e´ conhecido como Teorema de Tutte-Berge, e sera´
utilizado como ferramenta na prova do pro´ximo teorema.
Teorema 5.2. (Tutte, 1947) Um grafo G admite um emparelhamento per-
feito se e somente se
o(G− S) ≤ |S|, para todo S ⊆ V (G).
Um corola´rio do teorema acima e´ o conhecido Teorema de Petersen, de
1891:
Teorema 5.3. (Petersen, 1891) Todo grafo 3-regular sem pontes conte´m um
emparelhamento perfeito.
5.4 Teorema de Hall
Passamos agora a estudar emparelhamentos em grafos bipartidos. Iniciamos
com o seguinte problema, conhecido como o Problema do Casamento:
“Dado um conjunto Y de rapazes e um conjunto X de moc¸as com |Y | ≥ |X|,
qual e´ a condic¸a˜o necessa´ria e suficiente para que cada moc¸a se case com um
rapaz de que ela goste?”
A resposta para esta questa˜o esta´ no pro´ximo teorema. Dado um sub-
conjunto S de ve´rtices de um grafo G, denotamos por N(S) ao conjunto de
todos os ve´rtices adjacentes a ve´rtices de S.
Teorema 5.4. (Hall, 1935) Seja G um grafo bipartido com partic¸a˜o de
ve´rtices V (G) = X ∪ Y . Enta˜o, G conte´m um emparelhamento que satura
todo ve´rtice de X se e somente se
|N(S)| ≥ |S|, para todo S ⊆ X.
Corola´rio 5.5. Se G e´ um grafo bipartido k-regular, k > 0, enta˜o G admite
um emparelhamento perfeito.
42
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
5.5 Teorema de Ko¨nig
Vamos agora apresentar uma condic¸a˜o que permite confirmar que um dado
emparelhamento em um grafo bipartido e´ de fato ma´ximo. Esta confirmac¸a˜o
se dara´ pela existeˆncia de um certificado baseado no conceito de cobertura.
Uma cobertura de um grafo G e´ um conjunto K ⊆ V (G) tal que toda
aresta de G tem pelo menos um de seus extremos em K. A cobertura sera´
mı´nima se na˜o houver nenhuma outra de cardinalidade menor.
Proposic¸a˜o 5.6. Para qualquer emparelhamento M e para qualquer cober-
tura K de um grafo G vale |M | ≤ |K|.
O seguinte lema sera´ u´til, e decorre imediatamente da proposic¸a˜o anterior.
Lema 5.7. Sejam M um emparelhamento e K uma cobertura de um grafo
G tais que |M | = |K|. Enta˜o, M e´ ma´ximo e K e´ mı´nima.
O pro´ximo teorema diz que, para os grafos bipartidos, a igualdade do
lema anterior e´ sempre atingida.
Teorema 5.8. (Ko¨nig, 1931) Em um grafo bipartido, o nu´mero de arestas em
um emparelhamento ma´ximo e´ igual ao nu´mero de ve´rtices em uma cobertura
mı´nima.
O problema de determinar um emparelhamento ma´ximo em um grafo
bipartido pode ser resolvido pelo Algoritmo de Egerva´ry, tambe´m conhe-
cido como Algoritmo Hu´ngaro. Este algoritmo e´ de tempo polinomial e de-
volve, juntamente com o emparelhamento ma´ximo, uma cobertura mı´nima
de mesmo tamanho, que serve como um certificado de sua corretude.
5.6 Exerc´ıcios
5.1. Determine condic¸o˜es necessa´rias e suficientes para que uma a´rvore pos-
sua um emparelhamento perfeito.
5.2. Mostre que se G e´ Hamiltoniano e 3-regular enta˜o G tem emparelha-
mento perfeito.
43
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
5.3. Duas pessoas disputam um jogo sobre um grafo G escolhendo alter-
nadamente ve´rtices distintos v1, v2, . . . formando um caminho. Ganha
quem for a u´ltima pessoa a conseguir escolher um ve´rtice.
(a) Mostre que quem comec¸a o jogo tem um estrate´gia vencedora caso
G na˜o tenha emparelhamento perfeito.
(b) Mostre que a segunda a jogar tem uma estrate´gia vencedora caso
G tenha um emparelhamento perfeito.
5.4. Um k-fator de G e´ um subgrafo gerador k-regular de G. Um grafo e´
k-fatora´vel se existirem k-fatores disjuntos em arestas H1, H2, ..., Hp,
tal que G = H1 ∪H2 ∪ ... ∪Hp. Responda, justificando:
(i) Kn,n e´ 1-fatora´vel?
(ii) K4,4 e´ 2-fatora´vel?
5.5. Seja um tabuleiro de xadrez de dimensa˜o 8 × 8, em que dois cantos
opostos (isto e´, os extremos 1 × 1 de uma mesma diagonal) foram
retirados. Moste que e´ imposs´ıvel cobrir este tabuleiro com retaˆngulos
de dimensa˜o 1× 2.
44
6 Colorac¸a˜o de Ve´rtices
6.1 Grafos k-color´ıveis
Uma k-colorac¸a˜o de ve´rtices e´ uma atribuic¸a˜o de k cores aos ve´rtices de um
grafo. Esta colorac¸a˜o e´ pro´pria quando ve´rtices adjacentes recebem cores
distintas.
Uma k-colorac¸a˜o pro´pria particiona o conjunto de ve´rtices do grafo em k
conjuntos independentes.
Um grafo G e´ k-color´ıvel se G admite uma k-colorac¸a˜o pro´pria de ve´rtices.
O nu´mero croma´tico de G, denotado por χ(G), e´ o menor inteiro k para o
qual G e´ k-color´ıvel. Obviamente, χ(G) ≤ n. Teremos χ(G) = n se e somente
se G = Kn.
6.2 Grafos cr´ıticos
Um grafo G e´ cr´ıtico se χ(H) < χ(G) para todo subgrafo pro´prio H de G.
Um grafo G e´ k-cr´ıtico quando for cr´ıtico e k-croma´tico.
Observe que todo grafo cr´ıtico e´ conexo, e todo grafo k-croma´tico tem
um subgrafo k-cr´ıtico.
Teorema 6.1. Se G e´ k-cr´ıtico enta˜o δ(G) ≥ k − 1.
Demonstrac¸a˜o.Seja v um ve´rtice de grau mı´nimo em G, isto e´, d(v) =
δ(G). Como G e´ k-cr´ıtico, χ(G − v) ≤ k − 1. Considere uma (k − 1)-
colorac¸a˜o de G− v que define uma partic¸a˜o de V (G− v) em k− 1 conjuntos
independentes V1, V2, . . . , Vk−1. Claramente, devemos ter Vi 6= ∅ para todo
i ∈ {1, . . . , k − 1}, caso contra´rio G na˜o teria nu´mero croma´tico igual a k.
Observe que, para todo i ∈ {1, . . . , k − 1}, deve existir em G uma aresta
de v para algum ve´rtice em Vi, pois se v na˜o fosse conectado a nenhum ve´rtice
de Vi ter´ıamos que Vi∪{v} seria um conjunto independente em G, e portanto
G seria (k − 1)-color´ıvel, o que e´ uma contradic¸a˜o. Logo, d(v) ≥ k − 1, e o
teorema vale.
Corola´rio 6.2. Todo grafo k-croma´tico possui pelo menos k ve´rtices de grau
maior ou igual a k − 1.
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Demonstrac¸a˜o. Todo grafo k-croma´tico G conte´m um subgrafo k-cr´ıtico
H . (Para provar este fato, basta remover sucessivamente arestas ou ve´rtices
isolados enquanto o grafo na˜o e´ cr´ıtico.) Como χ(H) = k, o subgrafo H
conte´m pelo menos k ve´rtices. Como H e´ k-cr´ıtico, pelo Teorema 6.1 todos
estes ve´rtices teˆm grau pelo menos k − 1.
6.3 Cotas para o nu´mero croma´tico
Iniciamos esta sec¸a˜o exibindo cotas inferiores para o nu´mero croma´tico.
Proposic¸a˜o 6.3. Para qualquer grafo G, vale que:
(a) χ(G) ≥ ω(G), onde ω(G) e´ o nu´mero de ve´rtices da maior clique de G.
(b) χ(G) ≥ n
α(G)
, onde α(G) e´ o numero de ve´rtices do maior conjunto
independente de G.
A pro´xima proposic¸a˜o exibe um limite superior simples para o nu´mero
croma´tico.
Proposic¸a˜o 6.4. Para qualquer grafo G, vale que χ(G) ≤ ∆(G) + 1.
6.3.1 Construc¸a˜o de Mycielski
Seja G um grafo com n ve´rtices v1, v2, . . . , vn. O grafo de Mycielski de G,
denotado por µ(G), e´ formado por uma co´pia de G mais n+1 ve´rtices novos
w, u1, u2, . . . , un conectados da seguinte forma: cada ui e´ conectado a w e a
todos os vizinhos de vi em G.
A construc¸a˜o de Mycielski, concebida pelo matema´tico Jan Mycielski em
1955, consiste numa sequeˆncia de grafos M2,M3,M4, . . . tal que M2 = K2 e
Mk = µ(Mk−1) para k ≥ 3. Assim, teremos: M2 = K2, M3 = C5, e M4 e´ o
grafo de Gro¨tzsch, representado na Figura 6.1.
A construc¸a˜o de Mycielski e´ importante porque mostra que o nu´mero
croma´tico pode se afastar arbitrariamente do tamanho da maior clique (veja
Proposic¸a˜o 6.3(a)). Pode-se provar que ω(Mk) = 2 e χ(Mk) = k, para todo
k ≥ 2 (veja Exerc´ıcio 6.5).
46
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
u1
u2
u3
u4 u5
w
v1
v2
v3
v4 v5
Figura 6.1: Grafo de Gro¨tzsch.
6.3.2 Teorema de Brooks
O seguinte teorema fornece um limite superior mais justo do que aquele na
Proposic¸a˜o 6.4:
Teorema 6.5. (Brooks, 1941) Se G e´ conexo e na˜o e´ completo nem um
ciclo ı´mpar enta˜o χ(G) ≤ ∆(G).
6.4 Exerc´ıcios
6.1. Suponha que quaisquer dois ciclos ı´mpares de um grafo G possuem pelo
menos um ve´rtice em comum. Mostre que χ(G) ≤ 5.
6.2. Prove: se toda aresta de G ocorre no ma´ximo em um ciclo, enta˜o
χ(G) ≤ 3.
6.3. Prove ou refute: Se |E(G)| > 1 e y e´ uma ponte de G enta˜o χ(G) =
χ(G− y).
47
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
6.4. Mostre que existe uma ordenac¸a˜o dos ve´rtices de G tal que o me´todo
guloso de colorac¸a˜o aplicado a esta ordenac¸a˜o usa χ(G) cores.
6.5. SejamM2,M3,M4, . . . os grafos da construc¸a˜o de Mycielski, ondeM2 =
K2. Mostre que:
(a) Todo Mk e´ k-cr´ıtico.
(b) Todo Mk e´ livre de triaˆngulos.
6.6. Um grafo G e´ unicamente k-color´ıvel se quaisquer duas k-colorac¸o˜es
de G induzem a mesma partic¸a˜o de V (isto e´, coincidem a menos de
uma permutac¸a˜o de cores). Mostre que nenhum corte de ve´rtices de
um grafo k-cr´ıtico induz um subgrafo unicamente (k − 1)-color´ıvel.
48
7 Colorac¸a˜o de Arestas
7.1 Grafos k-color´ıveis em arestas
Uma k-colorac¸a˜o de arestas de um grafo G e´ uma atribuic¸a˜o de k cores
1, 2, . . . , k a`s suas arestas. Esta colorac¸a˜o sera´ pro´pria se arestas adjacentes
tiverem cores diferentes; neste caso, cada conjunto de arestas de mesma cor
e´ um emparelhamento.
Um grafo e´ k-color´ıvel em arestas se admitir uma k-colorac¸a˜o pro´pria de
arestas. Obviamente, todo grafo e´ m-color´ıvel em arestas, onde m = |E(G)|.
Ale´m disso, se G e´ k-color´ıvel em arestas, enta˜o G e´ r-color´ıvel em arestas
para todo r ≥ k.
O ı´ndice croma´tico χ′(G) de um grafo G e´ o menor k para o qual G e´
k-color´ıvel. Obviamente, χ′(G) ≥ ∆(G).
Exemplo 7.1. O ı´ndice croma´tico do grafo de Petersen e´ 4. Para provar
este fato, e´ necessa´rio mostrar que: (a) o grafo de Petersen e´ 4-color´ıvel em
arestas; (b) o grafo de Petersen na˜o e´ 3-color´ıvel em arestas. A demonstrac¸a˜o
de (a) e (b) fica como exerc´ıcio para o leitor.
7.2 Teorema de Vizing
Dada uma colorac¸a˜o de arestas de um grafo, dizemos que uma certa cor j
esta´ representada no ve´rtice v quando alguma aresta incidente a v possui a
cor j.
Lema 7.1. Seja G um grafo conexo que na˜o e´ um ciclo ı´mpar. Enta˜o existe
uma 2-colorac¸a˜o de arestas de G tal que, em todo ve´rtice de grau maior que
um, as duas cores esta˜o representadas.
Denotemos por c(v) o nu´mero de cores representadas no ve´rtice v em
uma k-colorac¸a˜o de arestas C de um grafo G. Observe que C e´ pro´pria se e
somente se c(v) = d(v).
Uma k-colorac¸a˜o C ′ e´ uma melhoria de uma k-colorac¸a˜o C se a soma
dos valores c′(v) e´ estritamente maior que a soma dos valores c(v). Uma
k-colorac¸a˜o e´ plena quando na˜o admite melhoria.
Prof. Fa´bio Protti Notas de Aula de Teoria dos Grafos - IC/UFF
Para o lema a seguir, utilizamos a seguinte notac¸a˜o: dada uma colorac¸a˜o
de arestas de um grafo, Ej e´ o conjunto de arestas com a cor j.
Lema 7.2. Seja G um grafo com uma k-colorac¸a˜o plena tal que existe um
ve´rtice u onde uma certa cor 0 na˜o esta´ representada em u e uma certa cor 1
esta´ representada pelo menos duas vezes em u. Enta˜o, a componente conexa
H de G[E0 ∪ E1] que conte´m u e´ um ciclo ı´mpar.
Teorema 7.3. Se G e´ bipartido enta˜o χ′(G) = ∆(G).
Teorema 7.4. (Vizing - 1964, Gupta - 1966, Fournier - 1973)
Para qualquer grafo G, χ′(G) ≤ ∆(G) + 1.
Pelo teorema acima, conclu´ımos que o ı´ndice croma´tico de um grafo G
vale ∆(G) ou ∆(G) + 1. Grafos que teˆm ı´ndice croma´tico ∆ sa˜o chamados
grafos Classe 1, enquanto que os demais sa˜o grafos Classe 2. O grafo de
Petersen, por exemplo, e´ um grafo Classe 2. O problema de decidir se um
dado grafo e´ Classe 1 ou Classe 2 e´ NP-dif´ıcil.
7.3 Exerc´ıcios
7.1. Pinte as arestas de Km,n com ∆ cores.
7.2. Prove que se um grafo G tem 2k+1 ve´rtices e mais do que k.∆ arestas,
enta˜o χ′(G) = ∆ + 1.
7.3. Seja G um grafo cu´bico hamiltoniano. Mostre que χ′(G) = 3.
7.4. Mostre que se G e´ um grafo na˜o vazio, regular e tal que |V (G)| e´ ı´mpar
enta˜o χ′(G) = ∆ + 1.
7.5. Descrever um me´todo algor´ıtmico para colorir as arestas de um grafo
bipartido com ∆ cores.
50
8 Planaridade
8.1 Definic¸a˜o de grafo planar
Um grafo G e´ planar se existe uma representac¸a˜o (ou desenho, ou imersa˜o)
de G no plano de modo que as arestas se encontrem somente nos ve´rtices,
isto e´, de modo que as arestas na˜o se cruzem. Uma tal representac¸a˜o de G e´
dita plana ou planar.
Uma representac¸a˜o planar divide o plano em regio˜es chamadas faces.
Existe sempre uma u´nica face que na˜o esta´ limitada (isto e´, tem a´rea in-
finita); tal face e´ chamada externa ou infinita.
Qualquer representac¸a˜o planar de G possui sempre o mesmo nu´mero de
faces; portanto, o nu´mero de faces de um grafo planar e´ uma invariante do
mesmo.
Note que se G e´ planar enta˜o todo subgrafo de G tambe´m e´ planar. Ale´m
disso, G e´ planar se e somente se todas as suas componentes conexas sa˜o
planares.
8.2 Fo´rmula de Euler