Exercícios de

Teoria dos Grafos

[Link]

Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística
Universidade de São Paulo

fevereiro de 2013
FEOFILOFF 2
Sumário

1 Conceitos básicos 7
1.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Grafos bipartidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Vizinhanças e graus de vértices . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Caminhos e circuitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5 União e interseção de grafos . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6 Grafos planares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7 Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.8 Cortes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.9 Caminhos e circuitos em grafos . . . . . . . . . . . . . . . . . . . . . . . 32
1.10 Grafos conexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.11 Componentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.12 Pontes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.13 Grafos aresta-biconexos . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.14 Articulações e grafos biconexos . . . . . . . . . . . . . . . . . . . . . . . 45
1.15 Florestas e árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.16 Menores de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.17 Mapas planos e suas faces . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.18 Grafos aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2 Isomorfismo 61

3 Síntese de grafos com graus dados 67

4 Grafos bicoloráveis 69

5 Conjuntos estáveis 73

6 Cliques 79

7 Cobertura por vértices 83

3
FEOFILOFF 4

8 Coloração de vértices 85

9 Emparelhamentos 97

10 Emparelhamentos em grafos bipartidos 103

11 Emparelhamentos em grafos arbitrários 109

12 Coloração de arestas 113

13 Conectores e conjuntos acíclicos 119

14 Caminhos e circuitos mínimos 123

15 Fluxo 127

16 Fluxo internamente disjunto 131

17 Circuitos e caminhos hamiltonianos 135

18 Coberturas por circuitos 141

19 Caracterização da planaridade 147

A Algumas dicas 151

B O alfabeto grego 157

Bibliografia 159

Índice Remissivo 161

Prefácio

A teoria dos grafos estuda objetos combinatórios — os grafos — que são um

bom modelo para muitos problemas de matemática, de computação, e de
engenharia. A teoria dos grafos não é propriamente uma teoria mas uma
coleção de problemas. Muitos desses problemas são um interessante desafio
intelectual e têm importantes aplicações práticas.
O presente texto é uma coleção de exercícios de teoria dos grafos. A mai-
oria dos exercícios foi extraída dos livros de Bondy e Murty [BM08, BM76],
Wilson [Wil79], Diestel [Die00, Die05], Bollobás [Bol98], Lovász [Lov93], Mel-
nikov et alii [MST+ 98], Lucchesi [Luc79] e Lovász e Plummer [LP86]. Alguns
outros são subproduto de projetos de pesquisa. Autros ainda nasceram de
conversas com professores (especialmente meu orientador Dan Younger),
colegas e alunos.
O texto tem muitos links que levam de uma parte do texto a outra e
apontam para material complementar. Para tirar proveito desses links é
preciso ler o texto na tela do seu computador (e não impresso em papel).
O sítio [Link]/~pf/grafos-exercicios/ tem informações adicionais,
além de uma versão atualizada do texto.

Organização. O capítulo 1 trata de conceitos básicos. Cada um dos outros

capítulos aborda um problema clássico. Muitos desses problemas têm caráter
computacional: procura-se um algoritmo eficiente que receba um grafo e
extraia dele uma certa informação. Alguns dos problemas são fáceis, outros
são difíceis; alguns já foram resolvidos, outros não.1
Em que ordem os capítulos devem ser examinados? Depois de estudar a
primeira seção do capítulo 1, sugiro que o leitor avance imediatamente para o
capítulo 2 e os seguintes, voltando ao capítulo 1 somente quando isso se fizer
necessário. Há um bom índice remissivo que ajuda a localizar as definições
dos vários conceitos.
1
Para vários desses problemas não se conhece (ainda?) um algoritmo rápido, ou seja,
não se conhece um algoritmo substancialmente melhor que examinar, pacientemente, uma
enorme lista de candidatos a solução. Em termos técnicos, um problema desse tipo é NP-
completo ou NP-difícil. Veja os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97].

5
FEOFILOFF 6

Classificação dos exercícios. A maioria dos exercícios tem um prefixo ge-

nérico E. Alguns têm prefixos mais específicos:

◦E ... particularmente fácil ou rotineiro

!E ... difícil
!! E ... muito difícil
?E ... importante
?! E ... importante e difícil
?◦ E ... importante mas fácil
.E ... útil como ferramenta técnica
E♥ ... particularmente bom
D ... desafio, problema em aberto

Mas esta classificação não é muito confiável e não foi feita de maneira muito
sistemática.

Terminologia técnica em inglês. Boa parte da literatura da teoria dos gra-

fos está escrita em inglês. Por isso, a definição de cada termo técnico em
português é acompanhada, entre parênteses, do correspondente termo em
inglês. O termo em inglês também é listado no índice remissivo.
O idioma inglês determinou a escolha de muitos símbolos. Assim, por
exemplo, o conjunto das arestas (= edges) de um grafo é denotado por “E” e
não por “A”, como seria mais natural em português.

Agradecimentos. Agradeço a Rogério Brito por resolver várias dificulda-

des tipográficas.

IME–USP, São Paulo, julho de 2012

P. F.
Capítulo 1

Conceitos básicos

Este capítulo formaliza a noção de grafo e introduz alguns conceitos básicos,

como grau de vértice, corte, subgrafo, conexão, componente, ponte, arti-
culação, união, interseção, complemento, menor, etc. O capítulo também
introduz alguns tipos importantes de grafos, como
caminhos,
circuitos,
árvores,
grafos bipartidos,
grafos aresta-biconexos,
grafos biconexos,
grafos planares,
grafos de intervalos,
grafos aleatórios, etc.
Vários exemplos de grafos encontrados na natureza também são apresenta-
dos. É o caso
das grades,
dos cubos,
do grafo de Petersen,
dos grafos de diversas peças do jogo de xadrez,
dos grafos de compostos químicos, etc.
Estes exemplos serão úteis nos demais capítulos do texto.
Sugiro que o leitor estude a primeira seção deste capítulo e logo avance
para os capítulos seguintes (a começar pelo capítulo 2, que trata de isomor-
fismo). Quando necessário, o leitor poderá voltar a este capítulo 1 para
aprender novos conceitos e rever definições. O índice remissivo pode ser
muito útil nesse processo.

7
 FEOFILOFF Grafos 8

1.1 Grafos
Um grafo (= graph)1 é uma estrutura formada por dois tipos de objetos:
vértices (= vertices) e arestas (= edges). Cada aresta é um par não ordenado
de vértices, ou seja, um conjunto com exatamente dois vértices.2 Uma aresta
vw como {v, w} será denota simplesmente por vw ou wv; diremos que a aresta
incide em v e em w; diremos também que v e w são as pontas da aresta;
diremos, ainda, que os vértices v e w são vizinhos (= neighbors), ou adjacentes
(= adjacent).

E XEMPLO : os vértices do grafo são t, u, v, w, x, y, z e as arestas

são vw, uv, xw, xu, xy e yz. A figura abaixo é uma representação
gráfica desse grafo.
u
t
x
v y z
w

De acordo com nossa definição, um grafo não pode ter duas arestas dife-
rentes com o mesmo par de pontas (ou seja, não pode ter arestas “paralelas”).
Além disso, as duas pontas de qualquer aresta são diferentes (ou seja, não há
“laços”). Alguns livros gostam de enfatizar esse aspecto da definição dizendo
simples que o grafo é “simples”; nós não usaremos este adjetivo.
Um grafo com conjunto de vértices V e conjunto de arestas E é denotado
(V, E) por (V, E). Muitas vezes é conveniente dar um nome ao grafo como um todo.
VG , EG Se o nome do grafo é G, o conjunto dos seus vértices é denotado por VG e o
n(G) conjunto das suas arestas por EG . O número de vértices de G é denotado por
m(G)
n(G) e o número de arestas por m(G); portanto,

n(G) := |VG | e m(G) := |EG | .

V (2) O complemento de um grafo (V, E) é o grafo (V, V (2) r E), onde V (2)
é o conjunto de todos os pares não ordenados3 de elementos de V . O
G complemento de G é usualmente denotado por G.
(2)
Kn Um grafo G é completo se EG = VG . A expressão “G é um Kn ” é uma
abreviatura de “G é um grafo completo com n vértices”. Um grafo G é vazio
Kn se EG = ∅. A expressão “G é um Kn ” é uma abreviatura de “G é um grafo
vazio com n vértices”.
1
O termo foi usado pela primeira vez (no sentido que nos interessa aqui) por James
Joseph Sylvester ( − ). (Veja verbete na Wikipedia.)
2
Suporemos sempre que os conjuntos de vértices e de arestas de qualquer grafo são
finitos e mutuamente disjuntos. Suporemos também que o
conjunto de vértices não é vazio.
3
Diestel [Die05] escreve “[V ]2 ”. Há quem escreva “ V2 ”.
FEOFILOFF Grafos 9

Exercícios
E 1.1 Faça uma lista de todos os grafos que tenham {a, b, c} por conjunto
de vértices.4 Faça a lista de modo que cada grafo apareça ao lado do seu
complemento.

E 1.2 Faça uma figura de um K5 e outra de um K5 . Quantas arestas tem

um Kn ? E um Kn ?

E 1.3 A matriz de adjacências de um grafo G é a matriz A definida da

seguinte maneira: para quaisquer dois vértices u e v, matriz de
adjacências
1 se uv ∈ EG ,
A[u, v] =
0 em caso contrário.

É claro que a matriz é indexada por VG × VG . (A matriz de adjacência é uma

espécie de “figura” do grafo. Ela tem certas vantagens sobre a figura pontos-
e-linhas que usamos acima.)
Escreva a matriz de adjacências do grafo definido no exemplo que apa-
rece na página 8. Escreva a matriz de adjacências de um K4 . Qual a relação
entre a matriz de adjacências de um grafo e matriz de adjacências do seu
complemento?

E 1.4 A matriz de incidências de um grafo G é a matriz M definida da

seguinte maneira: para todo vértice u e toda aresta e, matriz de
incidências
1 se u é uma das pontas de e ,
M [u, e] =
0 em caso contrário.

É claro que a matriz é indexada por VG × EG . (A matriz de incidência é uma

espécie de “figura” do grafo. Ela tem certas vantagens sobre a figura pontos-
e-linhas que usamos acima.)
Escreva a matriz de incidências do grafo definido no exemplo que apa-
rece na página 8. Escreva a matriz de incidências de um K4 . Quanto vale a
soma de todos os elementos da matriz de incidências de um grafo? Qual a
relação entre a matriz de incidências de um grafo e matriz de incidências do
seu complemento?

E 1.5 Os hidrocarbonetos conhecidos como alcanos têm fórmula química alcanos

Cp H2p+2 , onde C e H representam moléculas de carbono e hidrogênio res-
pectivamente. As moléculas de alcanos podem ser representadas por grafos
como os da figura 1.1.
4
Num conjunto, a ordem em que os elementos são apresentados é irrelevante. Assim,
{a, b, c} = {b, c, a} = {c, b, a}.
 FEOFILOFF Grafos 10

Faça uma figura de uma molécula de metano C1 H4 . Quantas moléculas

“diferentes” de C3 H8 existem?

Figura 1.1: Etano (C2 H6 ), butano (C4 H10 ) e isobutano (C4 H10 ). Os vérti-
ces em que incide uma só aresta representam átomos de hidrogênio (H);
os demais representam átomos de carbono (C). (Veja o exercício 1.5.)

E 1.6 Seja V o produto cartesiano {1, 2, . . . , p}×{1, 2, . . . , q}, isto é, o conjunto

de todos os pares ordenados5 (i, j) com i em {1, . . . , p} e j em {1, . . . , q}.
Digamos que dois elementos (i, j) e (i0 , j 0 ) de V são adjacentes se

i = i0 e |j − j 0 | = 1 ou j = j 0 e |i − i0 | = 1 .

Essa relação de adjacência define um grafo sobre o conjunto V de vértices.

grade Esse grafo é conhecido como grade (= grid) p-por-q.
Quantas arestas tem a grade p-por-q? Escreva as matrizes de adjacência
e incidência de uma grade 4-por-5.

Figura 1.2: Uma grade 3-por-4 (veja exercício 1.6).

E 1.7 Dados números inteiros p e q, seja V o conjunto {1, 2, 3, . . . , pq−2, pq−1,

pq}. Digamos que dois elementos k e k 0 de V , com k < k 0 , são adjacentes se
k 0 = k + q ou6
k mod q 6= 0 e k 0 = k + 1.
Essa relação de adjacência define um grafo com conjunto de vértices V .
Faça uma figura do grafo com parâmetros p = 3 e q = 4. Faça uma figura
do grafo com parâmetros p = 4 e q = 3. Qual a relação entre esses grafos e a
grade definida no exercício 1.6?

dama E 1.8 O grafo dos movimentos da dama, ou simplesmente grafo da dama, é

5
Um par ordenado é uma sequência de comprimento 2. Numa sequência, a ordem dos
elementos é essencial. Assim, (1, 2) 6= (2, 1) e (1, 2, 1) 6= (1, 1, 2).
6
A expressão “k mod q” denota o resto da divisão de k por q, ou seja, k/q − bk/qc.
FEOFILOFF Grafos 11

definido assim: os vértices do grafo são as casas de um tabuleiro de xadrez

com t linhas e t colunas (no tabuleiro usual temos t = 8) e dois vértices são
adjacentes se uma dama (= queen) do jogo de xadrez pode saltar de um deles
para o outro em um só movimento. Para deixar claro o número de linhas e
colunas do tabuleiro, podemos dizer que esse é o grafo da dama t-por-t. (Veja
figura 1.3.)
Faça uma figura do grafo da dama 4-por-4. Escreva as matrizes de
adjacência e incidência do grafo da dama 4-por-4. Quantas arestas tem o
grafo da dama 8-por-8? Quantas arestas tem o grafo da dama t-por-t?

E 1.9 O grafo do cavalo t-por-t é definido assim: os vértices do grafo são as cavalo
casas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices são
adjacentes se um cavalo (= knight) do jogo de xadrez pode saltar de um deles
para o outro em um só movimento. (Veja figura 1.3.)
Faça uma figura do grafo do cavalo 3-por-3. Escreva as matrizes de
adjacência e incidência do grafo do cavalo 3-por-3. Quantas arestas tem o
grafo do cavalo 8-por-8? Quantas arestas tem o grafo do cavalo t-por-t?

Figura 1.3: Tabuleiros de xadrez 8-por-8. A figura esquerda indica todos

os vizinhos do vértice • no grafo da dama (veja exercício 1.8). A da direita
indica todos os vizinhos do vértice • no grafo do cavalo (veja exercício 1.9).

E 1.10 O grafo do bispo t-por-t é definido assim: os vértices do grafo são as bispo
casas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices são
adjacentes se um bispo (= bishop) do jogo de xadrez pode saltar de um deles
para o outro em um só movimento.
Faça uma figura do grafo do bispo 4-por-4. Escreva as matrizes de
adjacência e incidência do grafo do bispo 4-por-4. Quantas arestas tem o
grafo do bispo 8-por-8? Quantas arestas tem o grafo do bispo t-por-t?

E 1.11 O grafo da torre t-por-t é definido assim: os vértices do grafo são as torre
casas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices são
adjacentes se um torre (= rook) do jogo de xadrez pode saltar de um deles
para o outro em um só movimento.
Faça uma figura do grafo da torre 4-por-4. Escreva as matrizes de adja-
cência e incidência do grafo da torre 4-por-4. Quantas arestas tem o grafo da
torre 8-por-8? Quantas arestas tem o grafo da torre t-por-t?
 FEOFILOFF Grafos 12

rei E 1.12 O grafo do rei t-por-t é definido assim: os vértices do grafo são as
casas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices são
adjacentes se um rei (= king) do jogo de xadrez pode saltar de um deles para
o outro em um só movimento.
Faça uma figura do grafo do rei 4-por-4. Escreva as matrizes de adjacên-
cia e incidência do grafo do rei 4-por-4. Quantas arestas tem o grafo do rei
8-por-8? Quantas arestas tem o grafo do rei t-por-t?

palavras E 1.13 O grafo das palavras é definido assim: cada vértices é uma palavra da
língua portuguesa e duas palavras são adjacentes se diferem em exatamente
uma posição. (Esse grafo é uma adaptação do ladders do Stanford Graph-
Base [Knu93].) Por exemplo, rato e ralo são adjacentes, enquanto ralo e
rota não são. Faça uma figura da parte do grafo definida pelas palavras
abaixo:
caiado cavado cavalo girafa girava ralo ramo rata rato
remo reta reto rota vaiado varado virada virado virava
Escreva as matrizes de adjacência e incidência do grafo.

cubo E 1.14 Para qualquer inteiro positivo k, um cubo de dimensão k (ou k-cubo)
é o grafo definido da seguinte maneira: os vértices do grafo são todas as
sequências7 b1 b2 · · · bk de bits8 ; dois vértices são adjacentes se e somente se
diferem em exatamente uma posição. Por exemplo, os vértices do cubo de
dimensão 3 são 000, 001, 010, 011, 100, 101, 110, 111; o vértice 000 é adjacente
aos vértices 001, 010, 100 e a nenhum outro; e assim por diante. O cubo de
Qk dimensão k será denotado por Qk .
Faça figuras dos cubos Q1 , Q2 e Q3 . Escreva as matrizes de adjacência e
incidência de Q3 . Quantos vértices tem Qk ? Quantas arestas tem Qk ?

E 1.15 Seja X o conjunto {1, 2, 3, 4, 5} e V o conjunto X (2) (portanto, V é o

conjunto de todos os subconjuntos de X que têm exatamente 2 elementos).
Digamos que dois elementos v e w de V são adjacentes se v ∩ w = ∅. Essa
Petersen relação de adjacência sobre V define o grafo de Petersen.9 Faça uma figura
do grafo. Escreva as matrizes de adjacência e incidência do grafo. Quantos
vértices e quantas arestas tem o grafo?

E 1.16 Seja V o conjunto de todos os subconjuntos de {1, 2, . . . , n} que têm

exatamente k elementos, sendo k ≤ n/2. Digamos que dois elementos v e w
de V são adjacentes se v ∩ w = ∅. Essa relação de adjacência sobre V define o
Kneser grafo de Kneser K(n, k).10 Em particular, K(5, 2) é o grafo de Petersen. Faça

7
A expressão “b1 b2 · · · bk ” é uma abreviatura de “(b1 , b2 , . . . , bk )”.
8
Portanto, cada bi pertence ao conjunto {0, 1}.
9
Referência ao dinamarquês Julius Petersen ( − ). (Veja verbete na Wikipedia.)
FEOFILOFF Grafos 13

figuras de K(n, 1), K(n, n), K(n, n−1), K(4, 2), K(5, 3), K(6, 2) e K(6, 3).

E 1.17 O grafo dos estados do Brasil é definido assim: cada vértice é um dos estados
estados da República Federativa do Brasil; dois estados são adjacentes se têm
uma fronteira comum. Faça um desenho do grafo. Quantos vértices tem o
grafo? Quantas arestas?

E 1.18 Considere as grandes cidades e as grandes estradas do estado de

São Paulo. Digamos que uma cidade é grande se tem pelo menos 300 mil
habitantes. Digamos que uma estrada é grande se tiver pista dupla (como a
SP300, por exemplo). Digamos que duas grandes cidades são adjacentes se
uma grande estrada ou uma concatenação de grandes estradas liga as duas
cidades diretamente (ou seja, sem passar por uma terceira grande cidade). cidades
Faça uma figura do grafo das grandes cidades definido pela relação de
adjacência que acabamos de descrever.

E 1.19 Seja V um conjunto de pontos no plano. Digamos que dois desses

pontos são adjacentes se a distância entre eles é menor que 2. Essa relação
de adjacência define o grafo dos pontos no plano (sobre o conjunto V ). Faça pontos
uma figura do grafo definido pelos pontos abaixo. no plano

(0, 2) (1, 2) (2, 2)

(0, 1) (1, 1) (2, 1)
(0, 0) (1, 0) (2, 0)

Escreva as matrizes de adjacência e incidência do grafo.

E 1.20 Dado um conjunto V , seja E o conjunto definido da seguinte maneira:

para cada par não ordenado de elementos de V , jogue uma moeda; se o
resultado for cara, acrescente o par a E. O grafo (V, E) assim definido é
aleatório (= random). aleatório
Pegue sua moeda favorita e faça uma figura do grafo aleatório com
vértices 1, . . . , 6. Agora repita o exercício com uma moeda viciada que dá
cara com probabilidade 1/3 e coroa com probabilidade 2/3.

E 1.21 Seja S uma matriz quadrada de números inteiros. Suponha que as

linhas de S são indexadas por um conjunto V e que as colunas são indexadas
pelo mesmo conjunto V . O grafo da matriz S é definido da seguinte maneira: matriz
o conjunto de vértices do grafo é V e dois vértices i e j são adjacentes se
S[i, j] 6= 0.
O grafo de S está bem definido? Que condições é preciso impor sobre a
matriz para que o grafo esteja bem definido?
10
Lásló Lovász usou esse grafo em 1978 para provar uma conjectura proposta por M. Kne-
ser em 1955.
 FEOFILOFF Grafos 14

E 1.22 Suponha dados k intervalos de comprimento finito, digamos I1 , I2 ,

. . . , Ik , na reta real. Digamos que dois intervalos Ii e Ij são adjacentes se
Ii ∩ Ij 6= ∅. Essa relação de adjacência define um grafo com conjunto de
intervalos vértices {I1 , I2 , . . . , Ik }. Esse é um grafo de intervalos.
Faça uma figura do grafo definido pelos intervalos [0, 2], [1, 4], [3, 6], [5, 6]
e [1, 6]. Escreva as matrizes de adjacência e incidência do grafo.

E 1.23 Seja  uma relação de ordem parcial sobre um conjunto finito V .

Portanto, a relação é transitiva (se x  y e y  z então x  z), antissimétrica
(se x  y e y  x então x = y) e reflexiva (x  x para todo x). Digamos
que dois elementos distintos x e y de V são adjacentes se forem comparáveis,
ou seja, se x  y ou y  x. Essa relação de adjacência define o grafo de
compara- comparabilidade da relação .
bilidade Faça uma figura do grafo de comparabilidade da relação usual de inclu-
são ⊆ entre os subconjuntos de {1, 2, 3}.

E 1.24 Duas arestas de um grafo G são adjacentes se têm uma ponta comum.
Essa relação de adjacência define o grafo das arestas de G. De modo mais
das arestas formal, o grafo das arestas (= line graph) de um grafo G é o grafo (EG , A) em
que A é o conjunto de todos os pares de arestas adjacentes de G. (Há quem
diga [Per09] grafo lineal no lugar de grafo das arestas.) O grafo das arestas de
L(G) G será denotado por L(G). (Veja a figura 1.4.)
Faça uma figura de L(K3 ). Faça uma figura de L(K4 ). Escreva as
matrizes de adjacência e incidência de L(K4 ). Quantos vértices e quantas
arestas tem L(Kn )? Faça uma figura do grafo L(P ), sendo P o grafo de
Petersen (veja exercício 1.15).

u
t vu ux
x xy
v y z yz
w vw wx

Figura 1.4: Um grafo (esquerda) e o seu grafo das arestas (direita).

FEOFILOFF Grafos bipartidos 15

1.2 Grafos bipartidos

Um grafo G é bipartido (= bipartite) se existe uma bipartição11 {U, W } de VG
tal que toda aresta de G tem uma ponta em U e outra em W . Para explicitar
a partição, podemos dizer que o grafo é {U, W }-bipartido.
Se G é um grafo {U, W }-bipartido, podemos dizer, informalmente, que
os elementos de U são os vértices brancos e os de W são os vértices pretos
do grafo.
Um grafo {U, W }-bipartido é completo se todo vértice branco é adjacente
a todos os vértices pretos. Um Kp,q é um grafo bipartido completo com p Kp,q
vértices breancos e q pretos.
Todo K1,q é uma estrela (= star). Se q ≥ 2, o centro da estrela é o único estrela
vértice que incide em duas ou mais arestas. (Se q < 2, a estrela não tem
centro.)

Figura 1.5: Um grafo bipartido completo.

Exercícios
◦ E 1.25 Uma pequena fábrica tem cinco máquinas — 1, 2, 3, 4 e 5 — e seis
operários — A, B, C, D, E e F . A tabela especifica as máquinas que cada
operário sabe operar:

A 2, 3 B 1, 2, 3, 4, 5
C 3 D
E 2, 4, 5 F 2, 5

Faça uma figura do grafo bipartido que representa a relação entre operários
e máquinas.

◦ E 1.26 Quantas arestas pode ter um grafo {U, W }-bipartido?

11
Uma bipartição de um conjunto V é um par {U, W } de conjuntos não vazios tal que
U ∪ W = V e U ∩ W = ∅. De modo mais geral, uma partição de um conjunto V é uma
coleção {X1 , X2 , . . . , Xk } de conjuntos não vazios, disjuntos dois a dois (ou seja, Xi ∩ Xj = ∅
para cada i 6= j), cuja união é V (ou seja, X1 ∪ X2 ∪ · · · ∪ Xk = V ). Não faz sentido dizer
“X1 é uma das partições de V ”; isso equivale a confundir boi com boiada ou terno com
paletó. Diga “X1 é um dos elementos da partição” ou “X1 é uma das partes da partição”.
FEOFILOFF Grafos bipartidos 16

◦ E 1.27 Quantas arestas tem um Kp,q ? Quantas arestas tem um Kp,q ?

E 1.28 Faça uma figura de um K3,4 . Escreva as matrizes de adjacência e

incidência de um K3,4 . Faça uma figura de uma estrela com 6 vértices.

E 1.29 É verdade que o grafo do cavalo no tabuleiro t-por-t é bipartido?

E 1.30 Que aparência tem a matriz de adjacências de um grafo bipartido?

E 1.31 A matriz da bipartição de um grafo {U, W }-bipartido é definida as-

sim: cada linha da matriz é um elemento de U , cada coluna da matriz é um
elemento de W e no cruzamento da linha u com a coluna w temos um 1 se uw
é uma aresta e temos um 0 em caso contrário.
Escreva a matriz da bipartição do grafo do exercício 1.25. Adote a
bipartição óbvia: U = {A, . . . , F } e W = {1, . . . , 5}.
FEOFILOFF Vizinhanças e graus de vértices 17

1.3 Vizinhanças e graus de vértices

A vizinhança (= neighborhood) de um vértice v em um grafo G é o conjunto
de todos os vizinhos de v. Este conjunto será denotado por

NG (v)

ou simplesmente por N(v).12 O grau (= degree) de um vértice v em um grafo N(v)

G é o número de arestas que incidem em v. O grau de v será denotado por

dG (v)

ou simplesmente por d(v). É evidente que d(v) = |N(v)| para todo vértice v. d(v)
Um vértice v é isolado se d(v) = 0.
O grau mínimo e o grau máximo dos vértices de um grafo13 G são os
números δ(G)
δ(G) := min dG (v) e ∆(G) := max dG (v) ∆(G)
v∈VG v∈VG
1
P
respectivamente. A média dos graus de G, ou seja, |V | v∈V d(v), será deno-
tada por µ(G).14 Como veremos no exercício 1.43, µ(G)

µ(G) = 2m(G)/n(G) .

Um grafo é regular se todos os seus vértices têm o mesmo grau, ou seja, se

δ = ∆. Um grafo é r-regular se d(v) = r para todo vértice v. Um grafo cúbico
é o mesmo que um grafo 3-regular.

Exercícios
◦ E 1.32 Quais são os graus dos vértices de uma estrela (veja a seção 1.2)?

◦ E 1.33 Se G é um Kn , quanto valem δ(G) e ∆(G)? Quanto valem os parâ-

metros δ e ∆ de um Kp,q (veja a seção 1.2)?

◦ E 1.34 Para r = 1, 2, 3, faça uma figura de um grafo r-regular com 12

vértices.

E 1.35 Quais são os graus dos vértices de uma molécula de alcano (veja
exercício 1.5)?
12
Alguns autores escrevem “Adj (v)” em lugar de “N(v)”. Outros escrevem “Γ(v)”.
13
A expressão “grau mínimo de um grafo” não é muito gramatical, uma vez que “grau
de um grafo” não faz sentido.
14
Ao contrário de δ e ∆, a notação µ não é uma unanimidade. Diestel [Die05] e Bondy e
Murty [BM08], por exemplo, escrevem d no lugar do meu µ.
FEOFILOFF Vizinhanças e graus de vértices 18

E 1.36 Calcule os valores dos parâmetros δ, ∆ e µ no k-cubo (veja exercí-

cio 1.14) e no grafo de Petersen (veja exercício 1.15 ou figura 1.6).

Figura 1.6: Grafo de Petersen. Veja exercícios 1.15 e 1.36.

E 1.37 Calcule os valores dos parâmetros δ e ∆ no grafo dos estados do Brasil

(veja exercício 1.17).

E 1.38 Calcule os valores dos parâmetros δ, ∆ e µ no grafo da dama (veja

exercício 1.8) e no grafo do cavalo (veja exercício 1.9).

E 1.39 Seja A a matriz de adjacências (veja exercício 1.3) e M a matriz de

incidências (veja exercício 1.4) de um grafo G. Quanto vale a soma dos
elementos da linha v de A? Quanto vale a soma dos elementos da linha v
de M ?

. E 1.40 Seja G um grafo {U, W }-bipartido. Suponha que G é r-regular, com

r > 0. Mostre que |U | = |W |.

E 1.41 É verdade que todo grafo com pelo menos dois vértices tem dois
vértices com o mesmo número de vizinhos? Em outras palavras, se um grafo
tem mais de um vértice, é verdade que tem dois vértices distintos v e w tais
que |N(v)| = |N(w)|? (Uma maneira informal de dizer isso: é verdade que em
toda cidade com pelo menos dois habitantes residem duas pessoas que têm
exatamente o mesmo número de amigos na cidade?)

? E 1.42 Mostre15 que, em todo grafo, a soma dos graus dos vértices é igual
ao dobro do número de arestas. Ou seja, todo grafo (V, E) satisfaz a identi-
dade P
v∈V d(v) = 2|E| . (1.1)

◦ E 1.43 Mostre que a µ(G) = 2m(G)/n(G) para todo grafo G.

15
Mostre = prove.
FEOFILOFF Vizinhanças e graus de vértices 19

◦ E 1.44 Mostre que todo grafo G tem um vértice v tal que d(v) ≤
2m(G)/n(G) e um vértice w tal que d(w) ≥ 2m(G)/n(G). É verdade
que todo grafo G tem um vértice x tal que d(x) < 2m(G)/n(G)?

E 1.45 Mostre que em qualquer grafo tem-se δ ≤ 2m/n ≤ ∆.

E 1.46 Mostre que todo grafo com n vértices tem no máximo n(n − 1)/2
arestas.

. E 1.47 Mostre que em qualquer grafo o número de vértices de grau ímpar

é necessariamente par.

E 1.48 Quantas arestas tem o grafo da dama 8-por-8 (veja exercício 1.8)?
Quantas arestas tem o grafo da dama t-por-t?

E 1.49 Quantas arestas tem o grafo do cavalo 4-por-4 (veja exercício 1.9)?
Quantas arestas tem o grafo do cavalo t-por-t?

E 1.50 Quantas arestas tem um grafo r-regular com n vértices?

E 1.51 Quantas arestas tem o cubo de dimensão k?

E 1.52 Quantas arestas tem o grafo das arestas (veja exercício 1.24) de um
grafo G?

E 1.53 Seja G o complemento de um grafo G. Calcule δ(G) e ∆(G) em função

de δ(G) e ∆(G).

E 1.54 Seja G um grafo tal que m(G) > n(G). Mostre que ∆(G) ≥ 3.

E 1.55 Suponha que um grafo G tem menos arestas que vértices, ou seja, que
m(G) < n(G). Mostre que G tem (pelo menos) um vértice de grau 0 ou (pelo
menos) dois vértices de grau 1.

! E 1.56 Escolha dois números naturais n e k e considere o seguinte jogo para

dois jogadores, A e B. Cada iteração do jogo começa com um grafo G que
tem n vértices. No início da primeira iteração tem-se EG = ∅. Em cada
iteração ímpar (primeira, terceira, etc.), o jogador A escolhe dois vértices não
adjacentes u e v e acrescenta uv ao conjunto de arestas do grafo. Em cada
iteração par (segunda, quarta, etc.), o jogador B faz um movimento análogo:
escolhe dois vértices não adjacentes u e v e acrescenta uv ao conjunto de
arestas do grafo. O primeiro jogador a produzir um grafo G tal que δ(G) ≥ k
FEOFILOFF Vizinhanças e graus de vértices 20

perde o jogo. Problema: determinar uma estratégia vencedora para A e uma

estratégia vencedora para B.
FEOFILOFF Caminhos e circuitos 21

1.4 Caminhos e circuitos

Esta seção introduz dois tipos muito simples mas muito importantes de
grafos: os caminhos e os circuitos.16
Um grafo G é um caminho (= path) se VG admite uma permutação17
(v1 , v2 , . . . , vn ) tal que

EG = {vi vi+1 : 1 ≤ i < n} .

Os vértices v1 e vn são os extremos do caminho; os demais vértices são

internos.18 Diremos que esse caminho liga v1 a vn .
O caminho que acabamos de descrever pode ser denotado simplesmente
por v1 v2 · · · vn . Por exemplo, se dissermos “o caminho xywz” estaremos nos v1 v2 · · · vn
referindo ao grafo cujos vértices são x, y, w, z e cujas arestas são xy, yw e wz.
Um grafo G é um circuito (= circuit = polygon)19 se VG tem 3 ou mais
elementos e admite uma permutação (v1 , v2 , . . . , vn ) tal que

EG = {vi vi+1 : 1 ≤ i < n} ∪ {vn v1 } .

Este circuito pode ser denotado simplesmente por v1 v2 · · · vn v1 . Assim, se

dissermos “o circuito xywzx”, estaremos nos referindo ao grafo cujos vértices v1 v2 · · · vn v1
são x, y, w, z e cujas arestas são xy, yw, wz e zx.

Figura 1.7: Um caminho e um circuito.

O comprimento de um caminho20 ou circuito G é o número m(G). É

claro que um caminho de comprimento m tem m + 1 vértices e um circuito
comprimento m tem m vértices.
Um triângulo, quadrado, pentágono e hexágono é o mesmo que um
circuito de comprimento 3, 4, 5 e 6 respectivamente.

16
Convém insistir que, para nós, caminhos e circuitos são grafos. Em alguns livros,
caminhos e circuitos são tratados como sequências de vértices e não como grafos.
17
Uma permutação de um conjunto X é uma sequência em que cada elemento de X
aparece uma e uma só vez.
18
Alguns autores [Per09] dizem que um caminho só é caminho se tiver 2 ou mais vértices.
Para nós, entretanto, o grafo ({v}, ∅) é um caminho. Esse detalhe não é tão irrelevante quanto
pode parecer.
19
Alguns autores dizem “ciclo” (= cycle) no lugar de “circuito”.
20
A expressão “tamanho de um caminho” é ambígua: não se sabe se estamos falando do
número de vértices ou do número de arestas do caminho.
FEOFILOFF Caminhos e circuitos 22

Exercícios
◦ E 1.57 Faça uma figura de um caminho de comprimento 0, de um caminho
de comprimento 1 e de um caminho de comprimento 2. Faça uma figura de
um circuito de comprimento 3 e de um circuito de comprimento 4. Por que a
definição de circuito tem a restrição “n ≥ 3”?

◦ E 1.58 Seja V o conjunto {a, b, c, d, e} e E o conjunto {de, bc, ca, be}. Verifique
que o grafo (V, E) é um caminho. Agora suponha que F é o conjunto
{bc, bd, ea, ed, ac} e verifique que o grafo (V, F ) é um circuito.

◦ E 1.59 Faça um figura do caminho 1 2 4 3 5. Faça um figura do caminho

1 3 2 4 3 5. Faça um figura do circuito 1 2 4 3 5 1.

◦ E 1.60 Verifique que o caminho u v w x y z também pode ser denotado por

z y x w v u. Verifique que essas duas expressões representam o mesmo cami-
nho.

◦ E 1.61 Considere o circuito u v w x y z u. Mostre que z y x w v u z também é

um circuito. Mostre que qualquer permutação cíclica — como w x y z u v w,
por exemplo — também é um circuito. Mostre que todas essas expressões
representam o mesmo circuito.

◦ E 1.62 Exiba as matrizes de adjacências e incidências de um caminho de

comprimento 4. Exiba as matrizes de adjacências e incidências de um circuito
de comprimento 5.

◦ E 1.63 É verdade que o grafo do cavalo 3-por-3 é um circuito?

◦ E 1.64 Verifique que a grade 1-por-n é um caminho de comprimento n − 1.

Quais grades são circuitos?

◦ E 1.65 Suponha que P é um caminho de comprimento n−1 e O um circuito

de comprimento n. Quanto valem δ(P ), ∆(P ), δ(O) e ∆(O)?

◦ E 1.66 Faça uma figura do complemento de um caminho de compri-

mento 3. Faça uma figura do complemento de um caminho de compri-
mento 4. Faça uma figura do complemento de um circuito de comprimento 5.
Faça uma figura do complemento de um circuito de comprimento 6.

E 1.67 Quantos caminhos diferentes existem com conjunto de vértices

{1, 2, 3}? Quantos circuitos diferentes existem com conjunto de vértices
{1, 2, 3}? Quantos circuitos diferentes existem com conjunto de vértices
{1, 2, 3, 4}?
FEOFILOFF Caminhos e circuitos 23

E 1.68 É verdade que todo grafo 2-regular é um circuito?

E 1.69 Seja G um grafo com n(G) ≥ 3, ∆(G) = 2 e δ(G) = 1. Se G tem

exatamente dois vértices de grau 1, é verdade que G é um caminho?
 FEOFILOFF União e interseção de grafos 24

1.5 União e interseção de grafos

A união de dois grafos G e H é o grafo (VG ∪ VH , EG ∪ EH ). É natural denotar
G ∪ H esse grafo por G ∪ H.
A interseção de dois grafos G e H é o grafo (VG ∩ VH , EG ∩ EH ). É natural
G ∩ H denotar esse grafo por G ∩ H. Só trataremos da interação G ∩ H se VG ∩ VH
não for vazio.
Dois grafos G e H são disjuntos se os conjuntos VG e VH são disjuntos,
ou seja, se VG ∩ VH = ∅. É evidente que EG e EH também são disjuntos nesse
caso.

Exercícios
◦ E 1.70 Seja G um grafo completo com conjunto de vértices {1, 2, 3, 4, 5} e H
um grafo completo com conjunto de vértices {4, 5, 6, 7, 8}. Faça figuras dos
grafos G ∪ H e G ∩ H.

E 1.71 Seja G o grafo do bispo e H o grafo da torre (veja exercícios 1.10 e 1.11).
Mostre que G ∪ H é o grafo da dama.

◦ E 1.72 Seja G o circuito 1 2 3 4 5 6 1 e H o caminho 4 7 8 5. Faça figuras dos

grafos G ∪ H e G ∩ H.

E 1.73 Seja P um caminho com extremos u a v e Q um caminho com extremos

v e w. Mostre que se VP ∩ VQ = {v} então o grafo P ∪ Q é um caminho.

E 1.74 Suponha que os caminhos P e Q têm os mesmos extremos, digamos u

e v. Suponha ainda que VP ∩ VQ = {u, v}. Em que condições o grafo P ∪ Q é
um circuito?

E 1.75 Sejam A, B e C os conjuntos {1, 2, 3, 4}, {5, 6, 7} e {9, 10, 11}. Seja G o
grafo {A, B}-bipartido completo. Seja H o grafo {B, C}-bipartido completo.
Faça figuras dos grafos G ∪ H e G ∩ H.

E 1.76 Uma roda (= wheel) é qualquer grafo da forma G ∪ H, onde G é um

circuito e H é uma estrela (veja a seção 1.2) com centro v tal que VH r{v} = VG .
Faça figuras de rodas com 4, 5 e 6 vértices. Quanto valem os parâmetros m, δ
e ∆ de uma roda com n vértices?
FEOFILOFF Grafos planares 25

1.6 Grafos planares

Um grafo é planar se pode ser desenhado no plano sem que as linhas que
representam arestas se cruzem. Esta definição é imprecisa, mas suficiente
por enquanto. Daremos um definição melhor na seção 1.17.

Exercícios
◦ E 1.77 Verifique que todo caminho é planar. Verifique que todo circuito é
planar.

◦ E 1.78 Mostre que toda grade (veja exercício 1.6) é planar.

E 1.79 Mostre que o grafo dos estados do Brasil (veja exercício 1.17) é planar.

E 1.80 O grafo dos pontos no plano descrito no exercício 1.19 é planar?

E 1.81 Mostre que todo K4 é planar. É verdade que todo K5 é planar?

E 1.82 Mostre que todo K2,3 é planar. É verdade que todo K3,3 é planar?

E 1.83 Mostre que o grafo Q3 (veja exercício 1.14) é planar. O grafo Q4

também é planar? O grafo Q5 é planar?

E 1.84 O grafo do bispo t-por-t (veja exercício 1.10) é planar?

E 1.85 O grafo da dama t-por-t (veja exercício 1.8) é planar? O grafo do

cavalo t-por-t (veja exercício 1.9) é planar?

E 1.86 Mostre que o complemento de um circuito de comprimento 6 é planar.

 FEOFILOFF Subgrafos 26

1.7 Subgrafos
Um subgrafo de um grafo G é qualquer grafo H tal que VH ⊆ VG e EH ⊆ EG .
H⊆G É conveniente escrever “H ⊆ G” para dizer que H é subgrafo de G.
Um subgrafo H de G é gerador (= spanning) se VH = VG . (Há quem diga
abrangente no lugar de gerador [Per09].)
Um subgrafo H de G é próprio se VH 6= VG ou EH 6= EG . Às vezes é
H ⊂ G conveniente escrever “H ⊂ G” para dizer que H é subgrafo próprio de G.21
O subgrafo de G induzido por um subconjunto X de VG é o grafo (X, F )
G[X] onde F é o conjunto EG ∩ X (2) . Esse subgrafo é denotado por

G[X] .

G−X Para qualquer subconjunto X de VG , denotaremos por G − X o sub-

grafo G[VG r X]. Em particular, para qualquer vértice v,

G−v

é uma abreviatura de G − {v}. Para qualquer aresta e de G,

G−e

é o grafo (VG , EG r {e}). De modo mais geral, se A é um subconjunto de EG

G − A então G − A é o grafo (VG , EG r A). É claro que G − A é um subgrafo gerador
de G.

Exercícios
◦ E 1.87 Suponha que H é um subgrafo de G. Se VH = VG , é verdade que
H = G? Se EH = EG , é verdade que H = G?

◦ E 1.88 Seja G um grafo, V 0 um subconjunto de VG e E 0 um subconjunto

de EG . É verdade que (V 0 , E 0 ) é um subgrafo de G?

E 1.89 Repita o exercício 1.42: Use indução22 no número de arestas do grafo

para provar que todo grafo (V, E) satisfaz a identidade
P
v∈V d(v) = 2|E| .

◦ E 1.90 Seja v um vértice e e uma aresta de um circuito O. Mostre que o

grafo O − v é um caminho. Mostre que o grafo O − e é um caminho.
21
De modo geral, escreveremos “X ⊂ Y ” ou “Y ⊃ X” para dizer que o conjunto X é
subconjunto próprio de Y , ou seja, que X ⊆ Y mas X 6= Y .
22
Indução é a arte de reduzir um problema a uma versão menor dele mesmo.
FEOFILOFF Subgrafos 27

E 1.91 Mostre que todo subgrafo de um grafo planar é planar. Em outras

palavras, se um grafo G tem um subgrafo não planar então G não é planar.

E 1.92 Sejam v e w dois vértices de um grafo G. Suponha que d(v) = δ(G) e

d(w) = ∆(G). É verdade que δ(G − v) = δ(G) − 1? É verdade que ∆(G − w) =
∆(G) − 1?

◦ E 1.93 Verifique que o grafo do bispo t-por-t é um subgrafo do grafo da

dama t-por-t. Verifique que o grafo da torre t-por-t é um subgrafo do grafo
da dama t-por-t.

E 1.94 O grafo Q3 é subgrafo de Q4 ?

◦ E 1.95 Seja G um grafo {U, W }-bipartido. Mostre que os subgrafos induzi-

dos G[U ] e G[W ] são vazios.

◦ E 1.96 Mostre que todo subgrafo induzido de um grafo completo é com-

pleto. É verdade que todo subgrafo induzido de um caminho é um caminho?
É verdade que todo subgrafo induzido de um circuito é um caminho?

◦ E 1.97 Seja G o grafo representado na figura 1.8 e X o conjunto {a, b, f, e,

g, l}. Faça uma figura de G[X].

a b c d
e f g h

i j k l

Figura 1.8: Veja exercícios 1.97, 1.116 e 1.117.

E 1.98 ♥ Seja H o grafo das arestas (veja exercício 1.24) de um grafo G (por-
tanto, H = L(G)). Mostre que H não contém K1,3 como subgrafo induzido,
ou seja, mostre que não existe subconjunto X de VH tal que H[X] é um K1,3 .
Mostre que a recíproca não é verdadeira.

E 1.99 Seja H o grafo das arestas (veja exercício 1.24) de um grafo G (por-
tanto, H = L(G)). Seja H 0 um subgrafo induzido de H. Mostre que H 0 é o
grafo das arestas de algum grafo G0 .

E 1.100 Dado grafo G e inteiro k, encontrar um subconjunto máximo X de

VG tal que δ(G[X]) ≥ k. (Ou seja, dentre os subconjuntos X de VG que têm a
propriedade δ(G[X]) ≥ k, encontrar um de cardinalidade máxima.)
FEOFILOFF Subgrafos 28

E 1.101 Seja G um grafo tal que n(G) > 1 e δ(G) ≤ 12 µ(G). Mostre que G tem
um vértice x tal que
µ(G − x) ≥ µ(G) .
Em outras palavras, mostre que é possível retirar um vértice sem com isso
reduzir a média dos graus do grafo.

E 1.102 Mostre que todo grafo G com pelo menos uma aresta tem um sub-
grafo H tal que

δ(H) > µ(H)/2 mas µ(H) ≥ µ(G) .

FEOFILOFF Cortes 29

1.8 Cortes
Suponha que X é um conjunto de vértices de um grafo G. O corte associado
a X (ou franja de X) é o conjunto de todas as arestas que têm uma ponta em
X e outra em VG r X. O corte associado a X será denotado por ∂(X)

∂G (X)
ou simplesmente por ∂(X).23 (Alguns autores preferem escrever δ(X) ou
até ∇(X).)
Dizemos que os cortes ∂(∅) e ∂(VG ) são triviais. É evidente que os cortes
triviais são vazios.
É claro que |∂({v})| = d(v) para todo vértice v. Para qualquer conjunto
X de vértices, diremos que |∂(X)| é o grau de X e denotaremos esse número
por d(X): d(X)
d(X) := |∂(X)| .
Um corte (= cut = coboundary) em um grafo G é qualquer conjunto da
forma ∂(X), onde X é um subconjunto de VG . (Um corte é, portanto, um
conjunto de arestas e não de vértices.)

Exercícios
◦ E 1.103 Seja X um conjunto de vértices de um grafo G. Mostre que
(VG , ∂(X)) é um subgrafo gerador bipartido de G.

E 1.104 Seja G o grafo representado na figura 1.8. É verdade que o conjunto

{ae, ef, f j, jk, cd, dh} é um corte?

a b c d
e f g h

i j k l

Figura 1.9: Veja o exercício 1.104.

E 1.105 Encontre o menor corte não trivial que puder no grafo da dama
8-por-8. Encontre o maior corte não trivial que puder no grafo da dama.

E 1.106 Encontre o menor corte não trivial que puder no grafo do bispo
t-por-t.
23
Não confunda ∂ com a letra grega δ.
 FEOFILOFF Cortes 30

E 1.107 Encontre o menor corte que puder no grafo de Petersen. Encontre o

maior corte que puder no grafo de Petersen.

N(X) ◦ E 1.108 Para qualquer conjunto X de vértices, denotamos por N(X), o

conjunto dos vértices em VG r X que têm um ou mais vizinhos em X. É
verdade que d(X) = |N(X)|
S para todo X?
É claro que N(X) ⊆ x∈X N(x).24 É verdade que os dois conjuntos são
iguais?

? E 1.109 Mostre que para qualquer grafo G e qualquer subconjunto X de VG

tem-se P
x∈X dG (x) = 2m(G[X]) + dG (X) . (1.2)
(Isso é uma generalização do exercício 1.42.)

E 1.110 Suponha que todos os vértices de um grafo G têm grau par. É

verdade d(X) é par para todo subconjunto X de VG ?
Suponha que todos os vértices de um grafo G têm grau ímpar. É verdade
d(X) é ímpar para todo subconjunto próprio e não vazio X de VG ?

E 1.111 (C ORTE GRANDE) Mostre que em todo grafo existe um corte que
contém pelo menos a metade das arestas do grafo. Em outras palavras, mos-
tre que todo grafo G tem um conjunto X de vértices tal que d(X) ≥ 21 m(G).

E 1.112 Mostre que todo grafo G tem um subgrafo gerador bipartido H que
satisfaz a condição dH (v) ≥ dG (v)/2 para todo vértice v.

Operações sobre cortes

E 1.113 (D IFERENÇA SIMÉTRICA) Mostre que ∂(X ⊕ Y ) = ∂(X) ⊕ ∂(Y ) para
A⊕B quaisquer conjuntos X e Y de vértices de um grafo. Aqui, A ⊕ B denota a
diferença simétrica25 dos conjuntos A e B.

E 1.114 (S UBMODULARIDADE) Mostre que em qualquer grafo G, para

quaisquer subconjuntos X e Y de VG ,

d(X ∪ Y ) + d(X ∩ Y ) ≤ d(X) + d(Y ) .

24
S
Se X = {x1 , x2 , . . . , xk } então x∈X N(x) é o conjunto N(x1 )∪N(x2 )∪· · ·∪N(xk ), sendo
N(xi ) o conjunto de vizinhos de xi , conforme a seção 1.3.
25
A diferença simétrica de dois conjuntos A e B é o conjunto (A r B) ∪ (B r A). É fácil
verificar que A ⊕ B = (A ∪ B) r (A ∩ B).
FEOFILOFF Cortes 31

E 1.115 (Consequência de 1.114) Sejam v e w dois vértices de um grafo G.

Um isolador 26 é qualquer subconjunto de VG que contém v mas não con-
tém w. Um isolador X é mínimo se d(X) ≤ d(X 0 ) para todo isolador X 0 .
Mostre que se X e Y são isoladores mínimos então X ∪ Y e X ∩ Y também
são isoladores mínimos.

26
O termo isolador não é padrão. Ela está sendo usada aqui (e no capítulo 15) por falta
de uma palavra melhor.
 FEOFILOFF Caminhos e circuitos em grafos 32

1.9 Caminhos e circuitos em grafos

Se um caminho v1 · · · vp é subgrafo de G, dizemos simplesmente que v1 · · · vp
é um caminho em G ou que G contém o caminho v1 · · · vp . Por exem-
plo, se dissermos que u v w z é um caminho em G, devemos entender que
({u, v, w, z}, {uv, vw, wz}) é um subgrafo de G. Convenção análoga vale para
circuitos que são subgrafos de G.27
Se v e w são os dois extremos de um caminho em G, é cômodo dizer que
o caminho vai de v a w ou que começa em v e termina em w. Mas é preciso
usar estas expressões com cautela pois caminhos são objetos estáticos e não
têm orientação.
máximo Um caminho P em um grafo G é máximo se G não contém um caminho
maximal de comprimento maior que o de P . Um caminho P em G é maximal se não
existe caminho P 0 em G tal que P ⊂ P 0 .

Exercícios
◦ E 1.116 Seja G o grafo representado na figura 1.8. É verdade que e a b f g k é
um caminho em G? É verdade que e a b f c d é um caminho em G? É verdade
que e a b f g k j i e é um circuito em G?

E 1.117 Seja G o grafo da figura 1.8. É verdade que G contém um circuito

de comprimento 6? É verdade que G contém um circuito induzido de
comprimento 6? (Ou seja, é verdade que existe um subconjunto X de VG tal
que G[X] é um circuito de comprimento 6?) Exiba um caminho induzido de
comprimento 3 em G. (Ou seja, exiba um conjunto X de vértices tal que G[X]
é um caminho de comprimento 3.) Exiba um caminho de comprimento 3 em
G que não seja induzido.

. E 1.118 Sejam P um caminho com extremos x e x0 e seja Q um caminho

com extremos y e y 0 . Suponha que VP ∩ VQ 6= ∅. Mostre existe um caminho
com extremos x e y no grafo P ∪ Q (veja seção 1.5).
Pergunta adicional: Se z é um vértice em VP ∩ VQ , é verdade que existe,
no grafo P ∪ Q, um caminho de x a y que passa por z?

E 1.119 Encontre um circuito de comprimento mínimo no grafo de Petersen

(veja exercício 1.15 ou figura 1.6). Encontre um circuito de comprimento má-
ximo no grafo de Petersen. Encontre um caminho de comprimento máximo
no grafo de Petersen.
27
Eu gostaria de dizer “subcaminho de G” e “subcircuito de G”. Infelizmente, essas
expressões não são usadas na literatura.
FEOFILOFF Caminhos e circuitos em grafos 33

◦ E 1.120 Verifique que o grafo do cavalo 3-por-3 contém um circuito. Encon-

tre o circuito mais longo que puder no grafo do cavalo 4-por-4.

E 1.121 Encontre o mais longo caminho que puder no grafo da dama. En-
contre o mais longo circuito que puder no grafo da dama.

E 1.122 O grafo de Heawood28 tem conjunto de vértices {0, 1, 2, . . . , 13}.

Cada vértice i é vizinho de (i + 1) mod 14 e de (i + 13) mod 14.29 Além
disso, cada i é vizinho de um terceiro vértice, que depende da paridade de i:
se i é par então ele é vizinho de (i + 5) mod 14 e se i é ímpar então ele é
vizinho de (i + 9) mod 14. Faça uma figura do grafo. Encontre um circuito de
comprimento mínimo no grafo de Heawood.

E 1.123 Suponha que um grafo G tem um circuito ímpar. Mostre que G

também tem um circuito ímpar induzido, ou seja, que existe um conjunto X
de vértices tal que G[X] é um circuito ímpar. Algo análogo vale para circuitos
pares?

E 1.124 Dê um exemplo de um grafo G e um caminho em G que seja maximal

mas não seja máximo.

. E 1.125 ♥ Suponha que d(v) ≥ k para todo vértice v de um grafo. Mostre

que o grafo tem um caminho de comprimento pelo menos k. (Sugestão: tome
um caminho maximal.)30
O problema poderia ter sido formulado assim: mostre que todo grafo G
contém um caminho com pelo menos δ(G) + 1 vértices.

. E 1.126 Seja G um grafo tal que δ(G) ≥ 2. Prove que G tem um circuito.

E 1.127 Seja G um grafo tal que δ(G) ≥ 3. Prove que G tem um circuito de
comprimento par.

E 1.128 Seja k um número natural maior que 1. Suponha que d(v) ≥ k para
todo vértice v de um grafo G. Mostre que G tem um circuito de comprimento
pelo menos k + 1. Em outras palavras, mostre que G tem um circuito com
pelo menos δ(G) + 1 vértices, desde que δ(G) > 1. (Veja exercício 1.125.)
28
Percy John Heawood ( − ). (Veja verbete na Wikipedia.)
29
A expressão “i mod j” denota o resto da divisão de i por j.
30
O capítulo 17 discute o importante mas difícil problema de encontrar um caminho de
comprimento máximo em um grafo.
FEOFILOFF Caminhos e circuitos em grafos 34

. E 1.129 Seja P um caminho maximal num grafo G. Sejam u e w os extremos

de P e suponha que d(u) + d(w) ≥ |VP | ≥ 3. Mostre que G tem um circuito
cujo conjunto de vértices é VP .

E 1.130 Seja G um grafo com n > 1 vértices e pelo menos 2n arestas. Mostre
que G tem um circuito de comprimento ≤ 2 log2 n.

E 1.131 Seja G um grafo sem circuitos de comprimento menor que 5. Mostre

que n(G) ≥ δ(G)2 + 1.

E 1.132 Mostre que todo grafo G com pelo menos k n(G) arestas contém um
caminho de comprimento k. (Combine os exercícios 1.102 e 1.125.)

Caminhos e circuitos versus cortes

Dizemos que um corte ∂(X) separa um vértice x de um vértice y se X contém
x mas não contém y. É claro que se ∂(X) separa x de y então X separa y de x.

E 1.133 Seja P um caminho num grafo G. Seja X um conjunto de vértices

que contém um e apenas um dos extremos de P . Mostre que EP ∩ ∂(X) 6= ∅.

? E 1.134 Prove que, para qualquer par (x, y) de vértices de qualquer grafo,
vale uma e apenas uma das seguintes afirmações: (1) um caminho liga x a y
ou (2) um corte vazio separa x de y. (Outra maneira de formular a mesma
questão: prove que existe um caminho de x a y se e somente se nenhum corte
vazio separa x de y.)

E 1.135 (A LGORITMO) Construa um algoritmo eficiente que receba vértices

v e w de um grafo G e encontre um caminho que vá de v a w ou mostre que
tal caminho não existe.

Passeios, trilhas e ciclos

Um passeio (= walk) em um grafo é qualquer sequência finita (v0 , v1 , v2 , . . . ,
vk−1 , vk ) de vértices tal que vi é adjacente a vi−1 para todo i entre 1 e k. (Os
vértices do passeio podem não ser distintos dois a dois.) Dizemos que o
vértice v0 é a origem do passeio e que vk é o término do passeio. Dizemos
também que o passeio vai de v0 a vk e que o passeio liga v0 a vk .
As arestas do passeio são v0 v1 , v1 v2 , . . . , vk−1 vk . (Essas arestas podem não
ser distintas duas a duas.) O comprimento do passeio é o número k.
FEOFILOFF Caminhos e circuitos em grafos 35

Uma trilha (= trail) é um passeio sem arestas repetidas, isto é, um passeio

cujas arestas são distintas duas a duas. É claro que o comprimento de uma
trilha é igual à cardinalidade do seu conjunto de arestas.
Um passeio é simples se os seus vértices são distintos dois a dois, ou
seja, se não tem vértices repetidos. É evidente que todo passeio simples é,
em particular, uma trilha.
Um passeio (v0 , . . . , vk ) é fechado (= closed) se sua origem coincide com o
término, ou seja, se v0 = vk .
Um ciclo (= cycle) é uma trilha fechada, ou seja, um passeio fechado sem
arestas repetidas.31

. E 1.136 Seja (v0 , v1 , v2 , . . . , vk ) um passeio com origem r e término s em

um grafo G. Mostre que G tem um caminho com extremos r e s. Mais
especificamente, mostre há um caminho com extremos r e s no subgrafo
({v0 , v1 , v2 , . . . , vk } , {v0 v1 , v1 v2 , . . . , vk−1 vk }) de G.

E 1.137 Suponha que (v0 , . . . , vk ) é uma passeio fechado em um grafo G. É

verdade que G tem um circuito?

. E 1.138 Seja (v0 , v1 , v2 , . . . , vk ) um ciclo em um grafo G. Mostre que há um

circuito no subgrafo ({v1 , v2 , . . . , vk }, {v0 v1 , v1 v2 , . . . , vk−1 vk }) de G.

◦ E 1.139 Sejam v0 , . . . , v5 alguns vértices (não necessariamente distintos dois

a dois) de um grafo G. Quais das seguintes afirmações são verdadeiras:
(1) se v0 v1 v2 v3 v4 v5 é um caminho em G então (v0 , v1 , v2 , v3 , v4 , v5 ) é um passeio
simples; (2) se v0 v1 v2 v3 v4 v5 v0 é um circuito em G então (v0 , v1 , v2 , v3 , v4 , v5 , v0 )
é um ciclo; (3) se (v0 , v1 , v2 , v3 , v4 , v5 ) é uma trilha então v0 v1 v2 v3 v4 v5 é um
caminho; (4) se (v0 , v1 , v2 , v3 , v4 , v5 , v0 ) é um ciclo então v0 v1 v2 v3 v4 v5 v0 é um
circuito.

31
De acordo com essa definição, um ciclo pode ter comprimento 0. Já um circuito, por
definição, tem comprimento pelo menos 3.
FEOFILOFF Grafos conexos 36

1.10 Grafos conexos

Em qualquer grafo G, dizemos um vértice v está ligado a um vértice w se G
contém um caminho com extremos v e w. É evidente que a relação é simétrica:
se v está ligado a w então também w está ligado a v.
Um grafo é conexo (= connected) se seus vértices são ligados dois a dois.
Em outras palavras, um grafo é conexo se v é ligado a w para cada par (v, w)
de seus vértices.
Um grafo G é conexo se e somente se ∂(X) 6= ∅ para todo subconjunto
próprio e não vazio X de VG . (Veja exercício 1.148.)

Exercícios
E 1.140 O grafo do cavalo 3-por-3 é conexo? O grafo do bispo t-por-t é
conexo?

E 1.141 Mostre que o grafo Qk é conexo (qualquer que seja k).

E 1.142 Mostre que todo caminho é um grafo conexo. Mostre que todo
circuito é um grafo conexo.

. E 1.143 Sejam P e Q dois caminhos tais que VP ∩ VQ 6= ∅. Mostre que o

grafo P ∪ Q (veja seção 1.5) é conexo.

. E 1.144 Sejam G e H dois grafos conexos tais que VG ∩ VH 6= ∅. Mostre que

o grafo G ∪ H (veja seção 1.5) é conexo.

◦ E 1.145 Sejam G e H dois grafos. Quais das seguinte implicações são

verdadeiras? 1. Se VG ∩ VH = ∅ então G ∪ H não é conexo. 2. Se G ∪ H é
conexo então VG ∩ VH 6= ∅. 3. Se G ∪ H não é conexo então VG ∩ VH = ∅.

. E 1.146 ♥ Suponha que um certo vértice x de um grafo G é ligado a cada

um dos demais vértice. Mostre que G é conexo.

◦ E 1.147 Suponha que um subgrafo gerador H de um grafo G é conexo.

Mostre que G é conexo.

? E 1.148 Mostre que um grafo G é conexo se e somente se ∂(X) 6= ∅ para

todo X tal que ∅ ⊂ X ⊂ VG .

◦ E 1.149 Seja G um grafo e X um subconjunto próprio e não vazio de VG

(isto é, ∅ ⊂ X ⊂ VG ). Mostre que o grafo G − ∂(X) não é conexo.
FEOFILOFF Grafos conexos 37

◦ E 1.150 Quais das seguintes afirmações são verdadeiras para qualquer

grafo G? 1. Se G é conexo então ∂(X) 6= ∅ para todo X tal que ∅ ⊂ X ⊂ VG .
2. Se G é conexo então ∂(X) 6= ∅ para algum X tal que ∅ ⊂ X ⊂ VG . 3. Se
∂(X) 6= ∅ para todo X tal que ∅ ⊂ X ⊂ VG então G é conexo. 4. Se ∂(X) 6= ∅
para algum X tal que ∅ ⊂ X ⊂ VG então G é conexo.

E 1.151 Prove que se um grafo G não é conexo então seu complemento G é

conexo.

E 1.152 (A LGORITMO) Construa um algoritmo eficiente que decida se um

grafo é conexo. O que o seu algoritmo devolve (ou seja, qual a “saída” do
algoritmo)?

E 1.153 Sejam x, y e z três vértices de um grafo conexo G. É verdade que G

tem um caminho que contém x, y e z?

◦ E 1.154 Seja X um conjunto de vértices de um grafo conexo G. É verdade

que G[X] é conexo?

?◦ E 1.155 Seja e uma aresta e v um vértice de um circuito O. Mostre que o

grafo O − e é conexo. Mostre que O − v é conexo.

◦ E 1.156 Seja e uma aresta e v um vértice de um caminho P . Em que

condições P − e é conexo? Em que condições P − v é conexo?

. E 1.157 Seja O um circuito em um grafo conexo G. Mostre que G − e é

conexo para toda aresta e de O.

E 1.158 Seja v um vértice de grau 1 num grafo conexo G. Mostre que o grafo
G − v é conexo.

E 1.159 Suponha que G é um grafo conexo com pelo menos uma aresta. É
verdade que existe uma aresta a tal que G − a é conexo?

◦ E 1.160 Seja G um grafo conexo e seja v um dos extremos de um caminho

maximal (veja página 32) em G. É verdade que G[N(v)] é conexo?

E 1.161 ♥ Mostre que todo grafo conexo G com dois ou mais vértices tem um
vértice v tal que G − v é conexo.

? E 1.162 Prove que todo grafo conexo com n vértices tem pelo menos n − 1
arestas. Em outras palavras, mostre que em todo grafo conexo G tem-se
m(G) ≥ n(G) − 1 .
FEOFILOFF Grafos conexos 38

E 1.163 Seja k um número natural não nulo e G um grafo {U, W }-bipartido.

Suponha que |U | ≤ k e |W | ≤ k. Mostre que se δ(G) > k/2 então G é conexo.

E 1.164 Seja G um grafo tal que δ(G) ≥ n(G)/2. Mostre que G é conexo.

E 1.165 Seja G um grafo tal que δ(G) ≥ bn(G)/2c.32 Mostre que G é conexo.
(Mostre que o resultado é o melhor possível no seguinte sentido: existem
grafos desconexos com d(v) ≥ bn/2c − 1 para todo vértice v.)

◦ E 1.166 Suponha que d(v) + d(w) ≥ n − 1 para todo par (v, w) de vértices
não adjacentes de um grafo G. Mostre que G é conexo.

E 1.167 Mostre que todo grafo com n vértices e mais que 21 (n − 1)(n − 2)
arestas é conexo.

◦ E 1.168 Seja G um grafo e k um número natural. Mostre que d(X) ≥ k

para todo X tal que ∅ ⊂ X ⊂ VG se e somente se G − F é conexo para todo
subconjunto F de EG tal que |F | < k.

E 1.169 Prove que se um grafo G é conexo então o grafo das arestas L(G)
também é conexo.

E 1.170 (C AMINHOS MÁXIMOS NÃO SÃO DISJUNTOS) Sejam P ∗ e Q∗ dois

caminhos de comprimento máximo em um grafo conexo G. Mostre que P ∗ e
Q∗ têm um vértice em comum.

32
Por definição, bxc é o único inteiro i tal que i ≤ x < i + 1.
FEOFILOFF Componentes 39

1.11 Componentes
Um subgrafo conexo H de um grafo G é maximal (com relação à propriedade
de ser conexo) se não faz parte de um subgrafo conexo maior, ou seja, se não
existe grafo conexo H 0 tal que H ⊂ H 0 ⊆ G.
Um componente de um grafo G é qualquer subgrafo conexo maximal
de G. O número de componentes de um grafo G será denotado por c(G)

c(G) .

É claro que um grafo G é conexo se e somente se c(G) = 1.

O número de componentes de um grafo G é pelo menos tão grande
quanto n(G) − m(G). (Veja exercício 1.192.)

Exercícios
E 1.171 Quantos componentes tem o grafo do cavalo 3-por-3? Quantos com-
ponentes tem o grafo do bispo t-por-t?

E 1.172 Seja a uma aresta e v um vértice de um caminho P . Mostre que

P − a tem exatamente dois componentes. Mostre que P − v tem um ou dois
componentes.

E 1.173 Seja a uma aresta e v um vértice de um circuito O. Mostre que O − a

tem um só componente. Mostre que O − v tem um só componente.

E 1.174 Seja P um caminho e S um subconjunto próprio de VP . Prove que

c(P − S) ≤ |S| + 1.

E 1.175 Seja O um circuito e S um subconjunto de VO tal que 0 < |S| < n(O).
Prove que c(O − S) ≤ |S|.

E 1.176 Suponha que exatamente dois vértices, digamos u e v, de um grafo

G têm grau ímpar. Mostre que existe um caminho em G cujos extremos são
u e v.

. E 1.177 Seja G um grafo tal que ∆(G) ≤ 2. Descreva os componentes de G.

E 1.178 Seja G um grafo 2-regular. Mostre que cada componente de G é um

circuito.
FEOFILOFF Componentes 40

◦ E 1.179 Mostre que, em qualquer grafo, todo vértice pertence a um e ape-

nas um componente. Em outras palavras, mostre que em qualquer grafo G os
conjuntos de vértices de todos os componentes formam uma partição de VG .

◦ E 1.180 Seja H um componente de um grafo G. Mostre que ∂G (VH ) = ∅.

◦ E 1.181 Seja X um conjunto de vértices de um grafo G. Prove ou desprove

a seguinte afirmação: Se ∅ ⊂ X ⊂ VG e ∂G (X) = ∅ então G[X] é um
componente de G.

E 1.182 Seja X um conjunto não vazio de vértices de um grafo G. Mostre que

G[X] é um componente de G se e somente se G[X] é conexo e ∂G (X) = ∅.

? E 1.183 Seja x um vértice de um grafo G. Seja X o conjunto de todos os

vértices ligados a x. Mostre que G[X] é um componente de G.

E 1.184 (A LGORITMO) Construa um algoritmo eficiente que receba um vér-

tice x de um grafo G e calcule o conjunto de vértices do componente de G
que contém x.

E 1.185 (A LGORITMO) Construa um algoritmo eficiente que calcule o nú-

mero de componentes de qualquer grafo dado.

E 1.186 Seja H um subgrafo gerador de um grafo G. Mostre que c(H) ≥ c(G).

E 1.187 Seja e uma aresta de um grafo G. Mostre que c(G) ≤ c(G − e) ≤

c(G) + 1 para qualquer aresta e de G.

◦ E 1.188 Seja X um conjunto de vértices de um grafo G. Suponha que

c(G − X) > |X| + 1. É verdade que G não é conexo?

E 1.189 Seja v um vértice de um grafo conexo G. Mostre que o número de

componentes de G − v não passa de d(v).

E 1.190 Seja G um grafo conexo e suponha que d(v) é par para todo vértice v
de G. Mostre que, para qualquer vértice v, o número de componentes de
G − v não passa de 12 d(v).

E 1.191 (A LGORITMO) Construa um algoritmo eficiente para o seguinte pro-

blema: Dado um grafo G e um número natural k, encontrar um conjunto X
de não mais que k vértices que maximize o número de componentes de G−X.
FEOFILOFF Componentes 41

? E 1.192 Mostre que em todo grafo G tem-se

m(G) ≥ n(G) − c(G) .

E 1.193 Sejam n, m e c os números de vértices, de arestas e de componentes,

respectivamente, de um grafo G. Mostre que

m ≤ 12 (n − c)(n − c + 1) .
FEOFILOFF Pontes 42

1.12 Pontes
Uma ponte (= bridge) ou istmo (= isthmus) ou aresta de corte (= cut edge) em
um grafo G é qualquer aresta e tal que c(G − e) > c(G), ou seja, G − e tem
mais componentes que G.
Uma aresta e é ponte se e somente se o conjunto {e} é um corte do um
grafo. (Veja exercício 1.197.)
Há uma interessante “dicotomia” entre pontes e circuitos: em qualquer
grafo, toda aresta é uma ponte ou pertence a um circuito, mas não ambos.
(Veja o exercício 1.199.)

Exercícios
◦ E 1.194 O grafo do bispo t-por-t tem pontes?

E 1.195 Suponha que um grafo G tem uma ponte uv. Que aparência tem a
matriz de adjacências de G? Que aparência tem a matriz de incidências de G?

◦ E 1.196 Seja uv uma aresta de um grafo G. Mostre que uv é uma ponte se e

somente se u v é o único caminho em G que tem extremos u e v.

◦ E 1.197 Seja e uma aresta de um grafo G. Mostre que e é uma ponte se e

somente se {e} é um corte, ou seja, {e} = ∂(X) para algum conjunto X de
vértices. (Veja também o exercício 1.187.)

◦ E 1.198 Seja G o grafo que tem vértices a, b, . . . , g e arestas ab, bc, cd, de,
ec, bf , gb, ag. Quais das arestas pertencem a circuitos? Quais das arestas são
pontes?

? E 1.199 (D ICOTOMIA PONTES / CIRCUITOS) Prove que, em qualquer grafo,

toda aresta é de um e apenas um de dois tipos: ou ela pertence a um circuito
do grafo ou é uma ponte.

E 1.200 Que aparência tem um grafo se todas as suas arestas são pontes?
Que aparência tem um grafo se cada uma de suas arestas pertence a um
circuito?

E 1.201 Suponha que todos os vértices de um grafo G têm grau par. Mostre
que G não tem pontes.

E 1.202 Seja r um número natural maior que 1 e G um grafo bipartido r-

regular. Prove que G não tem pontes.
FEOFILOFF Pontes 43

E 1.203 Seja G um grafo conexo e X um subconjunto de VG tal que d(X) = 1.

Mostre que os grafos induzidos G[X] e G[X] são ambos conexos.

E 1.204 (A LGORITMO) Construa um algoritmo que encontre as pontes de

um grafo.
FEOFILOFF Grafos aresta-biconexos 44

1.13 Grafos aresta-biconexos

Um grafo é aresta-biconexo (= edge-biconnected) se for conexo, tiver três ou
mais vértices, e não tiver pontes.33
Um grafo com três ou mais vértices é aresta-biconexo se e somente se
cada par de seus vértices é ligado por dois caminhos sem arestas em comum.
(Veja exercício 1.208.) Esta propriedade explica o nome “aresta-biconexo”.

Exercícios
◦ E 1.205 Mostre que todo circuito é aresta-biconexo. Mostre que caminhos
não são aresta-biconexos.

E 1.206 Mostre que cada um dos dois componentes do grafo do bispo 3-por-3
é aresta-biconexo.

◦ E 1.207 Seja G um grafo aresta-biconexo. Mostre que d(X) ≥ 2 para todo

subconjunto não vazio e próprio X de VG .

? E 1.208 (D OIS CAMINHOS SEM ARESTAS EM COMUM) Seja G um grafo com

três ou mais vértices dotado da seguinte propriedade: todo par de vértices de
G é ligado por dois caminhos sem arestas em comum. Em outras palavras,
suponha que para cada par (r, s) de vértices de G existem caminhos P e Q,
ambos com extremos r e s, tais que EP ∩ EQ = ∅. Mostre que G é aresta-
biconexo.
Seja G um grafo aresta-biconexo. Mostre que todo par de vértices de
G é ligado por dois caminhos sem arestas em comum.34 (Compare com o
exercício 1.134.)

E 1.209 Mostre que m(G) ≥ n(G) para todo grafo aresta-biconexo G.

33
Em algumas áreas da Computação, diz-se que um tal grafo é “tolerante a falhas”.
34
Veja generalização no capítulo 15, exercício 15.7.
FEOFILOFF Articulações e grafos biconexos 45

1.14 Articulações e grafos biconexos

Uma articulação (= articulation) ou vértice de corte (= cut vertex) num grafo G
é um vértice v tal que c(G − v) > c(G), ou seja, G − v tem mais componentes
que G.
Um grafo é biconexo (= biconnected) se for conexo, sem articulações, e
tiver três ou mais vértices.35
Um grafo com três ou mais vértices é biconexo se e somente se cada par
de seus vértices estiver ligado por dois caminhos internamente disjuntos (ou
seja, dois caminhos sem vértices internos em comum). (Veja exercício 1.218.)
Essa propriedade explica o nome “biconexo”.
Segue daí que um grafo é biconexo se e somente se cada par de seus
vértices pertence a um circuito. (Veja o exercício 1.219.)

Exercícios
E 1.210 Seja v um vértice de um grafo G. Mostre que v é uma articulação se e
somente se existem dois vértices x e y em VG r{v} tais que (1) algum caminho
em G vai de x a y e (2) todo caminho de x a y contém v.

E 1.211 Seja v uma articulação de um grafo G. Que aparência tem a matriz

de adjacências de G? Que aparência tem a matriz de incidências de G?

◦ E 1.212 É verdade que todo grafo sem articulações não tem pontes? É
verdade que todo grafo sem pontes não tem articulações?

◦ E 1.213 Seja T uma árvore e v um vértice de T tal que d(v) ≥ 2. É verdade

que v é uma articulação?

E 1.214 (A LGORITMO) Construa um algoritmo que encontre todas as articu-

lações de um grafo.

E 1.215 Mostre que todo circuito é biconexo.

E 1.216 O grafo do bispo 3-por-3 tem dois componentes. Mostre que apenas
um deles é biconexo.

◦ E 1.217 Mostre que nem todo grafo aresta-biconexo é biconexo. Mostre que
todo grafo biconexo é aresta-biconexo.
35
Em algumas áreas da Computação, diz-se que um tal grafo é “tolerante a falhas”.
FEOFILOFF Articulações e grafos biconexos 46

? E 1.218 (D OIS CAMINHOS INTERNAMENTE DISJUNTOS ) Seja G um grafo

com três ou mais vértices dotado da seguinte propriedade: todo par de
vértices de G é ligado por dois caminhos internamente disjuntos. Em outras
palavras, suponha que para cada par (r, s) de vértices de G existem caminhos
P e Q, ambos com extremos r e s, tais que VP ∩ VQ = {r, s}. Mostre que G é
biconexo.
Seja G um grafo biconexo. Mostre que cada par de vértices de G é ligado
por dois caminhos internamente disjuntos.36

E 1.219 (A RTICULAÇÕES VERSUS CIRCUITOS) Suponha que todo par de vér-

tices de um grafo G pertence a algum circuito. Mostre que G não tem
articulações.
Seja G um grafo biconexo. Mostre que todo par de vértices de G pertence
a algum circuito. (Veja exercício 1.218.)

E 1.220 Exiba um grafo dotado da seguinte propriedade: quaisquer dois

vértices do grafo pertencem a um mesmo circuito mas há três vértices que
não pertencem a um mesmo circuito.

E 1.221 Seja G um grafo conexo sem articulações. Supondo que δ(G) ≥ 3,

mostre que G tem um vértice v tal que G − v é conexo e não tem articulações.
(Compare com o exercício 1.161 na seção 1.10.)

36
Veja generalização no capítulo 16, exercício 16.8.
FEOFILOFF Florestas e árvores 47

1.15 Florestas e árvores

Esta seção trata de duas espécies importantes de grafos: as florestas e as
árvores. Árvores são uma generalização de caminhos (veja os exercícios 1.224
e 1.225) e florestas são uma generalização de árvores.
Uma floresta (= forest), ou grafo acíclico, é um grafo sem circuitos. Essa
definição pode ser reformulada assim: um grafo é uma floresta se cada uma
de suas arestas é uma ponte (veja exercício 1.223).
Uma árvore (= tree) é uma floresta conexa. É claro que cada componente
de uma floresta é uma árvore.37
Uma folha (= leaf ) de uma floresta é qualquer vértice da floresta que
tenha grau 1.
Um grafo G é uma floresta se e somente se m(G) = n(G) − c(G). (Veja
exercício 1.231.)
Quaisquer duas das seguintes propriedades implicam a terceira: “G é flo-
resta”, “G é conexo” e “m(G) = n(G) − 1”. (Veja exercícios 1.228, 1.229
e 1.230.)

Exercícios
◦ E 1.222 Mostre que todo caminho é uma árvore. Mostre que toda estrela
(veja a seção 1.2) é uma árvore.

? E 1.223 Mostre que um grafo é uma floresta se e somente se cada uma de

suas arestas é uma ponte. (Veja o exercício 1.199.)

E 1.224 Seja (v1 , v2 , v3 , . . . , vn ) uma sequência de objetos distintos dois a dois.

Para cada j, seja i(j) um elemento de {1, . . .
, j−1}. Mostre que o grafo
{v1 , v2 , v3 , . . . , vn } , {v2 vi(2) , v3 vi(3) , . . . , vn vi(n) } é uma árvore. (Compare
essa construção com a definição de caminho na seção 1.4.) (Compare com
o exercício 1.225.)

E 1.225 Seja T uma árvore. Mostre que existe uma permutação (v1 , v2 , . . . , vn )
de VT dotada da seguinte propriedade: para j = 2, . . . , n, o vértice vj é
adjacente a exatamente um dos vértices do conjunto {v1 , . . . , vj−1 }. (Compare
com o exercício 1.224.)
37
Na Ciência da Computação, a palavra “árvore” traz à mente as ideias de pai e filho. No
presente contexto, entretanto, as expressões “pai de um vértice” e “filho de um vértice” não
fazem sentido. (Eles só adquirem sentido se um dos vértices da árvore for escolhido para
fazer o papel de “raiz”. Se r é a raiz da árvore então o pai de qualquer outro vértice v é o
vértice adjacente a v no único caminho (veja exercício 1.226) que liga v a r. Todo vizinho de
v que não seja o pai de v é filho de v.)
FEOFILOFF Florestas e árvores 48

? E 1.226 Mostre que um grafo é uma floresta se e somente se tem a seguinte

propriedade: para todo par (x, y) de seus vértices, existe no máximo um
caminho com extremos x e y no grafo.

E 1.227 (A LGORITMO) Construa um algoritmo eficiente que decida se um

grafo dado é uma árvore.

? E 1.228 Prove m(T ) = n(T ) − 1 em toda árvore T . (Compare com o

exercício 1.162.)

? E 1.229 Seja G um grafo conexo G tal que m(G) = n(G) − 1. Prove que G é
uma árvore.

E 1.230 Seja F uma floresta tal que m(F ) = n(F ) − 1. Prove que F é uma
árvore.

? E 1.231 Mostre que um grafo G é uma floresta se e somente se m(G) =

n(G) − c(G). (Compare com o exercício 1.192.)

. E 1.232 Mostre que toda árvore com pelo menos uma aresta tem pelo me-
nos duas folhas.

E 1.233 Mostre que toda floresta F tem pelo menos ∆(F ) folhas.

E 1.234 Seja T uma árvore com dois ou mais vértices. P

Seja X o conjunto dos
vértices cujo grau é maior que 2. Mostre que T tem 2+ x∈X (d(x)−2) folhas.

E 1.235 Seja T uma árvore com vértices 1, . . . , n. Suponha que os graus

dos vértices 1, 2, 3, 4, 5, 6 são 7, 6, 5, 4, 3, 2 respectivamente e que os vértices
7, . . . , n são folhas. Determine n (e portanto o número de folhas da árvore).

E 1.236 Seja T uma árvore com p + q vértices. Suponha que p dos vértices
têm grau 4 e q são folhas. Mostre que q = 2p + 2.38

E 1.237 Seja T uma árvore com pelo menos três vértices. É verdade que o
complemento T de T é conexo a menos que T seja um estrela?
38
Imagine que os vértices de grau 4 são átomos de carbono e os de grau 1 são átomos
de hidrogênio. O grafo representa então a molécula do hidrocarboneto Cp Hq . Veja o
exercício 1.5.
FEOFILOFF Florestas e árvores 49

E 1.238 Sejam T uma árvore e U um subconjunto de VT . Supondo que |U | é

par, mostre que existe um subconjunto X de ET tal que dT −X (u) é ímpar para
todo u em U e dT −X (v) é par para todo v em VT r U .

E 1.239 (P ROPRIEDADE DE H ELLY39 ) Sejam P, Q, R três caminhos em uma

árvore e T . Suponha que VP ∩ VQ 6= ∅, VQ ∩ VR 6= ∅ e VP ∩ VR 6= ∅. Prove que
VP ∩ VQ ∩ VR 6= ∅.

E 1.240 Mostre que toda floresta é planar.

39
Referência ao matemático Eduard Helly ( − ).
FEOFILOFF Menores de grafos 50

1.16 Menores de grafos

Esta seção introduz o conceito de menor, que pode ser entendido como uma
generalização da ideia de subgrafo. Pode-se dizer que um menor descreve
a estrutura “grossa” do grafo, enquanto um subgrafo descreve a estrutura
“fina”. Menores têm um papel importante no estudo da planaridade (capí-
tulo 19), da coloração de vértices (capítulo 8) e de diversos outros problemas.
Um grafo H é um menor40 (= minor), ou subcontração, de um grafo G se
VH é uma subpartição41 {V1 , . . . , Vp } de VG tal que
• cada subgrafo G[Vi ] é conexo e
• se Vi é adjacente a Vj em H então há uma aresta de Vi a Vj em G
(mas pode existir uma aresta de Vi a Vj em G sem que Vi seja adjacente a Vj
em H). A expressão “H é um menor de G” também é usada, num sentido
mais amplo, para dizer que H é isomorfo a um menor de G.
De maneira muito informal, podemos dizer que H é um menor de G se
H pode ser obtido a partir de um subgrafo de G por sucessivas operações
de “contração” de arestas. (A “contração” de uma aresta uv faz coincidir os
vértices u e v.)

Figura 1.10: O grafo à direita, H, é um menor do grafo à esquerda, G.

(Trata-se de um menor muito especial, pois V1 ∪ · · · ∪ Vp = VG .)

Um grafo H é um menor topológico (= topological minor) de um grafo G

se VH ⊆ VG e existe uma função P que associa um caminho em G a cada
aresta de H de tal modo que
• para cada aresta xy de H, o caminho P (xy) tem extremos x e y e não
tem vértices internos em VH e
• se xy e uv são duas arestas distintas de H então P (xy) e P (uv) não
têm vértices internos em comum.
40
Às vezes digo máinor, pois não me habituo a usar a palavra menor como substantivo.
41
Uma subpartição de um conjunto V é uma coleção {V1 , . . . , Vp } de subconjuntos não
vazios de V tal que Vi ∩ Vj = ∅ sempre que i 6= j.
FEOFILOFF Menores de grafos 51

A expressão “H é um menor topológico de G” também é usada, num sentido

mais amplo, para dizer que H é isomorfo a algum menor topológico de G.
Um menor topológico é um tipo especial de menor, embora isso não seja
imediatamente aparente. (Veja o exercício 1.250.)
Se H é um menor topológico de G, diz-se também que G contém uma
subdivisão de H porque é possível obter um subgrafo de G a partir de H
por meio de sucessivas operações de “subdivisão” de arestas. (Cada “sub-
divisão” de uma aresta introduz um novo vértice de grau 2 no “interior” da
aresta.)

Exercícios
◦ E 1.241 Seja H um subgrafo de um grafo G. Mostre que H é um menor
topológico de G.

◦ E 1.242 Seja H um subgrafo de um grafo G. Mostre que H é isomorfo a um

menor de G.

E 1.243 Mostre que um grafo G tem um menor topológico isomorfo a K3 se

e somente se G contém um circuito.

E 1.244 Mostre que um grafo G tem um menor isomorfo a K3 se e somente

se G contém um circuito.

E 1.245 Seja G o grafo do rei num tabuleiro 4-por-4. Seja u o vértice de

coordenadas (2, 2) e v o vértice de coordenadas (3, 3). Mostre que G + uv
não tem subgrafo isomorfo a K4 mas tem um menor topológico isomorfo
a K4 .

E 1.246 Seja G o grafo do rei num tabuleiro 5-por-5. Seja u o vértice de

coordenadas (2, 2) e v o vértice de coordenadas (4, 4). Mostre que G + uv
não tem subgrafo isomorfo a K4 mas tem um menor isomorfo a K4 .
Seja x o vértice de coordenadas (2, 4) e y o vértice de coordenadas (4, 2).
Mostre que G + uv + xy tem um menor isomorfo a K4 .

E 1.247 Mostre que o grafo de Petersen tem um menor isomorfo a K5 (mas

não tem subgrafo isomorfo a K5 nem menor topológico isomorfo a K5 ).

E 1.248 Mostre que o grafo de Petersen tem um menor topológico isomorfo

a K3,3 . Mostre que o grafo de Petersen tem um menor isomorfo a K3,3 .
 FEOFILOFF Menores de grafos 52

E 1.249 Mostre que K3,3 é isomorfo a um menor topológico do cubo Q4 .

Mostre que K5 é um menor topológico de Q4 .

? E 1.250 Mostre que se H é um menor topológico de G então H é isomorfo

a um menor de G. Mostre que a recíproca não é verdadeira.

? E 1.251 Seja H um menor de um grafo G. Suponha que ∆(H) ≤ 3. Prove

que H é isomorfo a um menor topológico de G. Dê um bom exemplo para
mostrar que a condição “∆(H) ≤ 3” é essencial.

HG E 1.252 Se H é (isomorfo a) um menor de G, escrevemos H  G. Mostre que

 é uma relação de ordem. Mais precisamente, mostre que
1. G  G,
2. se H  G e G  H então H ∼
= G,
3. se H  G e G  F então H  F .
Mostre também que a relação é-menor-topológico-de é uma relação de or-
dem.
FEOFILOFF Mapas planos e suas faces 53

1.17 Mapas planos e suas faces

Já dissemos na seção 1.6 que, grosso modo, um grafo é planar se pode
ser desenhado no plano42 sem que as arestas se cruzem. A definição exata
envolve os conceitos de linha e mapa plano, que passamos a discutir.
Uma linha é qualquer união finita de segmentos de reta no plano R2
que seja topologicamente homeomorfa ao intervalo fechado [0, 1] da reta. Em
outras palavras, uma união finita c de segmentos de reta é uma linha se existe
uma bijeção topologicamente contínua do intervalo [0, 1] em c. As imagens
de 0 e 1 sob essa bijeção contínua são os extremos da linha.43
Um mapa plano44 é um par (V, E) de conjuntos finitos, sendo V um V
conjunto de pontos do plano R2 e E um conjunto de linhas tal que E
• os extremos de cada linha são elementos de V,
• o interior de cada linha é disjunto de V,
• o interior de cada linha é disjunto de todas os demais linhas,
• duas linhas diferentes têm no máximo um extremo em comum.
Os elementos de V são os pontos45 do mapa e os de E são as linhas46 do pontos
mapa. linhas

Figura 1.11: O mapa da esquerda não é plano. O mapa

plano da direita representa um K4 .

O grafo de um mapa plano (V, E) é definido da maneira óbvia: o con- grafo de

junto de vértices do grafo é V e dois vértices v e w são adjacentes no grafo se mapa
existe uma linha em E com extremos v e w. (Será necessário tomar cuidado
com a notação, uma vez que a letra ”V” está sendo usada para designar
tanto o conjunto de pontos de um mapa plano quanto o conjunto de vértices
do correspondente grafo. Analogamente, a letra “E” está sendo usada para
designar tanto o conjunto de linhas de um mapa plano quanto o conjunto de
arestas do correspondente grafo.)

42
Do ponto de vista técnico, seria mais cômodo usar a superfície da esfera no lugar do
plano. Mas os resultados são equivalentes.
43
Por definição, os dois extremos são distintos.
44
Alguns autores dizem “grafo plano”. Não confunda esta expressão com “grafo planar”.
45
Prefiro não dizer “vértices” para evitar confusão com os vértices de um grafo.
46
Prefiro não dizer “arestas” para evitar confusão com as arestas de um grafo.
 FEOFILOFF Mapas planos e suas faces 54

mapa Dizemos que um mapa plano M representa um grafo G se o grafo de M

representa é isomorfo (veja capítulo 2) a G. Em geral, um grafo pode ser representado
grafo por muitos mapas planos diferentes.
Um grafo G é planar se for representável por um mapa plano, ou seja, se
existir um mapa plano cujo grafo é isomorfo a G. Esta é a versão precisa da
definição vaga que demos na seção 1.6.

Exercícios
E 1.253 Veja o “jogo de planaridade” em [Link].

E 1.254 O grafo de Petersen (veja figura 1.6) é planar?

E 1.255 Seja G um K5 (isto é, um grafo completo com 5 vértices). Mostre que

G − e é planar qualquer que seja a aresta e de G. Repita o exercício com K3,3
(veja figura 19.1) no lugar de K5 .

◦ E 1.256 Mostre que um grafo é planar se e somente se cada uma de suas

componentes é planar.

E 1.257 Seja e uma ponte de um grafo G. Mostre que G é planar se e somente

se G − e é planar.
Seja v uma articulação de G. Mostre que G é planar se e somente se G − v
é planar.

Faces e dualidade planar

S
O suporte de um mapa plano (V, E) é o conjunto V ∪ E (trata-se, obvia-
mente, de um subconjunto de R2 ).47 Em outras palavras, o suporte do mapa
é o conjunto de todos os pontos de R2 que são pontos do mapa ou pertencem
a linhas do mapa.
Uma face (= face) de um mapa plano (V, E) é qualquer região do com-
plemento do suporte do mapa, ou seja, qualquerS componente conexo — no
sentido topológico48 — do conjunto R2 r V ∪ E). A fronteira de cada
face é formada por linhas do mapa; o número de linhas na fronteira de uma
face F é o grau de F .
Seja G o grafo de um mapa plano M com 3 ou mais pontos. Se G é
aresta-biconexo então as faces de M são “bem comportadas”: cada face é
47
S
Se X = {X1 , X2 , . . . , Xk } então X denota o conjunto X1 ∪ X2 ∪ · · · ∪ Xk .
48
O conceito topológico de conexão é formalmente análogo ao conceito de conexão da
teoria dos grafos: um subconjunto X do plano é conexo se, para quaisquer pontos x e x0 em
X, existe uma linha com extremos em x e x0 cujos pontos estão todos em X.
FEOFILOFF Mapas planos e suas faces 55

topologicamente homeomorfa a um disco e cada linha pertence à fronteira

de duas faces diferentes. Se G é biconexo, as faces de M são ainda mais “bem
comportadas”: a fronteira de cada face corresponde a um circuito de G.
O grafo das faces, ou grafo dual, de um mapa plano M é definido da
seguinte maneira: os vértices do grafo são as faces do mapa e duas faces são
adjacentes se suas fronteiras têm pelo menos uma linha em comum.49 (Note
que o grafo dual é definido a partir de um mapa e não a partir do grafo
do mapa. Um grafo planar pode ser representado por vários mapas planos
diferentes,50 e cada um desses mapas tem o seu grafo dual.)
Um exemplo: o grafo dos estados do Brasil que examinamos no exercí-
cio 1.17 é o grafo dual do mapa do Brasil.

Exercícios
E 1.258 Seja M um mapa plano e suponha que o grafo do mapa é um cami-
nho. Mostre que M tem apenas uma face.
Seja M um mapa plano e suponha que o grafo do mapa é um circuito.
Mostre que M tem exatamente duas faces (e as duas faces têm a mesma
fronteira).

E 1.259 Mostre que um mapa plano tem uma e uma só face se e somente se
o grafo do mapa é uma floresta.

E 1.260 Considere um mapa plano que representa uma grade p-por-q. Quan-
tas faces tem o mapa?

E 1.261 Seja M um mapa plano que representa uma grade 3-por-4. Faça uma
figura do grafo das faces (ou seja, do grafo dual) de M.

E 1.262 Quantas faces tem um mapa plano que representa o cubo Q3 ?

E 1.263 Faça uma figura dos grafos das faces de cada um dos mapas planos
desenhados nas figuras 1.12 e 1.13.

E 1.264 Seja G um K5 e e uma aresta de G. Seja M um mapa plano que

representa G − e. Seja G∗ o grafo das faces (ou seja, o grafo dual) de M.
49
O estudo da dualidade planar fica mais “limpo” se a definição de grafo é liberalizada
para permitir “arestas paralelas” (ou seja, duas ou mais arestas diferentes com o mesmo par
de pontas) e “laços” (ou seja, uma aresta com duas pontas iguais). É claro que a definição de
mapa plano deve ser liberalizada de acordo. Prefiro não adotar essa liberalização no presente
texto. Para compensar, será necessário evitar ocasionalmente grafos que têm articulações ou
vértices de grau 2.
50
Mas veja o exercício 1.282.
FEOFILOFF Mapas planos e suas faces 56

Figura 1.12: Faça uma figura do grafo dual de cada um

dos mapas planos da figura.

Figura 1.13: Faça uma figura do grafo dual de cada um

dos mapas planos da figura.

Faça uma figura de G∗ . Verifique que G∗ é planar. Exiba uma representação

plana, digamos M∗ , de G∗ . Faça uma figura do grafo das faces de M∗ .

E 1.265 Dê um exemplo de um grafo conexo planar que possa ser represen-

tado por dois mapas planos com diferentes números de faces.

? E 1.266 (F ÓRMULA DE E ULER51 ) Seja (V, E) um mapa plano cujo grafo é

conexo. Mostre que
|V| − |E| + |F| = 2 , (1.3)
onde F é o conjunto de faces do mapa. (Verifique que a fórmula é falsa em
mapas cujos grafos não são conexos.) (Compare com o exercício 1.228.)

E 1.267 Seja G um grafo planar aresta-biconexo. Seja (V, E) um mapa plano

que
P representa G e seja F o conjunto das faces do mapa. Mostre que
F ∈F d(F ) = 2|E|, sendo d(F ) o grau da face F . (Compare com o exercí-
cio 1.42.)

? E 1.268 Seja G um grafo planar conexo com três ou mais vértices. Mostre
que
m(G) ≤ 3n(G) − 6 . (1.4)
51
Leonhard Euler ( − ). Veja verbete na Wikipedia.
FEOFILOFF Mapas planos e suas faces 57

(Sugestão: Faça uma indução no número de pontes.) Deduza daí que a de-
sigualdade vale para qualquer grafo planar que tenha três ou mais vértices.
Como são as faces de um mapa plano com n pontos e exatamente 3n − 6
linhas?

◦ E 1.269 É verdade que todo grafo G com m(G) ≤ 3n(G) − 6 é planar?

E 1.270 Deduza da desigualdade (1.4) que K5 não é planar.

E 1.271 Seja G um grafo aresta-biconexo planar. Suponha que a cintura (veja

capítulo 14) de G não é inferior a 4. Mostre que m(G) ≤ 2n(G) − 4. (Compare
com o exercício 1.268.) Deduza daí que K3,3 não é planar. Deduza daí que Q4
não é planar.

E 1.272 Seja G um grafo bipartido com três ou mais vértices. Mostre que se
G é planar então m(G) ≤ 2n(G) − 4. (Veja o exercício 1.271.)

E 1.273 Seja G um grafo {U, W }-bipartido. Mostre que se G é planar então

m(G) ≤ 2|U | + 2|W | − 4.

E 1.274 Seja G um grafo e k um número natural não inferior a 3. Suponha que

G tem pelo menos 21 (k + 2) vértices e cintura não inferior a k. Mostre que se G
é planar então m(G) ≤ (n(G) − 2)k/(k − 2). (Compare com o exercício 1.271.)

? E 1.275 Mostre que todo grafo planar tem pelo menos um vértice de grau
não superior a 5. Em outras palavras, mostre que δ(G) ≤ 5 para todo grafo
planar G.
Dê exemplo de um grafo planar que não contém vértices de grau menor
que 5.

E 1.276 Seja G um grafo bipartido planar. Mostre que δ(G) ≤ 3.

◦ E 1.277 Um mapa plano “do tipo (n, m, d, g)” é um mapa plano com n pon-
tos e m linhas cujos pontos têm grau d e cujas faces têm grau g. Exiba um
mapa plano do tipo (4, 6, 3, 3). Exiba um mapa plano do tipo (6, 12, 4, 3).
Exiba um mapa plano do tipo (8, 12, 3, 4).

◦ E 1.278 Seja G um grafo cúbico biconexo com 10 vértices. Mostre que G

não pode ser representado por um mapa plano cujas faces tenham todas o
mesmo grau.

E 1.279 Seja G um grafo com 11 ou mais vértices. Mostre que G e o seu

complemento G não podem ser ambos planares.
FEOFILOFF Mapas planos e suas faces 58

E 1.280 Um mapa plano é auto-dual (= self-dual) se o seu grafo for isomorfo

ao seu grafo dual. Mostre que se (V, E) é auto-dual então 2|V| = |E| + 2.
Mostre que nem todo mapa plano (V, E) tal que 2|V| = |E| + 2 é auto-dual.

? E 1.281 Seja G o grafo de um mapa plano M. Suponha que G é biconexo

e não tem vértices de grau 2 (ou seja, δ(G) ≥ 3). Seja G∗ o grafo das faces
(isto é, o grafo dual) do mapa M. Mostre que G∗ é planar.
Seja M∗ um mapa plano que representa G∗ . Seja G∗∗ o grafo das faces
de M∗ . Mostre que G∗∗ ∼ = G, ou seja, que G∗∗ é isomorfo a G.

! E 1.282 (T EOREMA DE W HITNEY) Todo grafo planar 3-conexo (veja pá-

gina 133) tem essencialmente um único mapa plano. O “essencialmente”
significa que todos os mapas planos são equivalentes. Dois mapas de um
mesmo grafo são equivalentes se o conjunto de arestas das fronteiras de faces
correspondentes são iguais.

E 1.283 (E XOPLANAR) Um mapa plano M é exoplano se seus pontos es-

tiverem todos na fronteira de uma mesma face. Um grafo G é exoplanar
(= outerplanar) (há que diga periplanar, embora os químicos usem a palavra
em outro sentido) se for representável por um mapa exoplano.
Mostre que K4 não é exoplanar. Mostre que K2,3 não é exoplanar.

E 1.284 Mostre que o grafo dual de um mapa exoplano (veja exercício 1.283)
pode não ser planar.

E 1.285 Seja M um mapa exoplano (veja o exercício 1.283). Seja F a face cuja
fronteira contém todos os pontos de M. Seja G∗ o grafo das faces (isto é, o
grafo dual) de M. Mostre que G∗ − F é uma árvore.

E 1.286 Seja e uma aresta de um grafo exoplanar G (veja exercício 1.283). É

verdade que existe um mapa exoplano de G em que a representação de e
pertence à fronteira da face que contém todos os vértices?
FEOFILOFF Grafos aleatórios 59

1.18 Grafos aleatórios

Seja V o conjunto {1, . . . , n} e seja G(n) a coleção52 de todos os grafos com V
conjunto de vértices V . É claro que G(n)

|G(n)| = 2N , com N := n2 .

Qualquer propriedade de grafos (como, por exemplo, a propriedade de ser N

conexo)53 define uma subcoleção de G(n). Assim, convém confundir os
conceitos de “propriedade” e “subcoleção” de G(n). Diremos que quase todo
grafo tem determinada propriedade P(n) se

|P(n)|
lim = 1.
n→∞ |G(n)|

Uma maneira de estudar o conjunto G(n) é baseada na introdução de uma

medida de probabilidade nesse conjunto. Seja p um número no intervalo
(0, 1) e escolha cada elemento de V (2) , independentemente, com probabili-
dade p. (Veja exercício 1.20.) Se A é o conjunto dos pares escolhidos, então
(V, A) é um grafo aleatório em G(n). A probabilidade de que o grafo (V, A)
assim construído seja idêntico a um determinado elemento de G(n) que tenha
m arestas é
pm (1 − p)N −m .
Se p = 21 então todos os 2N grafos em G(n) são equiprováveis: a probabilidade
de obter qualquer um deles é 1/2N .

Exercícios
◦ E 1.287 Mostre que quase todo grafo em G(n) tem mais que 10000 arestas.

E 1.288 Prove que quase todo grafo G em G(n) é conexo. (Veja a seção 1.18.)

52
“Coleção” é o mesmo que “conjunto”.
53
Naturalmente, só estamos interessados em propriedades invariantes sob isomorfismo
(veja o capítulo 2).
FEOFILOFF Grafos aleatórios 60
Capítulo 2

Isomorfismo

Dois grafos são isomorfos se têm a mesma “estrutura”. A definição exata do

conceito é um pouco trabalhosa, como veremos a seguir.
Um isomorfismo (= isomorphism) entre dois grafos G e H é uma bijeção1
f de VG em VH tal que, para todo par (v, w) de elementos de VG , v e w são
adjacentes em G se e somente se f (v) e f (w) são adjacentes em H.
Dois grafos G e H são isomorfos (= isomorphic) se existe um isomorfismo
entre eles. Em outras palavras, dois grafos são isomorfos se é possível alterar
os nomes dos vértices de um deles de tal modo que os dois grafos fiquem
iguais. A expressão “G ∼= H” é uma abreviatura de “G é isomorfo a H”. ∼
=

P ROBLEMA DO I SOMORFISMO: Decidir se dois grafos dados são iso-

morfos.

Exercícios
E 2.1 Um grafo G tem conjunto de vértices {a, b, c, d} e conjunto de arestas
{ab, bc, cd, da}. Um grafo H tem conjunto de vértices {a, b, c, d} e conjunto de
arestas {ab, bd, dc, ca}. Os grafos G e H são iguais?

E 2.2 Os grafos G e H descritos a seguir são isomorfos?

VG = {a, b, c, d, e, f, g} EG = {ab, bc, cd, cf, f e, gf, ga, gb}
VH = {h, i, j, k, l, m, n} EH = {hk, nj, jk, lk, lm, li, ij, in}
E se trocarmos hk por hn em EH ?

E 2.3 Os grafos da figura 2.1 são isomorfos?

1
Uma bijeção é uma função f de um conjunto A em um conjunto B tal que (1) f (a) 6=
f (a0 ) sempre que a 6= a0 e (2) para todo b em B existe a em A tal que b = f (a).

61
FEOFILOFF Isomorfismo 62

Figura 2.1: Os grafos da figura são isomorfos?

E 2.4 Mostre que dois caminhos são isomorfos se e somente se têm o mesmo
comprimento. Mostre que dois circuitos são isomorfos se e somente se têm o
mesmo comprimento.

E 2.5 Faça uma lista de todos os grafos sobre o conjunto de vértices {1, 2, 3, 4}
que sejam dois a dois não isomorfos. (Em outras palavras, faça a lista modo
que todo grafo com 4 vértices seja isomorfo a um e apenas um dos grafos da
lista.)

E 2.6 Para n = 1, 2, 3, . . . , faça uma lista de todas as árvores sobre o conjunto

de vértices {1, 2, 3, . . . , n} que sejam duas a duas não isomorfas.

E 2.7 Os grafos da figura 2.2 são isomorfos dois a dois?

Figura 2.2: Esses grafos são dois a dois isomorfos?

E 2.8 Os grafos da figura 2.3 são isomorfos? Justifique.

Figura 2.3: Os grafos da figura são isomorfos?

FEOFILOFF Isomorfismo 63

E 2.9 Os grafos da figura 2.4 são isomorfos? Justifique.

. .

Figura 2.4: Esses grafos são isomorfos?

E 2.10 Seja G a grade 3-por-4 e H a grade 4-por-3 (veja exercício 1.6). Os

grafos G e H são iguais? são isomorfos?

E 2.11 Mostre que a grade p-por-q e o grafo definido no exercício 1.7 são
isomorfos.

E 2.12 Mostre que o cubo Q3 é isomorfo a algum subgrafo do Q4 .

E 2.13 Mostre que o cubo Q4 tem um subgrafo isomorfo à grade 4-por-4.

E 2.14 Para quais valores de t os dois componentes do grafo do bispo t-por-t

são isomorfos?

D 2.15 Caracterize os grafos que são isomorfos a um subgrafo do Qk .

E 2.16 Suponha que os grafos G e H são isomorfos. Mostre que n(G) = n(H)
e m(G) = m(H). Mostre que para qualquer isomorfismo f de G em H tem-se
dG (v) = dH (f (v)) para todo v em VG . Mostre que se G tem um circuito de
comprimento k então H também tem um circuito de comprimento k.

E 2.17 (A LGORITMO) O seguinte algoritmo se propõe a decidir se dois gra-

fos, G e H, são isomorfos:
examine todas as bijeções de VG em VH ;
se alguma delas for um isomorfismo, então G é isomorfo a H;
caso contrário, G e H não são isomorfos.
Discuta o algoritmo.

E 2.18 (A LGORITMO) O seguinte algoritmo se propõe a decidir se dois gra-

fos, G e H, são isomorfos:
se n(G) 6= n(H) então G e H não são isomorfos;
se m(G) 6= m(H) então G e H não são isomorfos;
se |{ v ∈ VG : dG (v) = i }| =
6 |{ v ∈ VH : dH (v) = i }| para algum i
FEOFILOFF Isomorfismo 64

então G e H não são isomorfos;

em todos os demais casos, G é isomorfo a H.
Discuta o algoritmo.

E 2.19 Sejam G e H dois grafos e f uma bijeção de VG em VH tal que dG (v) =

dH (f (v)) para todo v em VG . É verdade que G ∼
= H?

◦ E 2.20 Certo ou errado? Para mostrar que dois grafos G e H com mesmo
número de vértices não são isomorfos basta exibir uma bijeção f de VG em
VH e um par de vértices u e v em VG tal que (1) uv ∈ EG mas f (u)f (v) ∈
/ EH
ou (2) uv ∈
/ EG mas f (u)f (v) ∈ EH .

E 2.21 Seja A o conjunto de todos grafos que representam os alcanos que têm
fórmula C4 H10 . (Veja exercício 1.5.) Cada um desses alcanos tem 4 vértices
de grau 4 e 10 vértices de grau 1. Quantos grafos dois-a-dois não isomorfos
há em A?

E 2.22 Mostre que o grafo das arestas (veja o exercício 1.24) de um K5 é

isomorfo ao complemento do grafo de Petersen.

E 2.23 É verdade que todo grafo é isomorfo ao grafo das arestas (veja exercí-
cio 1.24) de algum outro grafo?

E 2.24 Seja X um conjunto de vértices de um grafo G. Suponha que o sub-

grafo induzido G[X] é uma estrela (veja a seção 1.2) com 4 vértices. Mostre
que G não é isomorfo ao grafo das arestas (veja exercício 1.24) de outro grafo,
ou seja, que não existe grafo H tal que G ∼
= L(H).

E 2.25 Seja G o grafo de Petersen. Dados quaisquer dois vértices u e v de G,

mostre que existe um isomorfismo de G em G (isomorfismos desse tipo são
conhecidos como automorfismos) que leva u em v. Dadas quaisquer duas
arestas uv e xy de G, mostre que existe um isomorfismo de G em G que leva
uv em xy (ou seja, leva u em x e v em y ou leva u em y e v em x).

E 2.26 Um grafo é auto-complementar se for isomorfo ao seu complemento.

Mostre que se G é um grafo auto-complementar então n(G) = 0 (mod 4) ou
n(G) = 1 (mod 4).2
2
A expressão “x = i (mod 4)” significa que o resto da divisão de x por 4 e o resto da
divisão de i por 4 são iguais, ou seja, que x mod 4 = i mod 4. Em outras palavras, x − i é
divisível por 4.
FEOFILOFF Isomorfismo 65

D 2.27 Encontre uma caracterização eficiente de grafos não isomorfos. Em

outras palavras, encontre uma propriedade X que seja fácil de verificar e que
torne verdadeira a seguinte afirmação: “Dois grafos G e H não são isomorfos
se e somente se X ”.

D 2.28 (A LGORITMO) Esboce um algoritmo rápido que resolva o problema

do isomorfismo (isto é, decida se dois grafos dados são isomorfos).
FEOFILOFF Isomorfismo 66
Capítulo 3

Síntese de grafos com graus dados

Um grafo G realiza uma sequência (g1 , g2 , . . . , gn ) de números naturais1 se os

vértices do grafo são 1, 2, . . . , n e d(i) = gi para todo i.
Uma sequência (g1 , g2 , . . . , gn ) de números naturais é gráfica se existe um sequência
grafo que a realize. gráfica

P ROBLEMA DA S ÍNTESE: Dada uma sequência de números naturais,

decidir se ela é ou não gráfica.

Esse problema é às vezes chamado de graph design problem.

Exercícios
E 3.1 Considere as sequências (2, 2, 0), (1, 1, 2, 2), (0, 3, 1, 0), (0, 1, 2, 2, 3),
(3, 3, 2, 2, 1), (6, 6, 5, 4, 3, 3, 1) e (7, 6, 5, 4, 3, 3, 2). Quais delas são gráficas?

g2 , . . . , gn ) é uma sequência gráfica. Mostre que gi ≤

E 3.2 Suponha que (g1 ,P
n − 1 para todo i e que gi é par. Formule a recíproca; ela é verdadeira?

E 3.3 Mostre que uma sequência (g1 , g2 , . . . , gn ) é gráfica se e somente se

a sequência (n−g1 −1, n−g2 −1, . . . , n−gn −1) é gráfica. (Este fato pode ser
usado como base de um algoritmo que reconhece sequências gráficas.)

E 3.4 Prove que, para cada n ≥ 5, existe um grafo 4-regular com n vértices.

E 3.5 É verdade que para cada número r existe um grafo r-regular? É

verdade que para cada par (r, n) de números tal que r < n existe um grafo
r-regular com n vértices?
1
O conjunto dos números naturais é {0, 1, 2, . . .}.

67
FEOFILOFF Síntese de grafos com graus dados 68

E 3.6 Suponha que (g1 , g2 , . . . , gn ) é uma sequência gráfica e k é um número

natural ≤ n. Mostre que a sequência

(k, g1 +1, g2 +1, . . . , gk +1, gk+1 , . . . , gn )

também é gráfica. Formule a recíproca deste fato; ela é verdadeira?

? E 3.7 (T EOREMA H AVEL E H AKIMI2 ) Seja (k, g1 , g2 , . . . , gn ) uma se-

DE
quência de números naturais tal que k ≥ g1 ≥ g2 ≥ . . . ≥ gn . Suponha
que a sequência

(g1 − 1, g2 − 1, . . . , gk − 1, gk+1 , . . . , gn )

é gráfica. Mostre que a primeira sequência também é gráfica.

? E 3.8 (T EOREMA DE E RD ŐS3 E G ALLAI4 ) Mostre que P uma sequência

(g1 , g2 , . . . , gn ) de números naturais é gráfica se e somente se i gi é par e
k
X n
X
gi ≤ k(k − 1) + min (k, gi )
i=1 i=k+1

para cada k tal que 1 ≤ k ≤ n.

E 3.9 (A LGORITMO) Esboce um algoritmo eficiente que resolva o problema

de síntese enunciado acima, ou seja, decida se uma dada sequência de nú-
meros naturais é gráfica. Busque inspiração nos exercícios 3.6 e 3.7 ou no
exercício 3.8.

E 3.10 Sejam g1 , . . . , gn números inteiros positivos. Suponha que ni=1 gi =

P
2(n − 1). Mostre que existe uma árvore (veja seção 1.15) T com vértices 1,
. . . , n tal que d(i) = gi para cada i.

2
Publicado em 1955 por Václav Havel e em 1962 por S. Louis Hakimi.
3
Paul Erdős ( − ). (Veja verbete na Wikipedia.)
4
Tibor Gallai ( − ).
Capítulo 4

Grafos bicoloráveis

Uma bicoloração de um grafo G é uma bipartição1 {U, W } de VG tal que toda

aresta de G tem uma ponta em U e outra em W . (Você pode imaginar que
todos os vértices em U são vermelhos e todos os vértices em W são azuis.) Por
exemplo, todo grafo bipartido (veja seção 1.2) tem uma bicoloração óbvia.

P ROBLEMA DA B ICOLORAÇÃO: Encontrar uma bicoloração de um

grafo dado.

Faz parte do problema decidir se o grafo dado admite2 bicoloração.3

Diremos que um grafo é bicolorável se admite bicoloração. Portanto, um
grafo bicolorável é o mesmo que um grafo bipartido.4
Como veremos adiante (exercício 4.15), um grafo é bicolorável se e so-
mente se não contém circuito ímpar. Dizemos que um circuito é ímpar se seu
comprimento é um número ímpar.

Exercícios
? E 4.1 Mostre que um grafo G é bicolorável se e somente se EG é um corte.

E 4.2 Mostre que o grafo do cavalo t-por-t é bicolorável.

1
Uma bipartição de um conjunto V é um par {U, W } de subconjuntos não vazios de V
tal que U ∪ W = V e U ∩ W = ∅. A bipartição é o par {U, W }; não faz sentido dizer “U é
uma das bipartições de V ”. Diga “U é um dos elementos da bipartição”.
2
A expressão “admite bicoloração” significa o mesmo que “tem uma bicoloração”.
3
Muitos problemas na teoria dos grafos são do tipo “mostre que este grafo não tem
a propriedade X.” No presente caso, a questão é “mostre que este grafo grafo não admite
bicoloração.” A resposta “tente todas as possíveis bipartições de VG ” não é satisfatória, pois o
número de bipartições é enorme: um conjunto de tamanho n tem 2n−1 diferentes bipartições.
4
Na verdade, há uma sutil distinção entre os dois conceitos: um grafo bicolorável só se
torna bipartido depois que uma de suas bicolorações for explicitamente dada.

69
FEOFILOFF Grafos bicoloráveis 70

E 4.3 É verdade que o grafo do bispo t-por-t é bicolorável?

E 4.4 Mostre que todo cubo Qk é bicolorável.

E 4.5 Mostre que toda grade é bicolorável.

◦ E 4.6 Mostre que todo caminho é bicolorável. Mostre que todo circuito de
comprimento par é bicolorável.

E 4.7 Mostre que um grafo pode ter duas ou mais bicolorações diferentes.
Mostre que grafos conexos têm no máximo uma bicoloração.

. E 4.8 Mostre que toda floresta é bicolorável.

E 4.9 Seja {U, W } uma bicoloração de uma floresta tal que |U | = |W |. Mostre
que a floresta tem pelo menos uma folha em U e uma em W .

◦ E 4.10 Suponha que um grafo G é bicolorável. É verdade que todo subgrafo

de G é bicolorável? É verdade que todo subgrafo induzido de G é bicolorá-
vel?

E 4.11 Os grafos da figura 4.1 são bicoloráveis?

Figura 4.1: Exercício 4.11. Esses grafos são bicoloráveis?

E 4.12 ♥ Quantas arestas pode ter um grafo bicolorável com n vértices?

◦ E 4.13 Suponha que um grafo G tem um circuito ímpar. Mostre que G não
é bicolorável.

? E 4.14 Mostre que todo grafo sem circuitos ímpares é bicolorável.5

5
Portanto, um circuito ímpar é um certificado da inexistência de bicoloração do grafo.
Reciprocamente, uma bicoloração do grafo é um certificado da ausência de circuitos ímpa-
res.
FEOFILOFF Grafos bicoloráveis 71

? E 4.15 (S OLUÇÃO DO PROBLEMA DA BICOLORAÇÃO) Deduza de 4.13

e 4.14 que um grafo é bicolorável se e somente se não tem circuitos ímpares.

E 4.16 Dizemos que um grafo G tem um circuito induzido se existe X ⊆ VG

tal que G[X] é um circuito. Mostre que um grafo é bicolorável se e somente
se não tem circuitos ímpares induzidos.

E 4.17 (A LGORITMO) Construa um algoritmo eficiente que decida se um

grafo dado é bicolorável. O algoritmo deve devolver uma bicoloração do
grafo ou um circuito ímpar.

E 4.18 (C AMINHO PAR / ÍMPAR) Seja G um grafo biconexo. Sejam r e s dois

vértices de G. Existe um caminho de comprimento par de r a s e um caminho
de comprimento ímpar de r a s (os dois caminhos não são necessariamente
disjuntos) se e somente se G não é bicolorável.

E 4.19 (C IRCUITO ÍMPAR) Seja G um grafo biconexo e suponha que G tem

um circuito de comprimento ímpar. Mostre que todo vértice de G faz parte
de um circuito de comprimento ímpar.

Caracterização de cortes
E 4.20 Caracterize os conjuntos de arestas de um grafo que são cortes, ou
seja, estabeleça as condições em que um conjunto de arestas de um grafo é
um corte.

E 4.21 (A LGORITMO) Esboce um algoritmo eficiente que execute a seguinte

tarefa: Dado um grafo G e um subconjunto C de EG , o algoritmo decide se
C é ou não um corte. Em caso afirmativo, o algoritmo deve devolver um
conjunto X de vértices tal que ∂(X) = C. Que coisa o seu algoritmo deve
devolver em caso negativo?

E 4.22 Seja D um corte e O um circuito em um grafo. Mostre que |D ∩ EO | é

par.

E 4.23 (Recíproca de 4.22.) Seja D um conjunto de arestas de um grafo G.

Suponha que |D ∩ EO | é par para todo circuito O em G. Mostre que D é um
corte.

E 4.24 Seja D um corte e P um caminho em um grafo G. O que se pode dizer

sobre a paridade de |D ∩ EP |?
FEOFILOFF Grafos bicoloráveis 72

E 4.25 Digamos que um grafo-com-sinais é um terno (G, P, N ) em que G é um

grafo e (P, N ) é uma partição do conjunto EG . As arestas em P são positivas
e as outras são negativas. Um grafo-com-sinais (G, P, N ) é equilibrado se todo
circuito em G tem um número par de arestas negativas. Prove que um grafo-
com-sinais (G, P, N ) é equilibrado se e somente se existe uma bipartição
{U, W } de VG tal que ∂(U ) = N .
Capítulo 5

Conjuntos estáveis

Um conjunto X de vértices de um grafo é estável (= stable = independent) se

seus elementos são dois a dois não adjacentes. Em outras palavras X é estável
se nenhuma aresta do grafo tem ambas as pontas em X, ou seja, se o grafo
induzido G[X] é vazio. Por exemplo, se {U, W } é uma bicoloração do grafo
então os conjuntos U e W são estáveis.
Um conjunto estável X ∗ é máximo se não existe conjunto estável X tal máximo
que |X| > |X ∗ |. Em outras palavras, X ∗ é máximo se |X ∗ | ≥ |X| para todo
conjunto estável X.

P ROBLEMA DO C ONJUNTO E STÁVEL M ÁXIMO: Encontrar um conjunto

estável máximo num grafo dado.

É importante não confundir máximo com maximal. Um conjunto estável

0
X é maximal se não faz parte de um conjunto estável maior, ou seja, se não maximal
existe conjunto estável X tal que X ⊃ X 0 .1
Eis uma variante do problema: Dado um grafo e um número natural k,
encontrar um conjunto estável com k ou mais vértices. (É claro que essa
variante nem sempre tem solução.)
O tamanho de um conjunto estável máximo em um grafo G é denotado
por
α(G) .
Em inglês, esse parâmetro é conhecido como stability number ou independence
number. Quem sabe deveríamos chamar α de índice de estabilidade do
grafo.

1
A expressão “A ⊃ B” significa “B é subconjunto próprio de A”, ou seja, B ⊆ A mas
B 6= A.

73
FEOFILOFF Conjuntos estáveis 74

Exercícios
E 5.1 Mostre que o índice de estabilidade é invariante sob isomorfismo. Em
outras palavras, se G e H são grafos isomorfos então α(G) = α(H).

◦ E 5.2 Encontre um conjunto estável máximo em um Kn . Encontre um

conjunto estável máximo em um Kn .

E 5.3 No grafo da figura 5.1, exiba um conjunto estável maximal que não seja
máximo.

Figura 5.1: Veja exercício 5.3.

◦ E 5.4 Suponha que X e Y são conjuntos estáveis maximais de um grafo. É

verdade que X e Y são disjuntos (ou seja, que X ∩ Y = ∅)?

◦ E 5.5 Calcule um conjunto estável máximo em um caminho. Calcule um

conjunto estável máximo em um circuito.

E 5.6 Encontre um conjunto estável máximo na grade p-por-q.

E 5.7 Exiba um conjunto estável máximo no cubo Qk .

E 5.8 Encontre um conjunto estável máximo no grafo do cavalo.

E 5.9 Encontre um conjunto estável máximo no grafo do bispo.

E 5.10 Encontre um conjunto estável máximo no grafo da dama. (Em outras

palavras, disponha o maior número possível de damas no tabuleiro de modo
que elas não se ataquem mutuamente.)

E 5.11 Encontre um conjunto estável máximo no grafo de Petersen.

E 5.12 Encontre um conjunto estável máximo no grafo de Kneser K(n, k)

(veja exercício 1.16).

E 5.13 Encontre um conjunto estável máximo no grafo dos estados do Brasil

(veja exercício 1.17).
FEOFILOFF Conjuntos estáveis 75

? E 5.14 Seja G um grafo bicolorável com bicoloração {U, W } e suponha que

|U | ≥ |W |. É verdade que U é um conjunto estável máximo?

E 5.15 Suponha que um grafo G admite bicoloração. É verdade que todo

conjunto estável maximal de G é máximo? E se G for uma árvore?

◦ E 5.16 Seja H um subgrafo de um grafo G. Qual a relação entre α(H)

e α(G)?

◦ E 5.17 Sejam G e H dois grafos tais que VG ∩VH = ∅. Mostre que α(G∪H) =
α(G) + α(H).

◦ E 5.18 Seja A a matriz de adjacências de um grafo G (veja exercício 1.3). Seja

X um conjunto estável de G. Que aparência tem a restrição de A a X × X?

E 5.19 (A LGORITMO) Discuta o seguinte algoritmo para o problema do con-

junto estável máximo:
dado um grafo G, examine cada um dos subconjuntos de VG ;
descarte os subconjuntos que não forem estáveis;
escolha o maior dos que sobrarem.

D 5.20 (A LGORITMO) Invente um algoritmo rápido que resolva o problema

do conjunto estável máximo. Invente, pelo menos, um algoritmo que pro-
duza um conjunto estável grande.

◦ E 5.21 (A LGORITMO) Construa um algoritmo que encontre um conjunto

estável maximal em qualquer grafo dado. (Sugestão: use uma estratégia
“gulosa”: em cada iteração, escolha qualquer vértice que seja razoável.2 )

E 5.22 (A LGORITMO) O seguinte algoritmo guloso (= greedy) recebe um

grafo G e devolve um conjunto estável X:
X←∅
H←G
enquanto VH 6= ∅ faça
escolha v em VH de modo que |NH (v)| seja mínimo
X ← X ∪ {v}
Z ← {v} ∪ NH (v)
H ←H −Z
devolva X
2
De um modo geral, algoritmos gulosos abocanham o objeto que lhes parece mais
saboroso na iteração corrente, sem medir as consequências que essa escolha terá a longo
prazo.
 FEOFILOFF Conjuntos estáveis 76

É verdade que esse algoritmo devolve um conjunto estável máximo para

qualquer grafo G dado? E se G for bipartido? E se G for uma árvore?

E 5.23 ♥ Prove que todo conjunto estável maximal de qualquer grafo G tem
pelo menos
l n(G) m
∆(G) + 1
n(G)
vértices.3 Deduza daí que α(G) ≥ ∆(G)+1
para todo grafo G.

E 5.24 ♥ Prove que todo grafo G satisfaz a desigualdade

X 1
α(G) ≥ .
v∈VG
d(v) + 1
P 1 
Ou seja, prove que G tem um conjunto estável com d(v)+1
vértices.

E 5.25 Seja Gt o grafo da dama t-por-t. Estime α(Gt ) usando o exercício 5.24.

E 5.26 Seja X o conjunto

P estável produzido pelo algoritmo do exercício 5.22.
Mostre que |X| ≥ v∈VG 1/(d(v) + 1).

E 5.27 Prove que todo grafo G satisfaz a desigualdade

n
α(G) ≥ ,
µ+1
sendo n o número de vértices, m o número de arestas, e µ a média dos graus
dos vértices de G.

E 5.28 Digamos que uma cobertura-por-caminhos de um grafo G é uma coleção

{P1 , . . . , Pk } de caminhos em G tal que VP1 ∪· · ·∪VPk = VG . Suponha que toda
cobertura-por-caminhos de um grafo G tem pelo menos k caminhos. Mostre
que α(G) ≥ k. Em outras palavras, mostre que G tem um conjunto estável
com pelo menos k vértices.

E 5.29 (A LGORITMO) Esboce um algoritmo eficiente que receba um grafo

bipartido e devolva um conjunto estável máximo.4

α≤ E 5.30 Seja G um grafo sem vértices isolados. Mostre que

α(G) ≤ m(G)/δ(G) .
Em outras palavras, mostre que G não tem conjuntos estáveis com mais que
bm(G)/δ(G)c vértices.5
3
Por definição, dxe é o único inteiro j tal que j − 1 < x ≤ j.
4
Discutiremos esse algoritmo em detalhe no capítulo 10.
5
Por definição, bxc é o único inteiro i tal que i ≤ x < i + 1.
FEOFILOFF Conjuntos estáveis 77

E 5.31 Sejam n e a dois inteiros positivos. Seja k = bn/ac e r = n − ka. Seja H

o grafo que resulta da união de r cópias do Kk+1 e a − r cópias do Kk (os
conjuntos de vértices das cópias são dois a dois disjuntos). Observe que

n(H) = n, m(H) = r k+1 k

2
+ (a − r) 2
e α(H) = a .

Mostre que α(G) > α(H) para qualquer grafo G tal que n(G) = n e m(G) <
m(H).6

Grafos aleatórios
E 5.32 Mostre que o índice de estabilidade da maioria dos grafos não passa
de pouco mais que 2 log2 n(G). Mais precisamente, mostre que para qualquer
número real positivo ε tem-se

α(G) < (2 + ε) log2 n

para quase todo grafo G em G(n). (Veja a seção 1.18.)

6
Pode-se provar que H é o único grafo (a menos de isomorfismo) com n vértices,
m(H) arestas e índice de estabilidade a. Este fato é um conhecido teorema de Paul Turán
( − ). (Veja verbete na Wikipedia.) O complemento de H é conhecido como grafo
de Turán.
FEOFILOFF Conjuntos estáveis 78
Capítulo 6

Cliques

Uma clique1 (= clique) ou conjunto completo num grafo é qualquer conjunto

de vértices dois a dois adjacentes. Em outras palavras X é uma clique se o
grafo induzido G[X] é completo.

P ROBLEMA DA C LIQUE M ÁXIMA: Encontrar uma clique máxima num

grafo dado.

Eis uma variante do problema: dado um grafo e um número natural k,

encontrar uma clique com k ou mais vértices.
O tamanho de uma clique máxima de um grafo G é denotado por

ω(G) .

Em inglês, esse parâmetro é conhecido como clique number.

Exercícios
◦ E 6.1 Encontre uma clique máxima em um Kn . Encontre uma clique má-
xima em um Kn .

◦ E 6.2 Encontre uma clique máxima em um caminho. Encontre uma clique

máxima em um circuito.

E 6.3 Seja G um circuito de comprimento 6. Encontre uma clique máxima no

grafo G.
1
A palavra clique é um neologismo importado do inglês. A palavra denota uma
“panelinha” ou um grupo fechado de pessoas que se conhecem entre si. Nesse contexto,
a palavra não tem qualquer relação com “estalido” e com expressões como “dê um clique
com o botão esquerdo do mouse”.

79
FEOFILOFF Cliques 80

E 6.4 Exiba um grafo e uma clique que seja maximal mas não máxima.

E 6.5 Encontre uma clique máxima no grafo do cavalo.

E 6.6 Exiba uma clique máxima no cubo Qk .

◦ E 6.7 Suponha que G é um grafo bipartido. Quantos vértices tem uma

clique máxima em G?

E 6.8 Encontre uma clique máxima no grafo do bispo.

E 6.9 Encontre uma clique máxima no grafo da dama.

E 6.10 Mostre que toda clique maximal do grafo de Kneser K(n, k) (veja
exercício 1.16) tem bn/kc vértices. Exiba uma clique máxima em K(n, k).

E 6.11 Qual a relação entre o problema da clique máxima e o problema

do conjunto estável máximo (veja capítulo 5)? Como é possível usar um
algoritmo que resolve um desses problemas para resolver o outro?

◦ E 6.12 Prove que ω(G) ≤ ∆(G) + 1 para todo grafo G.

E 6.13 Prove que a seguinte relação vale para qualquer conjunto X de vérti-
ces de um grafo G: X é uma clique em G se e somente se X é um conjunto
estável em G. Deduza daí que ω(G) = α(G).

E 6.14 Suponha que um grafo G tem a seguinte propriedade: para cada

vértice v, o conjunto N(v) é uma clique. Mostre que cada componente de
G é uma clique.

E 6.15 Mostre que ω(G) ≥ 3 para todo grafo G com mais que n(G)2 /4 arestas.
(Veja exercício 4.12.)

E 6.16 Suponha que ω(G) ≤ k. Quantas arestas G pode ter no máximo (em
relação ao número de vértices)?

E 6.17 É verdade que toda clique maximal em uma árvore é máxima?

◦ E 6.18 (A LGORITMO) Construa um algoritmo que encontre uma clique

maximal em qualquer grafo dado.
FEOFILOFF Cliques 81

D 6.19 (A LGORITMO) Invente um algoritmo rápido que resolva o problema

da clique máxima. Invente, pelo menos, um algoritmo que encontre uma
clique grande em qualquer grafo dado.

E 6.20 Seja L(G) o grafo das arestas (veja exercício 1.24) de um grafo G.
Mostre que para cada vértice v de G, o conjunto ∂G (v) é uma clique em L(G).
Mostre que o conjunto das arestas de qualquer triângulo em G é uma cli-
que em L(G). Mostre que qualquer clique em L(G) cuja cardinalidade seja
diferente de 3 é subconjunto de algum conjunto da forma ∂G (v).

E 6.21 Dado um grafo G, calcule uma clique máxima no grafo das ares-
tas L(G). (Veja exercício 6.20.)

E 6.22 Mostre que um grafo H é isomorfo ao grafo das arestas (veja exercí-
cio 1.24) de um outro grafo G se e somente se existe uma coleção de cliques
de H tal que cada aresta de H tem ambas as pontas em uma e apenas uma
das cliques e todo vértice de H pertence a no máximo duas das cliques.

E 6.23 Seja G um grafo planar (veja seção 1.6). Mostre que ω(G) ≤ 4.
FEOFILOFF Cliques 82
Capítulo 7

Cobertura por vértices

Uma cobertura por vértices1 (= vertex cover), ou simplesmente cobertura, de

um grafo é qualquer conjunto de vértices que contenha pelo menos uma das
pontas de cada aresta. Em outras palavras, um conjunto X de vértices é uma
cobertura se toda aresta tem pelo menos uma de suas pontas em X.

P ROBLEMA DA C OBERTURA M ÍNIMA: Encontrar uma cobertura mí-

nima num grafo dado.

A cardinalidade de uma cobertura mínima de um grafo G é denotada por

β(G) .

Há uma relação simples e íntima entre coberturas por vértices e conjuntos

estáveis (veja o exercício 7.6). Essa relação torna o problema da cobertura
mínima equivalente ao problema do conjunto estável máximo.

Exercícios
E 7.1 Uma galeria de arte consiste em um grande número de corredores retos
que interligam pequenas praças. Um guarda postado numa praça é capaz de
vigiar todos os corredores que saem da praça. Qual o número mínimo de
guardas necessário para vigiar a galeria toda?

E 7.2 Encontre uma cobertura mínima no grafo do cavalo. Encontre uma

cobertura mínima no grafo do bispo.

E 7.3 Encontre uma cobertura mínima no cubo Qk .

1
Quem sabe seria melhor dizer “cobertura das arestas por vértices”.

83
FEOFILOFF Cobertura por vértices 84

◦ E 7.4 Mostre que um grafo G é bicolorável se e somente se VG tem um

subconjunto U que é, ao mesmo tempo, um conjunto independente e uma
cobertura.

◦ E 7.5 O que é uma cobertura minimal? Use o grafo da figura 5.1 para
dar um exemplo de uma cobertura minimal. É verdade que toda cobertura
minima é minimal? É verdade que toda cobertura minimal é minima?

? E 7.6 Prove a seguinte relação entre coberturas e conjuntos estáveis: em

qualquer grafo G, um conjunto X de vértices é uma cobertura se e somente
se VG r X é estável. Deduza daí que β(G) = n(G) − α(G).

E 7.7 Mostre que o problema da cobertura mínima é equivalente ao pro-

blema do conjunto estável máximo. (Em outras palavras, mostre que qual-
quer algoritmo para um dos problemas pode ser convertido num algoritmo
para o outro.)

E 7.8 Suponha que T é uma árvore. É verdade que toda cobertura minimal
de T é mínima?

◦ E 7.9 Seja {U, W } uma bicoloração de um grafo G. Seja {X, X 0 } uma par-
tição de U e {Y, Y 0 } uma partição de W . Suponha que N(X) ⊆ Y . (Veja
definição de N(X) no exercício 1.108.) Mostre que Y ∪ X 0 é uma cobertura.

?◦ E 7.10 (S OLUÇÃO APROXIMADA) Especifique um algoritmo que dê uma

solução aproximada do problema da cobertura mínima: ao receber um
grafo G, o algoritmo deve devolver uma cobertura X tal que |X| ≤ 2β(G).

E 7.11 Considere a equivalência discutida no exercício 7.7 e a solução aproxi-

mada discutida no exercício 7.10. É possível obter uma solução aproximada
semelhante para o problema do conjunto estável máximo (veja capítulo 5)?
Capítulo 8

Coloração de vértices

Uma coloração dos vértices, ou recobrimento por conjuntos estáveis, de um

grafo é uma coleção de conjuntos estáveis que cobre o conjunto de vértices do
grafo Mais precisamente, uma coloração dos vértices de um grafo G é uma
coleção {X1 , X2 , . . . , Xk } de conjuntos estáveis tal que X1 ∪X2 ∪· · ·∪Xk = VG .
Embora isso não seja essencial, é cômodo supor que os conjuntos X1 ,
. . . , Xk são disjuntos dois a dois. Podemos dizer então que uma coloração
dos vértices de G é uma partição de VG em conjuntos estáveis. Cada vértice
do grafo estará em um e apenas um desses conjuntos. (É claro que o conceito
de coloração de vértices é uma generalização do conceito de bicoloração
discutido no capítulo 4.)
Se imaginarmos que cada conjunto estável Xi corresponde a uma cor,
podemos dizer que uma coloração de vértices é uma atribuição de cores aos
vértices tal que vértices adjacentes recebem cores diferentes.
Dizemos que uma coloração {X1 , X2 , . . . , Xk } usa k cores.1 Dizemos
também que esta é uma k-coloração. Se um grafo tem uma k-coloração então
também tem uma k 0 -coloração para todo k 0 > k.
Uma coloração de vértices é mínima se o seu número de cores é o menor
possível, ou seja, se não existe outra que use menos cores.

P ROBLEMA DA C OLORAÇÃO DE V ÉRTICES: Encontrar uma coloração

mínima dos vértices de um grafo dado.

O número cromático (= chromatic number) de um grafo G é o número de

cores em uma coloração mínima dos vértices de G. Esse número é denotado
por
χ(G) .
Um grafo G é k-colorável (= k-colorable) se χ(G) ≤ k. Em particular, “2-
colorável” é o mesmo que “bicolorável”, conforme o capítulo 4.

1
Mesmo que algum Xi seja vazio.

85
FEOFILOFF Coloração de vértices 86

Veja o sítio WWW Graph Coloring Page de Joseph Culberson na Universi-

dade de Alberta, Canadá.

Uma cobertura de G por cliques é qualquer partição {X1 , . . . , Xk } de VG

tal que cada Xi é uma clique. É claro que uma cobertura de G por cliques é o
mesmo que uma coloração dos vértices de G. O correspondente PROBLEMA
DA COBERTURA POR CLIQUES consiste em encontrar a menor cobertura de VG
por cliques.

Exercícios
E 8.1 Uma indústria precisa armazenar um conjunto de reagentes químicos.
Por razões de segurança, certos pares de reagentes não devem ficar num
mesmo compartimento do armazém. Quantos compartimentos o armazém
deve ter no mínimo?

◦ E 8.2 Mostre que o número cromático é invariante sob isomorfismo. Em

outras palavras, se G e H são grafos isomorfos então χ(G) = χ(H).

◦ E 8.3 Seja {X1 , . . . , Xk } uma coloração dos vértices de um grafo G. Mostre

que existe uma coloração {Y1 , . . . , Yk } tal que os conjuntos Y1 , . . . , Yk são
disjuntos dois a dois.

◦ E 8.4 Encontre uma coloração mínima dos vértices de um caminho. Repita

com um circuito no lugar do caminho. Repita com uma grade no lugar do
caminho.

E 8.5 Seja Tt o grafo da torre t-por-t. Encontre uma coloração mínima dos
vértices de Tt .

E 8.6 Seja Bt o grafo do bispo t-por-t. Encontre uma coloração mínima dos
vértices de Bt .

E 8.7 Seja Bt o grafo do bispo t-por-t. Encontre uma cobertura por cliques
mínima do grafo Bt .

E 8.8 Seja Ct o grafo do cavalo t-por-t. Encontre uma coloração mínima dos
vértices de Ct . Encontre uma cobertura mínima de Ct por cliques. (Considere
inicialmente os casos t = 2, . . . , 6.)

E 8.9 Seja Dt o grafo da dama t-por-t. Encontre uma coloração mínima dos
vértices de Dt . (Trate inicialmente dos casos t = 2, . . . , 6.)
FEOFILOFF Coloração de vértices 87

E 8.10 Seja Rt o grafo do rei t-por-t. Encontre uma coloração mínima dos
vértices de Rt .

E 8.11 Encontre uma coloração mínima do grafo dos estados do Brasil (veja
exercício 1.17).

E 8.12 Encontre uma coloração mínima dos vértices do cubo Qk . Encontre

uma cobertura por cliques mínima do cubo Qk .

E 8.13 Encontre uma coloração mínima dos vértices do grafo de Petersen.

E 8.14 Encontre uma coloração mínima dos vértices do grafo G definido da

seguinte maneira: comece com cinco cópias mutuamente disjuntas, digamos
B1 , . . . , B5 , de um grafo completo com 3 vértices; para cada i, acrescente
arestas ligando todos os vértices de Bi a todos os de Bi+1 ; finalmente, acres-
cente arestas ligando todos os vértices de B5 a todos os de B1 . (Este grafo
foi usado por Catlin2 como contraexemplo para a conjectura de Hajós. Veja
exercício 8.71.)

E 8.15 São dadas máquinas 1, . . . , n e intervalos de tempo I1 , . . . , In . Para

cada i, um operador deve cuidar da máquina i durante o intervalo Ii . Se
Ii ∩ Ij 6= ∅, um mesmo operador não pode cuidar de i e j. Qual o número
mínimo de operadores suficiente para operar as máquinas? (Veja o exercí-
cio 1.22.)

◦ E 8.16 Exiba um grafo G com duas colorações mínimas diferentes dos vér-
tices de G.

◦ E 8.17 Suponha que um grafo G tem uma coloração de vértices com k cores.
É verdade que G tem uma coloração {X1 , . . . , Xk } tal que X1 é um conjunto
independente máximo?

◦ E 8.18 Seja G um grafo com pelo menos uma aresta. Prove que existe uma
partição {A, B} de VG tal que χ(G[A]) + χ(G[B]) = χ(G).

◦ E 8.19 Sejam G e H dois grafos tais que VG ∩VH = ∅. Mostre que χ(G∪H) =
max{χ(G), χ(H)}.

◦ E 8.20 Seja H um subgrafo de um grafo G. Qual a relação entre χ(H)

e χ(G)?
2
P. A. Catlin, 1979.
 FEOFILOFF Coloração de vértices 88

E 8.21 Seja e uma ponte de um grafo G com duas ou mais arestas. Mostre
que χ(G − e) = χ(G).

E 8.22 Seja v uma articulação de um grafo G. É verdade que χ(G) =

χ(G − v)?

E 8.23 Seja v um vértice de um grafo G. Suponha que d(v) < χ(G)−1. Mostre
que χ(G) = χ(G − v).

E 8.24 Mostre que, para qualquer grafo G, toda coloração dos vértices de G
χ≥ usa pelo menos dn(G)/α(G)e cores. Em outras palavras, mostre que χ(G) ≥
n(G)/α(G).

E 8.25 (G ENERALIZAÇÃO DE 8.24) Para cada vértice v de um grafo G, seja

αv a cardinalidade de
P um conjunto estável máximo dentre os que contêm v.
χ≥ Mostre que χ(G) ≥ v 1/αv .

E 8.26 Mostre que todo grafo com n vértices e número cromático k tem no
χ≥ máximo 21 (n2 − n2 /k) arestas. Deduza daí que χ(G) ≥ n2 /(n2 − 2m) para
todo grafo G com n vértices e m arestas.3 Deduza daí que χ(G) ≥ n/(n − r)
se G é r-regular.4
q
1 1
E 8.27 Mostre que χ(G) ≤ 2
+ 2m(G) + 4
para todo grafo G.

E 8.28 (A LGORITMO) O algoritmo que descreveremos a seguir resolve o

problema da coloração de vértices? Ao receber um grafo G, o algoritmo faz
o seguinte:
Escolhe um conjunto estável máximo, digamos X1 , em G. Em seguida,
escolhe um conjunto estável máximo X2 em G − X1 . Depois, escolhe um
conjunto estável máximo X3 em (G − X1 ) − X2 . E assim por diante, até que
não haja mais vértices a escolher.

E 8.29 (A LGORITMO) O seguinte algoritmo guloso (= greedy) recebe um

grafo G e devolve uma coloração dos vértices X1 , . . . , Xk . Cada iteração
começa com um coleção X1 , . . . , Xk de conjuntos estáveis; a primeira pode
começar com a coleção vazia, isto é, com k = 0. Cada iteração consiste no
seguinte:

3
Alguns exemplos: se m > 0 então χ > 1; se m > n2 /4 então χ > 2; se m > 4n2 /9
então χ > 9.
4
Exemplos: se r > 0 então χ > 0; se r > n/2 então χ > 2; se r > 2n/3 então χ > 3.
FEOFILOFF Coloração de vértices 89

C ASO 1: X1 ∪ . . . ∪ Xk = VG .
Devolva X1 , . . . , Xk e pare.
C ASO 2: X1 ∪ . . . ∪ Xk 6= VG .
Escolha um vértice v em VG r (X1 ∪ . . . ∪ Xk ).
Se Xi ∪ {v} é estável para algum i entre 1 e k
então comece nova iteração com Xi ∪ {v} no papel de Xi .
Caso contrário, faça Xk+1 = {v} e
comece nova iteração com k + 1 no papel de k.
Este algoritmo resolve o problema da coloração de vértices?

E 8.30 ♥ Prove que todo grafo G admite uma coloração de vértices com
apenas ∆(G) + 1 cores. Em outras palavras, prove que χ(G) ≤ ∆(G) + 1
para todo grafo G.

◦ E 8.31 É verdade que χ(G) ≥ ∆(G) para todo grafo G? Em outras palavras,
é verdade que toda coloração dos vértices de G usa pelo menos ∆(G) cores?

E 8.32 Prove que todo grafo G admite uma cobertura por cliques de tamanho
no máximo n(G)−δ(G). Em outras palavras, mostre que χ(G) ≤ n(G)−δ(G).

E 8.33 ♥ Seja G um grafo conexo não regular. Mostre que χ(G) ≤ ∆(G).
(Compare com o exercício 8.30.)

E 8.34 (T EOREMA DE B ROOKS5 ) Seja G um grafo conexo não completo di-

ferente de um circuito ímpar. Mostre que χ(G) ≤ ∆(G). (Compare com o
exercício 8.33.)

E 8.35 Mostre que a diferença ∆(G) − χ(G) pode ser arbitrariamente grande.
Mostre que o quociente ∆(G)/χ(G) pode ser arbitrariamente grande. (Com-
pare com o exercício 8.30.)

E 8.36 (G ENERALIZAÇÃO DE 8.30) Sejam v1 , v2 , . . . , vn os vértices de um

grafo G e suponha que d(v1 ) ≥ d(v2 ) ≥ · · · ≥ d(vn ). Mostre que χ(G) ≤
maxni=1 min{i, d(vi ) + 1}. (Sugestão: o lado direito da desigualdade é igual a
max { i : d(vi ) + 1 ≥ i }.)

E 8.37 Seja G um grafo dotado da seguinte propriedade: todo par de circui-

tos ímpares tem (pelo menos) um vértice em comum. Prove que G admite
uma 5-coloração dos vértices.
5
Publicado por R. L. Brooks em 1941.
 FEOFILOFF Coloração de vértices 90

? E 8.38 Suponha que um grafo G tem uma clique com k vértices. Mostre que
χ≥ toda coloração de vértices de G usa pelo menos k cores. Em outras palavras,
mostre que
χ(G) ≥ ω(G)
para todo grafo G. (Veja exercícios 6.8 e 6.9.)

E 8.39 Suponha que um grafo G tem uma clique com k vértices e uma colo-
ração dos vértices em k cores. Prove que a clique é máxima e que a coloração
é mínima.6

E 8.40 Prove que χ(G) = ω(G) para todo grafo bipartido G.

? E 8.41 (A LGORITMO7 ) Sejam v1 , v2 , . . . , vn os vértices de um grafo G.

Suponha que, para i = 2, . . . , n, o conjunto

{v1 , . . . , vi−1 } ∩ N(vi )

é uma clique. Mostre que χ(G) = ω(G). (Sugestão: Escreva um algoritmo

que calcule uma coloração de vértices mínima e uma clique máxima.)

E 8.42 Mostre que, para todo k, existe um grafo sem cliques de tamanho
k que não admite coloração com k (ou menos) cores. Em outras palavras,
mostre que existem grafos G tais que χ(G) > ω(G). Mostre que para cada k
existe um grafo G tal que χ(G) = k e ω(G) = 2.

E 8.43 Suponha que um grafo G tem um conjunto estável com k vértices.

Mostre que toda cobertura de VG por cliques usa pelo menos k cliques.
Deduza daí que χ(G) ≥ α(G).

E 8.44 Suponha que um grafo G não tem subgrafo induzido isomorfo a um

caminho com 4 vértices. Mostre que χ(G) = ω(G).

E 8.45 Suponha que um grafo G não tem subgrafo induzido isomorfo a K1,3
nem a K4 − e. Mostre χ(G) ≤ ω(G) + 1.

E 8.46 Seja G um grafo (não necessariamente bicolorável) e seja {R, S} uma

partição de VG . Suponha que d(R) < k (ou seja, há menos que k arestas com
uma ponta em R e outra em S). Suponha ainda que os grafos G[R] e G[S]
admitem colorações de vértices com k cores apenas. Mostre que G admite
uma coloração de vértices com k cores.
6
Uma tal clique pode ser usada como certificado de minimalidade da coloração. Reci-
procamente, uma tal coloração pode ser usada como certificado de maximalidade da clique.
7
Perfect Elimination Scheme.
FEOFILOFF Coloração de vértices 91

E 8.47 Seja P um caminho de comprimento máximo em um grafo G. Mostre

que χ(G) ≤ n(P ). (Em outras palavras, se um grafo não tem caminho com
mais que k vértices então pode ser colorido com apenas k cores.)

E 8.48 (T EOREMA DE G ALLAI E R OY8 ) Para qualquer orientação acíclica9 D

de um grafo G, seja l(D) o comprimento de um caminho orientado10 máximo
em D. Então
χ(G) = 1 + min l(D) .
D

D 8.49 (A LGORITMO) Invente um algoritmo rápido que resolva o problema

da coloração de vértices.

Coloração com número dado de cores

Se o número de cores disponíveis estiver fixo, temos a seguinte variante do
problema da coloração:
P ROBLEMA DA C OLORAÇÃO COM N ÚMERO D ADO DE C ORES: Dado
um número natural k e um grafo G, encontrar uma k-coloração de G.
(É evidente que o problema nem sempre tem solução.) O problema da 2-
coloração, por exemplo, equivale ao problema de decidir se um dado grafo é
bicolorável (veja exercício 4.15).

E 8.50 O seguinte algoritmo recebe um grafo G e promete devolver uma

bicoloração de G. Cada iteração começa com um par (X1 , X2 ) de conjuntos
estáveis; a primeira pode começar com X1 = X2 = ∅. Cada iteração consiste
no seguinte:
C ASO 1: X1 ∪ X2 = VG .
Devolva X1 , X2 e pare.
C ASO 2: X1 ∪ X2 6= VG .
Escolha um vértice v em VG r (X1 ∪ X2 ).
Escolha i em {1, 2} tal que Xi ∪ {v} é estável.
Comece nova iteração com Xi ∪ {v} no papel de Xi .
O algoritmo cumpre a promessa (ou seja, produz uma 2-coloração dos vérti-
ces do grafo)?
8
Publicado em 1966 por Tibor Gallai e em 1967, independentemente, por Bernard Roy.
9
Uma orientação de um grafo consiste na substituição de cada aresta vw pelo par orde-
nado (v, w) ou pelo par ordenado (w, v). Um tal par ordenado é chamado arco. O resultado
é um grafo dirigido. Um grafo dirigido D é acíclico se não tem circuitos orientados. Um
circuito é orientado se todos os seus arcos são dirigidas no mesmo sentido.
10
Um caminho é orientado se todos os seus arcos são dirigidas no mesmo sentido.
FEOFILOFF Coloração de vértices 92

E 8.51 O seguinte algoritmo guloso recebe um grafo G e promete devolver

uma 3-coloração de G. Cada iteração começa com conjuntos estáveis X1 , X2
e X3 ; a primeira pode começar com X1 = X2 = X3 = ∅. Cada iteração
consiste no seguinte:
C ASO 1: X1 ∪ X2 ∪ X3 = VG .
Devolva X1 , X2 , X3 e pare.
C ASO 2: X1 ∪ X2 ∪ X3 6= VG .
Escolha um vértice v em VG r (X1 ∪ X2 ∪ X3 ).
Escolha i em {1, 2, 3} tal que e Xi ∪ {v} é estável.
Comece nova iteração com Xi ∪ {v} no papel de Xi .
O algoritmo cumpre o prometido?

E 8.52 Considere o seguinte algoritmo guloso, que recebe um grafo G e

promete devolver uma 3-coloração de G:
W ← VG
enquanto W 6= ∅ faça
escolha w em W
i←1
enquanto N(w) ∩ Xi 6= ∅ faça i ← i + 1
Xi ← Xi ∪ {w}
W ← W r Xi
devolva X1 , X2 , X3
O algoritmo cumpre o que prometeu?

E 8.53 Quantas arestas no máximo pode ter um grafo com n vértices que
admite uma 3-coloração dos vértices?

E 8.54 Imagine uma grade em que todos os vértices exceto um estão colo-
ridos. Cada vértice colorido tem uma de 3 possíveis cores. Invente uma
“heurística da troca de cores em componentes bicoloridas” (compare com o
exercício 12.22) para obter, a partir da coloração parcial dada, uma coloração
de todos os vértices com apenas 3 cores.

E 8.55 Sejam I e J conjuntos estáveis num grafo G e suponha I ∩ J = ∅. Seja

X o conjunto dos vértices de um componente do grafo bipartido G[I ∪ J].
Mostre que o conjunto I ⊕ X é estável no grafo G.

E 8.56 (A LGORITMO) Descreva uma heurística11 de coloração de vértices

baseada no exercício 8.55. (No início de cada iteração temos uma coloração
11
Segundo Wilf (em Algorithms and Complexity, Prentice-Hall, 1986), heurísticas são
“methods that seem to work well in practice, for reasons nobody understands”.
FEOFILOFF Coloração de vértices 93

parcial dos vértices; cada iteração escolhe um vértice não colorido e procura
atribuir a ele uma das cores já usadas.)

D 8.57 Como se sabe, grafos 2-coloráveis são caracterizados pela ausência de

circuitos ímpares. Invente uma boa caracterização dos grafos 3-coloráveis.
Invente uma boa caracterização dos grafos k-coloráveis.

D 8.58 (A LGORITMO) Invente um algoritmo rápido que resolva o problema

da 3-coloração de vértices.12

D 8.59 (A LGORITMO) Seja k um número natural maior que 3. Invente um

algoritmo rápido que resolva o problema da k-coloração de vértices.

Coloração de grafos planares

Grafos planares podem ser coloridos com poucas cores.

E 8.60 Mostre que χ(G) ≤ 6 para todo grafo planar G. (Veja os exercí-
cios 1.275 e 8.30.)

E 8.61 (T EOREMA DE H EAWOOD13 ) Mostre que χ(G) ≤ 5 para todo grafo

planar G. (Veja exercícios 1.275, 8.54 e 8.56.)

E 8.62 (A LGORITMO) Construa um algoritmo que produza uma 5-coloração

dos vértices de qualquer grafo planar dado.

!! E 8.63 (T EOREMA DAS Q UATRO C ORES14 ) Mostre que todo grafo planar
admite uma coloração de vértices com 4 ou menos cores. Em outras palavras,
mostre que
χ(G) ≤ 4
para todo grafo planar G.

◦ E 8.64 Mostre que existem grafos planares que não admitem coloração dos
vértices com 3 cores apenas.
12
Não se conhece um algoritmo rápido que decida se um grafo é 3-colorável. Em termos
técnicos, esse problema de decisão é NP-completo. Veja observação na página 5.
13
Percy John Heawood ( − ).
14
Demonstrado em 1976 por Kenneth Appel e Wolfgang Haken. Demonstração simplifi-
cada em 1997 por Neil Robertson, Daniel P. Sanders, Paul D. Seymour e Robin Thomas. Veja
as páginas “The four color theorem” e “Four-Color Theorem” and “Four-Color Theorem.”
FEOFILOFF Coloração de vértices 94

E 8.65 É verdade que χ(G) = ω(G) para todo grafo planar G? (Veja exercí-
cios 8.38 e 8.39.)

E 8.66 Seja G o grafo dos estados do Brasil (veja exercício 1.17). Mostre que
χ(G) = 4.

!! E 8.67 (A LGORITMO) Construa um algoritmo que produza uma 4-

coloração dos vértices de qualquer grafo planar dado.

E 8.68 Mostre que α(G) ≥ 41 n(G) para todo grafo planar G. (Seria muito
interessante ter uma prova desse fato que não dependesse do teorema das
quatro cores, exercício 8.63.)

E 8.69 Uma coloração das faces de uma mapa plano é uma atribuição de
cores às faces do mapa (veja subseção 1.17) tal que faces adjacentes recebem
cores diferentes.
Deduza do Teorema das Quatro Cores (exercício 8.63) que as faces de
qualquer mapa plano cujo grafo é aresta-biconexo podem ser coloridas com
4 cores ou menos.

E 8.70 Mostre que o conjunto das faces de todo grafo exoplanar (veja o
exercício 1.283) é 3-colorável.

Coloração versus menores

Estude antes o capítulo 19 (Planaridade).

! E 8.71 Prove que a seguinte conjectura de Hajós15 é falsa: Para todo grafo G,
se χ(G) ≥ k então G tem um menor topológico (veja seção 1.16) isomorfo
a Kk .

E 8.72 Seja G um grafo tal que χ(G) ≥ 3. Mostre que G tem um menor (veja
seção 1.16) isomorfo a K3 . (Compare com o exercício 8.38.)

E 8.73 Seja G um grafo tal que χ(G) ≥ 4. Mostre que G tem um menor
isomorfo a K4 .

!! E 8.74 Seja G um grafo tal que χ(G) ≥ 5. Mostre que G tem um menor iso-
morfo a K5 . (Isto é equivalente ao teorema da Quatro Cores, exercício 8.63.)
15
A conjectura foi proposta por G. Hajós, em 1961.
FEOFILOFF Coloração de vértices 95

D 8.75 (C ONJECTURA DE H ADWIGER16 ) Para todo número natural k ≥ 2 e

todo grafo G, se χ(G) ≥ k então G tem um menor isomorfo a Kk . (Esta é uma
profunda generalização do teorema da Quatro Cores, exercício 8.63.)

Coloração de grafos aleatórios

E 8.76 Seja ε um número real positivo. Mostre que
1 n
χ(G) >
2 + ε log2 n
para quase todo grafo G em G(n). (Veja a seção 1.18.)

! E 8.77 Seja ε um número real positivo menor que 2. Mostre que

1 n
χ(G) <
2 − ε log2 n
para quase todo grafo G em G(n). (Compare com o exercício 8.76.)

Grafos perfeitos
Um grafo é perfeito (= perfect) se χ(G[X]) = ω(G[X]) para todo subconjunto
X de VG . (Veja o exercício 8.38.)

E 8.78 Exiba um grafo não perfeito G tal que χ(G) = ω(G).

E 8.79 Mostre que todo grafo bicolorável é perfeito.

! E 8.80 (T EOREMA DE L OVÁSZ17 ) Mostre que o complemento de todo grafo

perfeito é perfeito.

!! E 8.81 (T EOREMA F ORTE DO G RAFO P ERFEITO18 ) Um buraco ímpar

(= odd hole) é um circuito induzido com um número ímpar ≥ 5 de vértices.
Prove que um grafo G é perfeito se e somente se nem G nem G contêm
um buraco ímpar.19 (Esta caracterização de grafos perfeitos havia sido con-
jecturada por Claude Berge em 1960.)

16
A conjectura foi proposta por H. Hadwiger, em 1943.
17
Publicado por Lásló Lovász em 1972.
18
Strong Perfect Graph Theorem.
19
Este teorema foi provado em 2002 por Maria Chudnovsky e Paul D. Seymour com base
em trabalho prévio de Neil Robertson e Robin Thomas.
FEOFILOFF Coloração de vértices 96
Capítulo 9

Emparelhamentos

Duas arestas de um grafo são adjacentes se têm uma ponta comum. Um

emparelhamento (= matching) é um conjunto de arestas duas a duas não ad-
jacentes. Em outras palavras, um emparelhamento num grafo é um conjunto
M de arestas tal que |M ∩ ∂(v)| ≤ 1 para cada vértice v.

P ROBLEMA DO E MPARELHAMENTO M ÁXIMO: Encontrar um empare-

lhamento máximo num grafo dado.

Um emparelhamento M ∗ é máximo se não existe um emparelhamento M

tal que |M | > |M ∗ |. A cardinalidade de um emparelhamento máximo num
grafo G é denotada por
α 0 (G) .
A propósito, um emparelhamento M 0 é maximal se não faz parte de um
emparelhamento maior, ou seja, se não existe um emparelhamento M tal que
M ⊃ M 0.
O problema do emparelhamento é um caso particular do problema do
conjunto estável (veja o exercício 9.15). Embora não saibamos como resolver
este último de maneira eficiente, sabemos como resolver o primeiro.
Um emparelhamento M é perfeito (= perfect matching) se cada vértice
do grafo é ponta de algum elemento de M . Eis uma especialização inte-
ressante do problema acima: Encontrar um emparelhamento perfeito num
grafo dado. É claro que nem todo grafo tem um emparelhamento perfeito; a
dificuldade do problema está em decidir se o grafo dado tem ou não tem um
emparelhamento perfeito.
Os seguintes conceitos são importantes no estudo de emparelhamentos:
1. Um emparelhamento M satura um vértice v se ∂(v) ∩ M 6= ∅, ou seja,
se alguma aresta de M incide em v.
2. Um emparelhamento M satura um conjunto X de vértices se M
satura cada vértice em X.

97
FEOFILOFF Emparelhamentos 98

3. Um caminho é alternante (= alternating) em relação a um emparelha-

mento M se suas arestas estão alternadamente em M e fora de M .
Às vezes é mais cômodo dizer “M -alternante” que “alternante em
relação a M ”.
4. Um caminho de aumento (= augmenting path) para um emparelha-
mento M é um caminho M -alternante de comprimento não nulo cujos
extremos não estão saturados por M .

Exercícios
◦ E 9.1 Seja M um conjunto de arestas de um grafo G. Seja H o grafo (VG , M ).
Mostre que M é um emparelhamento em G se e somente se dH (v) ≤ 1 para
todo vértice v de H.

◦ E 9.2 Quantas arestas tem um emparelhamento máximo num grafo com-

pleto com n vértices?

◦ E 9.3 Quantas arestas tem um emparelhamento máximo em um grafo bi-

partido completo?

◦ E 9.4 Calcule um emparelhamento máximo em um caminho. Calcule um

emparelhamento máximo em um circuito.

◦ E 9.5 Suponha que um grafo G tem um emparelhamento perfeito. Mostre

que n(G) é par.

E 9.6 Seja G um K6 e M um emparelhamento perfeito em G. Mostre que

G − M é planar. Mostre que G − M tem um emparelhamento perfeito,
digamos M 0 . Mostre que o complemento de (G − M ) − M 0 é um circuito
de comprimento 6.

E 9.7 Calcule um emparelhamento máximo em um grafo cúbico dotado de

circuito hamiltoniano (veja capítulo 17).

◦ E 9.8 É verdade que todo grafo regular tem um emparelhamento perfeito?

◦ E 9.9 Encontre um emparelhamento máximo no grafo da dama t-por-t.

E 9.10 Encontre um emparelhamento máximo no grafo do bispo t-por-t.

E 9.11 Encontre um emparelhamento máximo no grafo do cavalo t-por-t.

FEOFILOFF Emparelhamentos 99

E 9.12 Quantas arestas tem um emparelhamento máximo no cubo Qk ?

E 9.13 Exiba um grafo G e um emparelhamento em G que seja maximal mas

não seja máximo.

E 9.14 É verdade que em qualquer árvore todo emparelhamento maximal é

máximo?

E 9.15 Mostre que o problema do emparelhamento máximo é um caso parti-

cular do problema do conjunto estável máximo.

E 9.16 É verdade que, em qualquer grafo, todo vértice não isolado é saturado
por algum emparelhamento máximo? É verdade que toda aresta pertence a
algum emparelhamento perfeito?

. E 9.17 ♥ Sejam M e M 0 dois emparelhamentos num grafo G. Descreva o

grafo (VG , M ∪ M 0 ). Descreva o grafo (VG , M ⊕ M 0 ).1 Que acontece se os M ⊕ M 0
emparelhamentos M e M 0 são perfeitos?

E 9.18 Suponha que um grafo G tem uma ponte a. Mostre que ou todos
os emparelhamentos perfeitos de G contêm a ou nenhum emparelhamento
perfeito de G contém a.

E 9.19 Prove que toda floresta tem no máximo um emparelhamento perfeito.

◦ E 9.20 Seja M um emparelhamento em um grafo e seja P um caminho M -

alternante. Mostre que todo caminho em P também é M -alternante.

E 9.21 Seja M um emparelhamento em um grafo e seja P um caminho M -

alternante maximal. Suponha que as duas arestas extremas de P não estão
em M . É verdade que P é um caminho de aumento?

? E 9.22 (C AMINHO DE AUMENTO )

Suponha que P é um caminho de au-
mento para um emparelhamento M . Prove que

M ⊕ EP

é um emparelhamento. Prove que |M ⊕ EP | > |M |.

1
Para quaisquer conjuntos A e B, denota-se por A ⊕ B o conjunto (A r B) ∪ (B r A).
É fácil verificar que A ⊕ B = (A ∪ B) r (A ∩ B).
FEOFILOFF Emparelhamentos 100

? E 9.23 Seja M um emparelhamento num grafo G. Suponha que M não é

máximo. Prove que existe um caminho de aumento para M .

? E 9.24 (T EOREMA B ERGE2 ) Prove que um emparelhamento M é má-

DE
ximo se e somente se não existe caminho de aumento para M . (Segue dos
exercícios 9.22 e 9.23.)

! E 9.25 (A LGORITMO) Seja M um emparelhamento em um grafo G. Sejam

a e b dois vértices não saturados por M . Escreva um algoritmo que encontre
um caminho alternante com origem a e término b (ou constate que um tal
caminho não existe).

E 9.26 ♥ Seja M um emparelhamento. Seja (v0 , v1 , . . . , vk ) um passeio (veja

fim da seção 1.9) cujas arestas estão alternadamente em M e fora de M e
suponha que v0 e vk não estão saturados por M . Seja A o conjunto das arestas
do passeio. Mostre que o conjunto M ⊕ A pode não ser um emparelhamento.
(Compare com o exercício 9.22.)

E 9.27 (S LITHER) Dois jogadores, digamos A e B, se alternam escolhendo

vértices num grafo G. Primeiro, A escolhe um vértice v0 . Em seguida, B
escolhe um vértice v1 adjacente a v0 . Depois, A escolhe um vértice adjacente
a v1 mas diferente de v0 e de v1 . E assim por diante.
Eis uma maneira mais limpa de descrever o jogo: Os vértices escolhidos
formam um caminho v0 v1 v2 · · · vk . Se k é ímpar, A escolhe um vértice vk+1
distinto dos demais mas adjacente a vk . Se k é par, B faz um jogada análoga.
O último jogador que puder fazer um movimento vence o jogo.
Prove que B tem uma estratégia vencedora se G tem um emparelha-
mento perfeito. Prove que A tem uma estratégia vencedora em caso contrá-
rio.

E 9.28 Seja M um emparelhamento e X um conjunto de vértices de um grafo.

Mostre que se X é saturado por M então X também é saturado por algum
emparelhamento máximo. (Compare com o exercício 9.16.)

E 9.29 Sejam X e Y dois conjuntos de vértices de um grafo G. Suponha

que X é saturado por algum emparelhamento e Y é saturado por algum
emparelhamento (não necessariamente o mesmo).
Se y é um elemento de Y r X, é verdade que X ∪ {y} é saturado por
algum emprelhamento?
Se |Y | > |X|, é verdade que existe y em Y r X, tal que X ∪ {y} é saturado
por algum emprelhamento?
2
Publicado em 1957 por Claude Berge ( − ).
FEOFILOFF Emparelhamentos 101

? E 9.30 (E MPARELHAMENTOS VERSUS COBERTURAS) Mostre que, em qual-

quer grafo, para qualquer emparelhamento M e qualquer cobertura K (veja
capítulo 7),
|M | ≤ |K| .
Deduza daí que se |M | = |K| então M é um emparelhamento máximo e K
é uma cobertura mínima.3 Dê um exemplo de um grafo que não possui um
par (M, K) tal que |M | = |K|. (Veja também o exercício 9.33.)

? E 9.31 Mostre que α 0 (G) ≤ β(G) para todo grafo G. α0 ≤

◦ E 9.32 Seja K uma cobertura minimal de um grafo (veja o capítulo 7). É

verdade que toda aresta de qualquer emparelhamento tem apenas uma das
pontas em K?

E 9.33 Seja M um emparelhamento e K uma cobertura (veja o capítulo 7)

tais que |M | = |K|. Mostre que M satura K e que cada elemento de M tem
apenas uma das pontas em K. (Veja o exercício 9.30.)

E 9.34 Suponha que M é um emparelhamento maximal num grafo. Seja

V (M ) o conjunto dos vértices saturados por M . Mostre que V (M ) é uma
cobertura (veja o capítulo 7).
Escolha uma das pontas de cada aresta em M . Seja W o conjunto
resultante. É verdade que W é uma cobertura?

E 9.35 (E MPARELHAMENTO QUASE MÁXIMO) Seja M um emparelhamento

maximal e M ∗ um emparelhamento máximo em um grafo. É evidente que
|M | ≤ |M ∗ |. Mostre que |M | ≥ 21 |M ∗ |. É verdade que |M | > 12 |M ∗ | qualquer
que seja o grafo?

E 9.36 Suponha que um grafo G tem um emparelhamento perfeito. Mostre

que, para todo vértice v, o grafo G − v tem exatamente um componente com
número ímpar de vértices.

E 9.37 Seja G um grafo com n(G) ≥ 2k e δ(G) ≥ k. Mostre que G tem um

emparelhamento com pelo menos k arestas.

3
Assim, se uma cobertura tem o mesmo tamanho que um emparelhamento, ela serve de
certificado da maximalidade do emparelhamento.
FEOFILOFF Emparelhamentos 102
Capítulo 10

Emparelhamentos em grafos
bipartidos

Quando restrito a grafos bipartidos, o problema do emparelhamento máximo

(veja capítulo 9) tem uma solução muito elegante e eficiente. Dois teoremas
(veja exercícios 10.7 e 10.23) resumem a solução:
1. Num grafo bipartido, um emparelhamento máximo tem o mesmo
tamanho que uma cobertura mínima.
2. Um grafo com bipartição {U, W } tem um emparelhamento que satura
U se e somente se |N(Z)| ≥ |Z| para todo subconjunto Z de U .
A expressão N(Z) denota o conjunto de todos os vértices que estão fora de Z N(X)
mas têm algum vizinho em Z. (Veja exercício 1.108.)

Exercícios
E 10.1 Exiba um emparelhamento máximo no grafo da figura 10.1.

Figura 10.1: Encontre um emparelhamento máximo.

E 10.2 Encontre um emparelhamento máximo no cubo Qk .

E 10.3 Exiba um emparelhamento máximo no grafo da figura 10.2.

103
FEOFILOFF Emparelhamentos em grafos bipartidos 104

Figura 10.2: Encontre um emparelhamento máximo.

. E 10.4 (L EMA DE D E C AEN1 ) Seja G um grafo bipartido com pelo menos

uma aresta. Mostre que algum vértice de G é saturado por todos os empare-
lhamentos máximos. (Usado na solução indutiva do exercício 10.6.)

◦ E 10.5 É verdade que todo grafo bipartido tem uma aresta que pertence
a todos os emparelhamentos máximos? (Compare com o exercício 10.4.) É
verdade que todo grafo bipartido tem uma aresta que não pertence a nenhum
emparelhamento máximo?

? E 10.6 Mostre que todo grafo bipartido tem um emparelhamento M e uma

cobertura K tais que
|M | = |K| .
(Compare com o exercício 9.30. Veja o exercício 10.4.)

Figura 10.3: Os círculos cinzentos indicam uma cobertura. As

linhas cinzentas indicam um emparelhamento. (Exercício 10.6.)

? E 10.7 (T EOREMA DEK ŐNIG –E GERVÁRY2 ) Seja M ∗ um emparelhamento

máximo e K∗ uma cobertura mínima de um grafo bicolorável. Mostre que
|M ∗ | = |K∗ |. (Segue de 9.30 e 10.6.)

E 10.8 Mostre que α 0 (G) = β(G) em todo grafo bicolorável G.

E 10.9 Encontre um emparelhamento máximo e uma cobertura mínima no

grafo da figura 10.1.

E 10.10 Seja G um grafo bicolorável. Prove que χ(G) = ω(G).

1
Publicado em 1988.
2
Publicado em 1931 por Dénes Kőnig ( − ). O teorema também é atribuído a
Eugene Egerváry ( − ).
FEOFILOFF Emparelhamentos em grafos bipartidos 105

E 10.11 Dê uma condição necessária e suficiente para que um grafo bipartido

tenha um emparelhamento com k arestas.

E 10.12 Seja G um grafo {U, W }-bipartido. Suponha que |U | = |W | e

m(G) > (k − 1) |U | para algum k inteiro positivo. Prove que G tem um
emparelhamento de cardinalidade k.

Algoritmos
◦ E 10.13 Seja G um grafo {U, W }-bipartido. Seja {U 0 , U 00 } uma partição de U
e {W 0 , W 00 } uma partição de W . Mostre que N(U 0 ) ⊆ W 0 se e somente se
N(W 00 ) ⊆ U 00 . Mostre que se N(U 0 ) ⊆ W 0 então W 0 ∪ U 00 é uma cobertura.
Mostre que para toda cobertura K de G tem-se N(U r K) ⊆ W ∩ K e
N(W r K) ⊆ U ∩ K.

. E 10.14 Seja M um emparelhamento em um grafo {U, W }-bipartido G. Seja

V (M ) o conjunto dos vértices que M satura. Seja X o conjunto dos vértices
de todos os caminhos M -alternantes que têm um dos extremos em U rV (M ).
Prove que
(W ∩ X) ∪ (U r X)
é uma cobertura de G. (Usado na resolução do exercício 10.15.)

. E 10.15 (A LGORITMO) Construa um algoritmo eficiente que receba um

grafo {U, W }-bipartido e um emparelhamento M e devolva (1) um empare-
lhamento M 0 tal que |M 0 | > |M | ou (2) uma cobertura K tal que |K| = |M |.
(Veja o exercício 10.14.)

? E 10.16 (A LGORITMO H ÚNGARO3 ) Construa um algoritmo eficiente que

receba um grafo bipartido G e devolva um emparelhamento M e uma co-
bertura K de mesmo tamanho. (Veja o exercício 10.15.) (Esta é a versão
algorítmica do exercício 10.6.)

E 10.17 (A LGORITMO) Seja M um emparelhamento em um grafo {U, W }-

bipartido G. Seja V (M ) o conjunto dos vértices saturados por M . Seja a um
vértice em U r V (M ) e b um vértice em W r V (M ). Escreva um algoritmo
que encontre um caminho alternante com origem a e término b (ou constate
que um tal caminho não existe).
3
Referência aos matemáticos húngaros Kőnig, Egerváry, etc. Veja Hungarian algorithm na
Wikipedia.
FEOFILOFF Emparelhamentos em grafos bipartidos 106

E 10.18 Use o algoritmo húngaro (exercício 10.16) para provar o teorema de

Kőnig–Egerváry (exercício 10.7).

E 10.19 (A LGORITMO) Mostre como encontrar um conjunto estável máximo

num grafo bipartido.

Emparelhamentos semi-perfeitos
Um emparelhamento num grafo bipartido é semi-perfeito se satura um dos
“lados” do grafo. É claro que todo emparelhamento semi-perfeito é máximo,
mas nem todo emparelhamento máximo é semi-perfeito.

P ROBLEMA: Dado um grafo {U, W }-bipartido, encontrar um empare-

lhamento que sature U .

◦ E 10.20 Seja G um grafo {U, W }-bipartido. Seja M um emparelhamento

que satura U . Prove que M é um emparelhamento máximo. Prove que U é
uma cobertura mínima.

◦ E 10.21 Seja G um grafo {U, W }-bipartido. Suponha que |N(Z)| < |Z| para
algum subconjunto Z de U . Mostre que G não tem um emparelhamento que
satura U .

? E 10.22 Seja G um grafo {U, W }-bipartido. Suponha que

|N(Z)| ≥ |Z|

para todo subconjunto Z de U . Mostre que G tem um emparelhamento que

satura U .

? E 10.23 (T EOREMA DE H ALL4 ) Mostre que um grafo {U, W }-bipartido tem

um emparelhamento que satura U se e somente se |N(Z)| ≥ |Z| para todo
subconjunto Z de U . (Segue de 10.21 e 10.22.)

◦ E 10.24 Quais das afirmações a seguir valem para todo grafo {U, W }-
bipartido G? (1) Se G tem um emparelhamento que satura U então |N(Z)| ≥
|Z| para todo subconjunto Z de U . (2) Se G tem um emparelhamento que sa-
tura U então |N(Z)| ≥ |Z| para algum subconjunto Z de U . (3) Se |N(Z)| < |Z|
para algum subconjunto Z de U então G não tem um emparelhamento que

4
Publicado em 1935 por Philip Hall ( − ). (Veja verbete na Wikipedia.)
FEOFILOFF Emparelhamentos em grafos bipartidos 107

satura U . (4) Se |N(Z)| ≥ |Z| para todo subconjunto Z de U então G tem um

emparelhamento que satura U . (5) Se |N(Z)| < |Z| para todo subconjunto Z
de U então G não tem um emparelhamento que satura U . (6) Se |N(Z)| ≥ |Z|
para algum subconjunto Z de U então G tem um emparelhamento que
satura U .

E 10.25 (A LGORITMO) Construa um algoritmo eficiente que receba um

grafo bipartido e sua bicoloração {U, W } e devolva (1) um emparelhamento
que satura U ou (2) um subconjunto Z de U tal que |N(Z)| > |Z|. (Esta é a
versão algorítmica do teorema de Hall, exercício 10.23.)

E 10.26 Deduza o teorema de Kőnig–Egerváry (exercício 10.7) do teorema de

Hall (exercício 10.23).

E 10.27 Seja H um conjunto de homens, M um conjunto de mulheres e k um

inteiro positivo. Suponha que cada homem conhece no máximo k mulheres e
cada mulher conhece no mínimo k homens. Prove que é possível casar cada
mulher com um homem que ela conhece.

E 10.28 Seja G um grafo {U, W }-bipartido com pelo menos uma aresta. Su-
ponha que d(u) ≥ d(w) para todo u em U e w em W . Prove que existe em G
um emparelhamento que cobre U .

E 10.29 Seja G um grafo bipartido r-regular com r > 0. Mostre que G tem
um emparelhamento perfeito.

E 10.30 Prove que um grafo bicolorável G tem um emparelhamento perfeito

∗ ∗
S se |N (Z)| ≥ |Z| para ∗todo subconjunto Z de VG , sendo N (Z) o
se e somente
conjunto z∈Z N(z). (É claro que N (Z) contém N(Z).)
Dê um exemplo de um grafo (não bicolorável) que não tem emparelha-
mento perfeito mas satisfaz a desigualdade |N∗ (Z)| ≥ |Z| para todo conjunto
Z de vértices.

E 10.31 Seja G um grafo {U, W }-bipartido e X um subconjunto de U . Dê uma

condição necessária e suficiente para que exista um emparelhamento em G
que satura X.

. E 10.32 Seja G um grafo {U, W }-bipartido, X um subconjunto de U e Y

um subconjunto de W . Seja M um emparelhamento que satura X e N um
emparelhamento que satura Y . Mostre que existe um emparelhamento que
satura X ∪ Y .
FEOFILOFF Emparelhamentos em grafos bipartidos 108

E 10.33 Seja G um grafo {U, W }-bipartido com pelo menos uma aresta. Seja
X o conjunto dos vértices em U que têm grau ∆(G). Mostre que G tem um
emparelhamento que satura X.

. E 10.34 ♥ Seja G um grafo bicolorável com pelo menos uma aresta. Mostre
que existe um emparelhamento que satura todos os vértices de grau ∆(G).
(Veja exercícios 10.32 e 10.33.)

E 10.35 Seja K um grafo {U, W }-bipartido completo com |U | = |W |. Seja G

um subgrafo de K e ponha r = ∆(G). Mostre que existe um grafo r-regular
H tal que G ⊆ H ⊆ K.

E 10.36 Seja G um grafo bicolorável e ponha r = ∆(G). Mostre que G é

subgrafo de algum grafo bicolorável r-regular.

E 10.37 (G ENERALIZAÇÃO DO TEOREMA DE H ALL) Seja G um grafo

{U, W }-bipartido. Prove que todo emparelhamento máximo em G tem
cardinalidade
min |U | − |Z| + |N(Z)| .
Z⊆U

E 10.38 Seja G um grafo (não necessariamente bicolorável) e seja {A, B} uma

partição de VG . Suponha ainda que há menos que k arestas com uma ponta
em A e outra em B (ou seja, d(A) < k). Suponha que os grafos G[A] e G[B]
admitem colorações de vértices (veja capítulo 8) com k cores. Mostre que G
admite uma coloração de vértices com k cores.
Capítulo 11

Emparelhamentos em grafos
arbitrários

Um componente de um grafo é ímpar (= odd component) se tem um número

ímpar de vértices. O número de componentes ímpares de um grafo G será
denotado nesta seção por o(G). o(G)

Exercícios
E 11.1 Seja T uma árvore e suponha que o(T − v) = 1 para cada vértice v
de T . Mostre que T tem emparelhamento perfeito. (Veja antes exercício 9.36.)

E 11.2 Suponha que um grafo G tem um emparelhamento perfeito. Mostre

que o(G − S) ≤ |S| para todo conjunto S de vértices.

◦ E 11.3 Suponha que um grafo G satisfaz a condição o(G − S) ≤ |S| para

todo conjunto S de vértices. Prove que n(G) é par.

?! E 11.4 Suponha que um grafo G tem a seguinte propriedade:

o(G − S) ≤ |S|

para todo conjunto S de vértices. Mostre que G tem um emparelhamento

perfeito.

? E 11.5 (T EOREMA T UTTE1 ) Mostre que um grafo G tem um empare-

DE
lhamento perfeito se e somente se o(G − S) ≤ |S| para todo conjunto S de
vértices. (Segue dos exercícios 11.2 e 11.4.)
1
Publicado em 1947 por William T. Tutte ( − ). (Veja verbete na Wikipedia.)

109
 FEOFILOFF Emparelhamentos em grafos arbitrários 110

?! E 11.6 (A LGORITMO) Esboce um algoritmo eficiente que decida se um

grafo tem ou não tem um emparelhamento perfeito.

E 11.7 Deduza o teorema de Hall (exercício 10.23) do teorema de Tutte (exer-

cício 11.4).

? E 11.8 Seja M um emparelhamento e S um conjunto de vértices de um

grafo G. Prove que o número de vértices não saturados por M é pelo menos
o(G − S) − |S|. Deduza daí que

|M | ≤ γ(G, S) ,
1 1


γ( ) sendo γ(G, S) o número 2
n(G) − 2
o(G − S) − |S| .

E 11.9 Seja M um emparelhamento e S um conjunto de vértices de um

grafo G. Suponha que |M | = γ(G, S), sendo γ(G, S) o número definido no
exercício 11.8. Mostre que o emparelhamento M é máximo.2

?! E 11.10 Mostre que em qualquer grafo G existe um emparelhamento M e

um subconjunto S de VG tais que M deixa de saturar apenas o(G − S) − |S|
vértices, ou seja, tais que
|M | ≥ γ(G, S) ,
sendo γ(G, S) o número definido no exercício 11.8.

?! E 11.11 (T EOREMA DE T UTTE –B ERGE3 ) Prove que, em qualquer grafo G,

α 0 (G) = γ(G) ,

sendo γ(G) o valor mínimo de γ(G, S) para todos os subconjuntos S de VG ,

onde γ(G, S) é o número definido no exercício 11.8. (Veja o exercício 11.10.)

E 11.12 Deduza o exercício 9.30 do exercício 11.8. Deduza o teorema de

Kőnig–Egerváry (exercício 10.7) do teorema de Tutte–Berge (exercício 11.11).

E 11.13 Seja G um grafo cúbico sem pontes. Mostre que G tem um empare-
lhamento perfeito. Mostre que nem todo grafo cúbico tem um emparelha-
mento perfeito.
2
O conjunto S serve de certificado da maximalidade do emparelhamento.
3
Combinação do teorema de Tutte (exercício 11.4) com um teorema de Claude Berge
( − ) publicado em 1958.
FEOFILOFF Emparelhamentos em grafos arbitrários 111

?! E 11.14 (D ECOMPOSIÇÃO DE G ALLAI –E DMONDS4 ) Seja G um grafo e D

o conjunto dos vértices que não são saturados por todos os emparelhaentos
máximos. (Veja o exercício 10.4.) Seja A o conjunto N(D). (Veja definição de
N no exercício 1.108.) Seja C o conjunto VG r (D ∪ A). Mostre que para todo
emparelhamento máximo M ∗ em G tem-se

2|M ∗ | = n(G) − c(G[D]) + |A| ,

onde c(H) denota o número de componentes do grafo H.

! E 11.15 (A LGORITMO DE E DMONDS5 ) Esboce um algoritmo eficiente que

encontre um emparelhamento máximo em qualquer grafo dado.

! E 11.16 Uma cobertura por arestas (= edge cover)6 de um grafo é um con-

junto F de arestas tal que todo vértice do grafo é ponta de algum elemento
de F . (Não confunda com o conceito de cobertura por vértices.) Invente um
algoritmo eficiente que produza uma cobertura por arestas mínima.

! E 11.17 (A LGORITMO DO E MPARELHAMENTO DE P ESO M ÁXIMO) Seja K

um grafo completo e π uma função de EK em {0, 1, 2, 3, . . .}. Para cada aresta
e do grafo,
P diremos que π(e) é o peso de e. O peso de um subconjunto F de
EK é e∈F π(e). Esboce um algoritmo para encontrar um emparelhamento
de peso máximo em K.

4
Publicada em 1963 e 1964 por Tibor Gallai ( − ) e em 1965 por Jack Edmonds.
5
Jack Edmonds.
6
Quem sabe eu deveria dizer “cobertura de vértices por arestas”.
FEOFILOFF Emparelhamentos em grafos arbitrários 112
Capítulo 12

Coloração de arestas

Uma coloração das arestas, ou recobrimento por emparelhamentos, de um

grafo é uma coleção de emparelhamentos que cobre o conjunto de arestas.
Mais precisamente, uma coloração das arestas de um grafo G é uma coleção
M1 , M2 , . . . , Mk de emparelhamentos tal que M1 ∪ M2 ∪ · · · ∪ Mk = EG .
(Podemos exigir que os emparelhamentos sejam disjuntos dois a dois; essa
disjunção é cômoda mas não é essencial.)
Se imaginarmos que cada emparelhamento Mi corresponde a uma cor,
poderemos dizer que uma coloração das arestas é uma atribuição de cores às
arestas do grafo tal que arestas adjacentes recebem cores diferentes.
Se M1 , . . . , Mk é uma coloração de arestas, dizemos que k é o número de
cores da coloração (mesmo que algum Mi seja vazio). Dizemos também que
esta é uma k-coloração. Uma coloração de arestas é mínima se o seu número
de cores é o menor possível, ou seja, se não existe outra que use menos cores.

P ROBLEMA DA C OLORAÇÃO DE A RESTAS: Encontrar uma coloração

mínima das arestas de um grafo dado.

O índice cromático (= chromatic index) de um grafo G é o número mínimo

de cores necessário para colorir as arestas de G. Este número é denotado por

χ 0 (G) .

(Não confunda com o número cromático χ(G) definido no capítulo 8.)

Exercícios
◦ E 12.1 Seja M1 , . . . , Mk uma coloração das arestas de um grafo. Mostre que
existe uma coloração M10 , . . . , Mk0 tal que os emparelhamentos M10 , . . . , Mk0 são
disjuntos dois a dois.

113
 FEOFILOFF Coloração de arestas 114

E 12.2 Um processo industrial consiste em um certo conjunto de tarefas.

Cada tarefa é executada por um operário em uma máquina e tem duração
de 1 dia. Cada operário está qualificado para operar apenas algumas das
máquinas. Quantos dias são necessários para completar o processo?

E 12.3 Uma escola pode ser representada por um grafo {U, W }-bipartido:
cada vértice em U é um professor, cada vértice em W é uma turma de alunos
e um professor é adjacente às turmas para as quais deve dar aulas. Uma
semana letiva é dividida em períodos (segunda-feira das 8h às 10h, segunda-
feira das 10h às 12h, etc.) e cada período é representado por uma cor. Uma
coloração das arestas do grafo é uma programação das aulas da semana.
Quantos períodos são necessários e suficientes para cumprir o programa de
aulas?1

E 12.4 Mostre que o problema da coloração das arestas é um caso particular

do problema da coloração de vértices (veja capítulo 8).

E 12.5 Exiba um grafo com duas colorações mínimas diferentes.

◦ E 12.6 Calcule uma coloração mínima das arestas de um grafo completo.

Calcule uma coloração mínima das arestas de um grafo bipartido completo.

◦ E 12.7 Calcule o índice cromático de um caminho e de um circuito. Calcule

o índice cromático de grafos com ∆ = 0, com ∆ = 1, e com ∆ = 2.

E 12.8 Calcule o índice cromático do grafo de Petersen.

E 12.9 Seja G um grafo cúbico dotado de circuito hamiltoniano. (Um circuito

C em G é hamiltoniano se VC = VG . Veja o capítulo 17.) Prove que χ 0 (G) = 3.

E 12.10 Mostre que χ 0 (G) ≥ m(G)/α 0 (G) para todo grafo G.

? E 12.11 Mostre que qualquer coloração das arestas de um grafo G usa pelo
0
χ ≥ menos ∆(G) cores. Em outras palavras, mostre que

χ 0 (G) ≥ ∆(G)

para todo grafo G. Mostre que isso é um caso particular da desigualdade

χ ≥ ω no exercício 8.38.
1
Este é o “problema da grade de horários” (timetabling problem).
FEOFILOFF Coloração de arestas 115

◦ E 12.12 Seja G um grafo r-regular com um número ímpar de vértices.

Mostre que χ 0 (G) > r.

E 12.13 Seja G um grafo r-regular com r ≥ 2. Suponha que G tem uma ponte
e mostre que χ 0 (G) > r. (Veja o exercício 9.18.)

E 12.14 Seja G um grafo r-regular com r ≥ 1. Suponha que G tem uma

articulação e mostre que χ 0 (G) > r.

E 12.15 Suponha que n(G) é ímpar e m(G) > ∆(G) (n(G) − 1)/2. Mostre que
χ 0 (G) > ∆(G).

E 12.16 Seja G um grafo r-regular, r ≥ 1, com um número ímpar de vértices.

Seja H um subgrafo obtido pela remoção de no máximo (r−1)/2 arestas de G.
Mostre que χ 0 (H) > ∆(H).

E 12.17 Mostre que o conjunto das arestas de toda árvore T pode ser colorido
com (apenas) ∆(T ) cores. (Compare com o exercício 12.11.)

E 12.18 Mostre que χ 0 (G) ≤ 2∆(G)−1 para todo grafo G. (Sugestão: indução
no número de arestas de G.)

E 12.19 (A LGORITMO DE COLORAÇÃO MINIMAL) Considere o seguinte al-

goritmo guloso de coloração das arestas de um grafo G. Cada iteração do
algoritmo começa com uma coleção M1 , . . . , Mj de emparelhamentos. Em
cada iteração,
escolha uma aresta e que não esteja em M1 ∪ · · · ∪ Mj ; se existe i tal que
Mi ∪ {e} é um emparelhamento então comece nova iteração com M1 ,
. . . , Mi−1 , Mi ∪ {e}, Mi+1 , . . . , Mj ; senão, comece nova iteração com a
coleção M1 , . . . , Mj , {e}.
Mostre que o algoritmo usa no máximo 2∆(G) − 1 emparelhamentos. Mostre
que o algoritmo usa no máximo 2χ 0 (G) − 1 emparelhamentos. O algoritmo
produz uma coloração mínima?

E 12.20 (A LGORITMO DE COLORAÇÃO MINIMAL) Considere o seguinte al-

goritmo guloso de coloração das arestas de um grafo G:
a j-ésima iteração começa com uma coleção M1 , M2 , . . . , Mj−1 de
emparelhamentos e calcula um emparelhamento maximal Mj no grafo
G − (M1 ∪ M2 ∪ · · · ∪ Mj−1 ).
Mostre que o algoritmo usa no máximo 2∆(G) − 1 cores. Mostre que o algo-
ritmo usa no máximo 2χ 0 (G) − 1 cores. O algoritmo produz uma coloração
mínima?
FEOFILOFF Coloração de arestas 116

E 12.21 (A LGORITMO) Considere o seguinte algoritmo de coloração das

arestas de um grafo G:
a j-ésima iteração começa com uma coleção M1 , M2 , . . . , Mj−1 de
emparelhamentos e calcula um emparelhamento máximo Mj no grafo
G − (M1 ∪ M2 ∪ · · · ∪ Mj−1 ).
Esse algoritmo produz uma coloração mínima?

E 12.22 (H EURÍSTICA DA TROCA DE CORES) Considere a seguinte heurís-

tica2 da “troca de cores em caminhos alternantes”, que tenta resolver o
problema da coloração de arestas:
No começo de cada iteração tem-se uma coloração parcial, ou seja, uma
coleção M1 , M2 , . . . , Mk de emparelhamentos disjuntos dois a dois. Seja
vw uma aresta ainda não colorida, isto é, uma aresta que não está em
M1 ∪ · · · ∪ Mk . Seja Mi uma cor “ausente” em v e seja Mj uma cor
“ausente” em w. Seja P o componente do grafo (VG , Mi ∪ Mj ) que
contém v. Troque Mi por Mi ⊕ EP . Em seguida, troque Mj por Mj ∪
{vw} e comece nova iteração.
Complete os detalhes e discuta a heurística. Ela resolve o problema da
coloração de arestas?

E 12.23 Mostre que todo grafo bipartido r-regular admite uma coloração das
arestas com apenas r cores. (Veja o exercício 10.29.)

E 12.24 Escolha 16 casas em um tabuleiro de xadrez 8-por-8 de forma que

cada linha e cada coluna do tabuleiro contenha exatamente duas das casas
escolhidas. Prove que é possível colocar 8 peões brancos e 8 pretos nas 16
casas escolhidas de tal forma que cada linha e cada coluna contenha contenha
exatamente um peão branco e um preto.

? E 12.25 Seja G um grafo bicolorável. Mostre que o conjunto de arestas de

G pode ser colorido com não mais que ∆(G) cores. (Veja a heurística 12.22 ou
o exercício 10.34.)

? E 12.26 (T EOREMA DEK ŐNIG3 ) Mostre que χ 0 (G) = ∆(G) para todo
grafo bicolorável G. (Segue dos exercícios 12.11 e 12.25.)

E 12.27 Exiba colorações mínimas das arestas dos grafos das figuras 10.1
e 10.2.
2
Wilf diz (em Algorithms and Complexity, Prentice-Hall, 1986) que heurísticas são
“methods that seem to work well in practice, for reasons nobody understands.”
3
Dénes Kőnig ( − ). (Veja verbete na Wikipedia.)
FEOFILOFF Coloração de arestas 117

 12.28 Sejam
E  M e N dois emparelhamentos de um grafo G. Suponha que
|M | − |N | ≥ 2. Mostre que existem emparelhamentos M 0 e N 0 tais que
   
M ∪ N = M 0 ∪ N 0 e |M 0 | − |N 0 | < |M | − |N |.

E 12.29 Seja G um grafo e ponha k = χ 0 (G).  Mostre que  existe uma k-colo-
ração M1 , M2 , . . . , Mk das arestas tal que |Mi | − |Mj | ≤ 1 para todo par

i,j de cores. Escreva uma “fórmula” para |Mi | em termos de m(G). (Veja
exercício 12.28.)

? E 12.30 (T EOREMA DE V IZING4 ) /Mostre que

χ 0 (G) ≤ ∆(G) + 1

para todo grafo G.5 (Se combinarmos isso com o exercício 12.11, poderemos
dizer que ∆ ≤ χ 0 ≤ ∆ + 1 para todo grafo.)

E 12.31 Mostre que a heurística de troca de pares de cores sugerido no

exercício 12.22 não é suficiente para demonstrar o teorema de Vizing (exercí-
cio 12.30).

E 12.32 (T EOREMA DE E RD ŐS AND W ILSON) Seja G 1 (n) a coleção de todos

os grafos em G(n) (veja seção 1.18) para os quais χ 0 = ∆. Mostre que

|G 1 (n)|
lim = 1.
n→∞ |G(n)|

D 12.33 (A LGORITMO) Invente um algoritmo rápido que calcule χ 0 (G) para

qualquer grafo G dado.

D 12.34 (A LGORITMO) Invente um algoritmo rápido que resolva o pro-

blema da coloração de arestas.

E 12.35 Seja X o conjunto dos vértices de um grafo G que têm grau ∆(G).
Mostre o seguinte: se G[X] é uma floresta então χ 0 (G) = ∆(G).
4
Publicado em 1964–1965 por Vadim G. Vizing ( − ). Descoberto, independen-
temente, por Ram Prakash Gupta em 1966.
5
É tentador comparar essa desigualdade com a desigualdade χ ≤ ∆+1 do exercício 8.30.
Mas as razões para as duas desigualdades são muito diferentes.
FEOFILOFF Coloração de arestas 118

Grafos planares
E 12.36 Prove que a seguinte afirmação equivale ao Teorema das Quatro
Cores (exercício 8.63): χ 0 (G) = 3 para todo grafo planar cúbico aresta-
biconexo G. (Compare com o exercício 12.13. Veja o exercício 8.69.)
Capítulo 13

Conectores e conjuntos acíclicos

Uma conector de um grafo G é qualquer subconjunto C de EG tal que o grafo

(VG , C) é conexo.1 Um conector C∗ é mínimo se não existe outro conector C
tal que |C| < |C∗ |.

P ROBLEMA DO C ONECTOR M ÍNIMO: Encontrar um conector mínimo

de um grafo dado.

Um conector Ĉ é minimal se não existe conector C tal que C ⊂ Ĉ. É

evidente que todo conector mínimo também é minimal. É um tanto surpre-
endente (diante do que acontece com coberturas por vértices, por exemplo)
que a recíproca seja verdadeira (veja exercício 13.5). Por isso, o problema do
conector mínimo é computacionalmente muito fácil.
Um conjunto F de arestas de um grafo G é acíclico se o grafo (VG , F ) não
tem circuitos, ou seja, se (VG , F ) é uma floresta. Um subconjunto acíclico F ∗
de EG é máximo se não existe subconjunto acíclico F tal que |F | > |F ∗ |.

P ROBLEMA DO C ONJUNTO A CÍCLICO M ÁXIMO: Dado um grafo G,

encontrar um subconjunto acíclico máximo de EG .

Uma subconjunto acíclico F̌ de EG é maximal se não existe subconjunto

acíclico F de EG tal que F ⊃ F̌ . É evidente que todo subconjunto acíclico
máximo também é maximal. É um tanto surpreendente que a recíproca seja
verdadeira (veja exercício 13.6). Por isso, o problema do subconjunto acíclico
máximo é computacionalmente muito fácil.
Uma árvore geradora, ou árvore abrangente (= spanning tree), de um
grafo G é qualquer subgrafo gerador de G que seja uma árvore.2 Uma árvore
geradora é essencialmente o mesmo que um conector minimal e um conjunto

1
Veja Schrijver [Sch03, p.855], por exemplo.
2
Uma árvore geradora de um grafo poderia ser chamada esqueleto do grafo. Em alemão,
por exemplo, diz-se Gerüst (= andaime).

119
FEOFILOFF Conectores e conjuntos acíclicos 120

acíclico minimal (veja o exercício 13.4).

Exercícios
◦ E 13.1 Mostre que um grafo tem um conector se e somente se ele é conexo.
Mostre que todo grafo tem um conjunto acíclico.

E 13.2 Seja C um conector minimal de um grafo. Mostre que C é um conjunto

acíclico maximal.

E 13.3 Seja G um grafo conexo e F um subconjunto acíclico maximal de EG .

Mostre que F é um conector minimal. (Veja o exercício 1.199.)

E 13.4 Seja C um conector minimal e F um conjunto acíclico maximal de um

grafo conexo G. Mostre que os grafos (VG , C) e (VG , F ) são árvores geradoras
de G.
Seja T uma árvore geradora de G. Mostre que ET é um conector minimal
e também um conjunto acíclico maximal de G.

? E 13.5 Mostre que todo conector minimal de um grafo G tem exatamente

n(G) − 1 arestas. (Veja exercício 1.228.) Deduza daí que todo conector
minimal é mínimo.

? E 13.6 Mostre que todo conjunto acíclico maximal de um grafo G tem

exatamente n(G) − c(G) arestas, sendo c(G) o número de componentes de G.
(Veja exercício 1.231.) Deduza daí que todo conjunto acíclico maximal é
máximo.

E 13.7 (A LGORITMO) Construa um algoritmo eficiente que receba um grafo

G e devolva um conector mínimo de G (ou uma prova de que G não é
conexo).
Construa um algoritmo eficiente que receba um grafo G e devolva um
subconjunto acíclico máximo de EG .

? E 13.8 (T ROCA DE ARESTAS) Seja C um conector minimal de um grafo G

e b um elemento de EG r C. Mostre que existe a em C tal que

(C ∪ {b}) r {a}

é um conector minimal de G.
FEOFILOFF Conectores e conjuntos acíclicos 121

E 13.9 Seja a uma aresta em um conector minimal C de um grafo G. Dê uma

condição necessária e suficiente para que exista uma aresta b em EG r C tal
que (C r {a}) ∪ {b} seja um conector. (Compare com o exercício 13.8.)

E 13.10 (A LGORITMO) Suponha que cada aresta e de um grafo G tem um

“peso” numérico
P π(e) ≥ 0. O peso de qualquer conjunto A de arestas é então
o número e∈A π(e).
Construa um algoritmo que encontre um conector de G que tenha peso
mínimo.3

3
Os célebres algoritmos de J. B. Kruskal e R. C. Prim resolvem o problema. Ambos usam
uma estégia “gulosa”. Eles estão entre os mais antigos e mais conhecidos algoritmos gulosos
da teoria dos grafos. A prova da correção desses algoritmos depende do exercício 13.8.
FEOFILOFF Conectores e conjuntos acíclicos 122
Capítulo 14

Caminhos e circuitos mínimos

Um caminho é mais curto que outro se o comprimento do primeiro é menor

que o do segundo. Um caminho P∗ é mínimo se nenhum caminho mais curto
tem os mesmos extremos que P∗ .

P ROBLEMA DO C AMINHO M ÍNIMO: Dados vértices v e w de um grafo,

encontrar um caminho mínimo com extremos v e w.

A distância entre dois vértices v e w é o comprimento de um caminho

mínimo com extremos v e w.1 (Se não existe caminho algum com esses
extremos, a distância não está definida.) A distância entre vértices v e w de
um grafo G será denotada por

distG (v, w) .

Se G estiver subentendido, diremos simplesmente dist(v, w).

Um circuito é mínimo se o grafo não contém um circuito mais curto. A
cintura (= girth) de um grafo é o comprimento de um circuito mínimo no
grafo. (Se um grafo não tem circuito algum, sua cintura não está definida.)

Exercícios
E 14.1 No grafo da figura 14.1, calcule a distância entre o vértice x e cada um
dos outros vértices. Em seguida, exiba um caminho mínimo entre x e y.

◦ E 14.2 Seja k a distância entre dois vértices v e w num grafo. Mostre que
(1) existe um caminho de comprimento k de v a w e (2) não existe caminho
de comprimento menor que k de v a w. Mostre a recíproca: se (1) e (2) valem
então a distância entre v e w é k.
1
A expressão “distância mínima” é redundante e deve ser evitada.

123
FEOFILOFF Caminhos e circuitos mínimos 124

y
Figura 14.1: Encontre um caminho mínimo en-
tre x e y. Veja o exercício 14.1.

E 14.3 Suponha que v0 v1 · · · vk é um caminho mínimo (dentre os que têm

extremos v0 a vk ). Prove que

dist(v0 , vj ) = j

para todo índice j.

? E 14.4 (D ESIGUALDADE T RIANGULAR) Seja (x, y, z) um terno de vértices

de um grafo conexo. Prove que

dist(x, y) + dist(y, z) ≥ dist(x, z) .

E 14.5 Seja r um vértice e uv uma aresta de um grafo conexo. Mostre que

|dist(r, u) − dist(r, v)| ≤ 1 .

E 14.6 (A LGORITMO DE B USCA EM L ARGURA2 ) Construa um algoritmo efi-

ciente que receba dois vértices v e w de um grafo e calcule a distância entre
v e w. Construa um algoritmo eficiente que encontre um caminho mínimo
entre dois vértices dados.

E 14.7 (Á RVORE DAS D ISTÂNCIAS) Seja r um vértice de um grafo conexo G.

Mostre que G tem uma árvore geradora T tal que

distG (r, x) = distT (r, x)

para todo vértice x (ou seja, a distância entre r e x em G é igual à distância

entre r e x em T ).

◦ E 14.8 É verdade que todo grafo conexo G tem uma árvore geradora T tal
que distG (u, v) = distT (u, v) para todo par u,v de vértices?
2
Breadth-First Search Algorithm.
FEOFILOFF Caminhos e circuitos mínimos 125

E 14.9 A excentricidade (= eccentricity) de um vértice v num grafo é o número

exc(v) := maxw∈V dist(v, w). Um centro é um vértice de excentricidade
mínima. O raio (= radius) do grafo é a excentricidade de um centro.
Mostre que toda árvore tem no máximo dois centros e se tiver dois então
eles são adjacentes.

E 14.10 O grafo de Heawood3 tem conjunto de vértices {0, 1, 2, . . . , 13}. Cada

vértice i é vizinho de (i + 1) mod 14 e de (i + 13) mod 14.4 Além disso, cada
i é vizinho de um terceiro vértice, que depende da paridade de i: se i é par
então ele é vizinho de (i + 5) mod 14 e se i é ímpar então ele é vizinho de
(i + 9) mod 14.
Faça uma figura do grafo de Heawood. Encontre um circuito de compri-
mento mínimo no grafo.

E 14.11 Mostre que todo grafo conexo com m ≥ 3n/2 tem um circuito de
comprimento ≤ c log n para alguma constante c.

E 14.12 (A LGORITMO) Construa um algoritmo que calcule a cintura de

qualquer grafo dado. Construa um algoritmo que encontre um circuito
mínimo em qualquer grafo dado. (Veja o exercício 14.6.)

Restrições de paridade
Dizemos que um circuito ou caminho é ímpar se o seu comprimento é
um número ímpar. Analogamente, um circuito ou caminho é par se o seu
comprimento é um número par.
A cintura ímpar de um grafo é o comprimento de um circuito ímpar
mínimo no grafo. A cintura par é definida analogamente.

E 14.13 Seja r um vértice de um grafo conexo G. Sejam u e v dois vértices

adjacentes tais que dist(r, u) = dist(r, v). Mostre que G tem um circuito ímpar
de comprimento não superior a dist(r, u)+dist(r, v)+1. (Veja o exercício 14.3.)

E 14.14 Seja r um vértice de um grafo conexo G. Sejam x e y dois vértices

adjacentes tais que dist(r, x) e dist(r, y) têm a mesma paridade (ou seja, ambos
são pares ou ambos ímpares). Mostre que G tem um circuito ímpar.

3
Percy John Heawood ( − ).
4
A expressão “i mod j” denota o resto da divisão de i por j.
FEOFILOFF Caminhos e circuitos mínimos 126

E 14.15 (Recíproca de 14.13) Seja r um vértice de um grafo conexo G. Seja O

um circuito ímpar em G. Mostre que O tem uma aresta xy tal que distG (r, x) =
distG (r, y). (Veja exercício 14.5.)

E 14.16 Seja r um vértice de um grafo conexo G. Mostre que G é bicolorável

se e somente se dist(r, u) 6= dist(r, v) para toda aresta uv. (Veja os exercí-
cios 14.13 e 14.15.)

E 14.17 Use o conceito de distância para mostrar que um grafo é bicolorável

se e somente se não tem circuitos ímpares. (Compare com o exercício 4.15.
Veja o exercício 14.14.)

E 14.18 (A LGORITMO) Construa um algoritmo que calcule a cintura ímpar

de qualquer grafo dado. Construa um algoritmo que encontre um circuito
ímpar mínimo em qualquer grafo dado. (Veja os exercícios 14.13, 14.15 e 14.6.
Compare com o exercício 1.123.)

! E 14.19 (A LGORITMO) Construa um algoritmo que calcule a cintura par de

qualquer grafo dado. Construa um algoritmo que encontre um circuito par
mínimo em qualquer grafo dado.

! E 14.20 (A LGORITMO) Dados dois vértices u e v de um grafo G, encontre

um caminho de comprimento mínimo na coleção de todos os caminhos de
comprimento par que têm extremos u e v.

! E 14.21 (A LGORITMO) Dados dois vértices u e v de um grafo G, encontre

um caminho de comprimento mínimo na coleção de todos os caminhos de
comprimento ímpar que têm extremos u e v.

Grafos aleatórios
E 14.22 O diâmetro (= diameter) de um grafo G é o número max(u,v) dist(u, v),
sendo o máximo tomado sobre todos os pares (u, v) de vértices. Prove que o
diâmetro de quase todo grafo em G(n) (veja a seção 1.18) não passa de 2.
Capítulo 15

Fluxo

Um fluxo (= flow) em um grafo é uma coleção de caminhos sem arestas em

comum.1 (Acho que “macarronada” seria um boa alternativa para “fluxo”!)
Mais precisamente, um fluxo é uma coleção F de caminhos tal que

EP ∩ EQ = ∅

para cada par (P, Q) de elementos distintos de F.

Dados vértices a e b de um grafo G, diremos que um fluxo F liga a a b
se cada caminho em F tem um extremo em a e outro em b Podemos dizer
também, nessas circunstâncias, que F é um fluxo entre a e b ou de a a b. (Um
fluxo de b a a é essencialmente o mesmo que um fluxo de a a b.)
Um fluxo F de a a b é máximo se |F| ≥ |F 0 | para todo fluxo F 0 de a a b.

P ROBLEMA DO F LUXO M ÁXIMO: Dados dois vértices a e b de um

grafo G, encontrar um fluxo máximo de a a b.

Um conjunto C de arestas separa a de b se todo caminho de a a b tem

pelo menos uma aresta em C. Conforme o exercício 15.4, todo conjunto que
separa a de b é, essencialmente, um corte ∂(X) tal que X contém a mas não
contém b.

Exercícios
E 15.1 Considere o grafo do bispo num tabuleiro 3-por-3. Seja a a casa no
canto superior esquerdo e b a casa no canto superior direito. Encontre um
fluxo máximo de a a b.

E 15.2 Considere o grafo da dama num tabuleiro 3-por-3. Seja a a casa no

1
Este uso da palavra “fluxo” não é ortodoxo. Na maioria dos livros, a palavra é usada
de maneira um pouco diferente.

127
FEOFILOFF Fluxo 128

canto superior esquerdo e b a casa no meio do tabuleiro. Encontre um fluxo

máximo de a a b.

E 15.3 Considere o grafo do cavalo num tabuleiro 3-por-3. Seja a a primeira

casa da primeira linha e b a última casa da segunda linha. Encontre um fluxo
máximo de a a b.

E 15.4 (S EPARADORES VERSUS CORTES) Sejam a e b dois vértices de um

grafo G. Seja X um subconjunto de VG que contém a mas não contém b.
Mostre que ∂(X) separa a de b.
Seja C um conjunto de arestas que separa a de b. Mostre que existe um
subconjunto X de VG tal que a ∈ X, b ∈
/ X e ∂(X) ⊆ C.

◦ E 15.5 Sejam a e b dois vértices de um grafo. Suponha que existe um fluxo

de cardinalidade k entre a e b. Mostre que todo conjunto de arestas que separa
a de b tem pelo menos k arestas.2

? E 15.6 (F LUXO VERSUS CORTE) Sejam a e b dois vértices de um grafo G.

Suponha que todo corte que separa a de b tem pelo menos k arestas. Mostre
que um fluxo de cardinalidade k liga a a b em G. (Compare com os exercí-
cios 15.5 e 1.208.)

? E 15.7 (T EOREMA M ENGER3 ) Sejam a e b dois vértices de um grafo.

DE
∗
Seja F um fluxo máximo dentre os que ligam a a b. Seja C∗ um conjunto
mínimo de arestas dentre os que separam a de b. Mostre que

|F ∗ | = |C∗ | .

(Esta é uma combinação dos exercícios 15.5 e 15.6.4 )

◦ E 15.8 Sejam a e b dois vértices de um grafo G. Suponha que todo conjunto

que separa a de b tem pelo menos 2 arestas. Seja P um caminho em G com
extremos a e b. É verdade que G − EP tem um caminho com extremos a e b?

E 15.9 (A LGORITMO) Construa um algoritmo que receba dois vértices a e b

de um grafo G e devolva um fluxo F de a a b e um conjunto X que contém a
mas não contém b tais que |F| = d(X).
2
Assim, um corte com k arestas é um certificado de que não existe fluxo de tamanho
maior que k.
3
Karl Menger ( − ). O “g” tem som de “gato” e não de “gente”.
4
Trata-se também de um caso especial do Teorema do Fluxo Máximo e Corte Mínimo de
Ford, Fulkerson, Elias, Feinstein e Shannon.
FEOFILOFF Fluxo 129

E 15.10 Seja G um grafo e sejam A e B dois subconjuntos não vazios de VG

tais que A ∩ B = ∅. Uma barreira é qualquer subconjunto F de EG tal que
todo caminho de A a B tem uma aresta em F .
Suponha que toda barreira tem pelo menos k arestas. Mostre que existe
uma coleção de k caminhos de A a B tal que nenhuma aresta pertence a dois
dos caminhos.

Grafos aresta-k-conexos
A aresta-conexidade de um grafo G é a cardinalidade do menor subconjunto
C de EG tal que G − C é desconexo (ou seja, tem dois ou mais componentes).
A aresta-conexidade de G é denotada por
κ 0 (G) .
Esta definição de conexidade não se aplica ao caso em que G tem um só
vértice, pois nesse caso não existe C tal que G−C é desconexo. Convenciona-
se, nesse caso, dizer que κ 0 (K1 ) = 1. (Talvez ∞ faça mais sentido.)
Dizemos que um grafo G é aresta-k-conexo (= k-edge-connected) para todo
k ≤ κ 0 (G). Assim, um grafo aresta-1-conexo é o mesmo que um grafo conexo
e um grafo aresta-2-conexo é o mesmo que um grafo aresta-biconexo (veja
seção 1.13).

◦ E 15.11 Calcule a aresta-conexidade de um caminho. Calcule a aresta-

conexidade de um circuito.

E 15.12 Calcule a aresta-conexidade de um grafo completo com n ≥ 2 vérti-

ces.

E 15.13 Seja G um grafo aresta-k-conexo, com k > 0. Seja C um conjunto de

k arestas. Mostre que G − C tem no máximo 2 componentes.

◦ E 15.14 Seja G um grafo com dois ou mais vértices e k um número natural.

Mostre que G é aresta-k-conexo se e somente se G − C é conexo para todo
subconjunto C de EG tal que |C| < k.

E 15.15 Seja G um grafo com dois ou mais vértices e k um número natural.

Mostre que G é aresta-k-conexo se e somente se d(X) ≥ k para todo conjunto
X de vértices tal que ∅ ⊂ X ⊂ VG . (Veja o exercício 15.4.)

E 15.16 Seja Bt um dos componentes do grafo do bispo num tabuleiro t-por-t.

Calcule κ 0 (Bt ) para t = 2, 3, 4.
FEOFILOFF Fluxo 130

E 15.17 Seja Dt o grafo da dama num tabuleiro t-por-t. Calcule κ 0 (Dt ) para
t = 2, 3, 4.

E 15.18 Seja C4 o grafo do cavalo num tabuleiro 4-por-4. Calcule κ 0 (C4 ).

? E 15.19 Seja G um grafo com dois ou mais vértices. Mostre (a partir do

teorema de Menger, exercício 15.7) que G é aresta-k-conexo se e somente se
cada par de seus vértices é ligado por um fluxo de cardinalidade k.

? E 15.20 Mostre que κ 0 (G) ≤ δ(G) para todo grafo G com dois ou mais
vértices. Mostre que a desigualdade pode ser estrita.

E 15.21 Seja G um grafo com dois ou mais vértices tal que δ(G) ≥
(n(G) − 1)/2. Mostre que κ 0 (G) = δ(G).

◦ E 15.22 Seja G um grafo aresta-k-conexo. Mostre que m(G) ≥ k n(G)/2.

E 15.23 Seja G um grafo aresta-k-conexo. Sejam A e B dois subconjuntos

não vazios de VG tais que A ∩ B = ∅. Mostre que existe um fluxo F de
cardinalidade k em G tal que cada caminho em F tem um extremo em A e
outro em B.

E 15.24 Seja G um grafo aresta-(2k−1)-conexo. Mostre que G tem um sub-

grafo bipartido gerador H que é aresta-k-conexo.
Capítulo 16

Fluxo internamente disjunto

Um vértice de um caminho é considerado interno se for diferente da origem

e do término do caminho. Dois caminhos em um grafo são internamente
disjuntos se não têm vértices internos em comum, ou seja, se cada vértice do
grafo é interno a no máximo um dos dois caminhos.
Dados vértices a e b de um grafo, um fluxo internamente disjunto é uma
coleção de caminhos de a a b que são dois a dois internamente disjuntos.
Portanto,
VP ∩ VQ = {a, b}
para cada par (P, Q) de caminhos da coleção. Diremos que uma tal coleção
liga a a b.

P ROBLEMA DO FLUXO INTERNAMENTE DISJUNTO MÁXIMO: Dados

dois vértices a e b de um grafo, encontrar um fluxo internamente
disjunto máximo ligando a a b.

Para evitar discussões inúteis, é melhor restringir o problema ao caso em

a e b não são adjacentes.
Um separador de (a, b) é qualquer conjunto S de vértices tal que a e b
estão em componentes distintas de G − S. Em outras palavras, um separador
de (a, b) é qualquer subconjunto S de VG r {a, b} tal que todo caminho com
extremos a e b tem pelo menos um vértice em S. (É claro que se a e b são
adjacentes então não existe separador de (a, b).)

Exercícios
E 16.1 Considere o grafo do bispo num tabuleiro 4-por-4. Seja a a primeira
casa da primeira linha e b a última casa da última linha. Encontre um fluxo
internamente disjunto máximo ligando a a b. Repita o exercício com b sendo
a terceira casa da primeira linha.

131
FEOFILOFF Fluxo internamente disjunto 132

E 16.2 Considere o grafo da dama num tabuleiro 3-por-3. Seja a a casa no

canto superior esquerdo e b a casa no meio do tabuleiro. Encontre um fluxo
internamente disjunto máximo ligando a a b.

E 16.3 Considere o grafo do cavalo num tabuleiro 3-por-3. Seja a a primeira

casa da primeira linha e b a última casa da segunda linha. Encontre um fluxo
internamente disjunto máximo ligando a a b.

◦ E 16.4 Seja v uma articulação em um grafo G e sejam a e b vértices em

componentes distintos de G − v. Verifique que {v} separa a de b.

◦ E 16.5 Critique a seguinte definição alternativa de separador: “Um separa-

dor de (a, b) é um conjunto S de vértices tal que todo caminho com extremos
a e b tem pelo menos um vértice em S.”

◦ E 16.6 Sejam a e b dois vértices não adjacentes de um grafo. Suponha que

um fluxo internamente disjunto de a a b tem k caminhos. Mostre que todo
separador de (a, b) tem pelo menos k vértices.1 (Que acontece se a e b forem
adjacentes?)

? E 16.7 (F LUXO VERSUS SEPARADOR) Sejam a e b dois vértices não adjacen-

tes de um grafo G. Suponha que todo separador de (a, b) tem pelo menos k
vértices. Mostre que G tem um fluxo internamente disjunto de tamanho k
ligando a a b. (Compare com os exercícios 16.6 e 1.218.)

? E 16.8 (T EOREMA DE M ENGER2 ) Sejam a e b dois vértices não adjacentes

de um grafo. Seja P ∗ um fluxo internamente disjunto máximo dentre todos
os que ligam a a b. Seja S∗ um separador mínimo de (a, b). Mostre que

|P ∗ | = |S∗ | .

(Esta é uma combinação dos exercícios 16.6 e 16.7.)

? E 16.9 Deduza o teorema de Kőnig–Egerváry (exercício 10.7) do teorema

de Menger (exercício 16.8).

E 16.10 (L EMA DO LEQUE) Seja a um vértice de um grafo G e seja B um

subconjunto não vazio de VG r {a}. Um leque é uma coleção de caminhos
de a a B tal que VP ∩ VQ = {a} para cada par (P, Q) de caminhos da coleção.

1
Assim, um separador com k vértices é um certificado de inexistência de um fluxo
internamente disjunto de tamanho maior que k.
2
Karl Menger ( − ). Pronuncie o “g” como “gato” e não como “gente”.
FEOFILOFF Fluxo internamente disjunto 133

Uma barreira é qualquer subconjunto S de VG r {a} tal que todo caminho de

a a B tem um vértice em S.
Suponha que todo barreira tem k ou mais vértices. Mostre que existe um
leque com k caminhos.

E 16.11 Seja G um grafo e sejam A e B dois subconjuntos não vazios de VG .

Uma coleção de caminhos é disjunta se VP ∩ VQ = ∅ para cada par (P, Q) de
caminhos da coleção. Uma barreira é qualquer subconjunto S de VG tal que
todo caminho de A a B tem um vértice em S.
Suponha que toda barreira tem pelo menos k vértices. Mostre que existe
uma coleção disjunta de k caminhos de A a B.

Conexidade
A conexidade de um grafo G é a cardinalidade do menor subconjunto S de
VG tal que G − S é desconexo (ou seja, tem dois ou mais componentes). A
conexidade de um grafo G é denotada por

κ(G) .

Esta definição não se aplica quando G é completo, pois nesse caso não existe
S tal que G − S é desconexo.3 Convenciona-se, então, que κ(Kn ) = n − 1 para
todo n ≥ 2 e κ(K1 ) = 1.
Dizemos que um grafo G é k-conexo (= k-connected) para todo k ≤ κ(G).
Assim, um grafo 1-conexo é o mesmo que um grafo conexo e um grafo 2-
conexo é o mesmo que um grafo biconexo (veja seção 1.14).

◦ E 16.12 Qual a conexidade de um caminho? Qual a conexidade de um

circuito?

◦ E 16.13 Seja G um grafo completo com n ≥ 2 vértices e e uma de suas

arestas. Calcule a conexidade de G − e.

E 16.14 Seja G um grafo não completo e k um número natural. Mostre que G

é k-conexo se e somente se G − S é conexo para todo subconjunto S de VG tal
que |S| < k.

E 16.15 Seja Bt um dos componentes do grafo do bispo num tabuleiro t-por-t.

Calcule κ(Bt ) para t = 2, 3, 4.
3
Poderíamos dizer, talvez, que κ(G) é ∞ nesse caso.
FEOFILOFF Fluxo internamente disjunto 134

E 16.16 Seja Dt o grafo da dama num tabuleiro t-por-t. Calcule κ(Dt ) para
t = 2, 3, 4.

E 16.17 Seja C4 o grafo do cavalo num tabuleiro 4-por-4. Calcule κ(C4 ).

E 16.18 Seja G um circuito de comprimento 6. Calcule a conexidade de G.

E 16.19 Calcule a conexidade do grafo de Petersen.

? E 16.20 Seja G um grafo não completo. Mostre (a partir do teorema de

Menger, exercício 16.8) que G é k-conexo se e somente se cada par de vér-
tices não adjacentes de G é ligado por um fluxo internamente disjunto de
tamanho k.

◦ E 16.21 Mostre que todo grafo k-conexo com dois ou mais vértices é aresta-
k-conexo. Mostre que a recíproca não é verdadeira, ou seja, que nem todo
grafo aresta-k-conexo com dois ou mais vértices é k-conexo.

? E 16.22 Mostre que κ(G) ≤ κ 0 (G) para todo grafo G com dois ou mais
vértices. Mostre que a desigualdade pode ser estrita.

E 16.23 Mostre que κ(G) = κ 0 (G) para todo grafo cúbico G.

E 16.24 Seja k um número natural maior que 1 e G um grafo k-conexo com

n(G) ≥ 2k. Mostre que G tem um circuito com 2k ou mais vértices.

E 16.25 (T EOREMA DE D IRAC4 ) Seja k um número natural maior que 1 e G

um grafo k-conexo. Seja Z um conjunto de k vértices de G. Mostre que algum
circuito em G contém todos os vértices de Z.

4
Publicado em 1952 por Gabriel Andrew Dirac ( − ).
Capítulo 17

Circuitos e caminhos
hamiltonianos

Um circuito num grafo é máximo se o grafo não contém um circuito mais

comprido. A circunferência de um grafo é o comprimento de um circuito de
comprimento máximo no grafo.

P ROBLEMA DO C IRCUITO M ÁXIMO: Encontrar um circuito máximo

num grafo dado.

O problema de encontrar um caminho máximo é formulado de maneira

análoga. Um caminho num grafo é máximo se o grafo não contém um
caminho mais comprido.
Um circuito é hamiltoniano1 se contém todos os vértices do grafo. É
evidente que todo circuito hamiltoniano é um circuito máximo. O problema
do circuito máximo tem a seguinte especialização óbvia:

P ROBLEMA DO C IRCUITO H AMILTONIANO: Decidir se um dado grafo

tem um circuito hamiltoniano.

O conceito de caminho hamiltoniano e o problema do caminho hamilto-

niano são definidos de maneira análoga.
Alguns dos exercícios abaixo envolvem a condição “δ(G) ≥ k”. Convém
lembrar que esta condição equivale a “|N(v)| ≥ k para todo vértice v”, uma
vez que |N(v)| = d(v) para todo vértice v.

1
Referência a William Rowan Hamilton ( − ). (Veja verbete na Wikipedia.) Teria
sido mais justo homenagear o inglês Thomas P. Kirkman ( − ). (Veja verbete na
Wikipedia.)

135
FEOFILOFF Circuitos e caminhos hamiltonianos 136

Exercícios
◦ E 17.1 É verdade que todo grafo completo tem um circuito hamiltoniano?

◦ E 17.2 Dê condições necessárias e suficientes para que um grafo bipartido

completo tenha um circuito hamiltoniano.

E 17.3 Encontre um circuito máximo em cada um dos grafos da figura 17.1.

Figura 17.1: Encontre um circuito máximo. Veja exercício 17.3.

E 17.4 Encontre um circuito máximo no grafo de Petersen. Encontre um

caminho máximo no grafo de Petersen.

E 17.5 Prove que para todo k ≥ 2 o grafo Qk tem um circuito hamiltoniano.

(Sugestão: Use indução em k.)

E 17.6 Dê uma condição necessária e suficiente para que uma grade tenha
um circuito hamiltoniano.

E 17.7 Encontre um circuito hamiltoniano no grafo do cavalo t-por-t. (Veja

verbete na Wikipedia e artigo no Wolfram MathWorld.)

◦ E 17.8 Seja G um grafo cúbico dotado de um circuito hamiltoniano. Mostre

que χ 0 (G) = 3.

E 17.9 (A LGORITMO) Discuta o seguinte algoritmo para o problema do cir-

cuito hamiltoniano: Ao receber um grafo G, gere uma lista de todas as per-
mutações de VG ; descarte as permutações que não correspondem a circuitos
hamiltonianos; devolva qualquer uma das permutações restantes.

E 17.10 Mostre que todo grafo G tem um caminho de comprimento pelo

menos δ(G). (Veja exercício 1.125.)
FEOFILOFF Circuitos e caminhos hamiltonianos 137

E 17.11 Mostre que todo grafo G tem um circuito com δ(G) + 1 ou mais
vértices, desde que δ(G) > 1. (Veja exercício 1.128 na seção 1.9.)

E 17.12 Mostre que todo grafo G tem um caminho com pelo menos χ(G)
vértices, sendo χ(G) o número cromático (veja capítulo 8) de G. (Veja o
exercício 8.47).

E 17.13 Sejam P ∗ e Q∗ dois caminhos máximos em um grafo conexo G.

Mostre que P ∗ e Q∗ têm um vértice em comum. (Veja o exercício 1.170.)

◦ E 17.14 Seja G um grafo dotado de circuito hamiltoniano. Mostre G não

tem pontes. Mostre que G não tem articulações.

E 17.15 Seja G um grafo dotado de circuito hamiltoniano. Mostre que toda

aresta de G pertence a um circuito.

E 17.16 Seja G um grafo {U, W }-bipartido tal que |U | =

6 |W |. Prove que G não
tem circuito hamiltoniano. (Outra maneira de formular a questão: para todo
grafo {U, W }-bipartido dotado de circuito hamiltoniano tem-se |U | = |W |.)

E 17.17 Suponha que um grafo G tem um conjunto estável com mais que
n(G)/2 vértices. Mostre que G não tem circuito hamiltoniano.
É verdade que todo grafo G com α(G) ≤ n(G)/2 tem um circuito hamil-
toniano?

E 17.18 (C ONDIÇÃO NECESSÁRIA) Seja S um conjunto de vértices de um

grafo G. Suponha que |S| < n(G) e

c(G − S) > |S| + 1 ,

sendo c(G − S) o número de componentes de G − S. Mostre que G não tem

caminho hamiltoniano. (Veja exercício 1.174.)

? E 17.19 (C ONDIÇÃO NECESSÁRIA) Seja S um conjunto de vértices de um

grafo G. Suponha que 0 < |S| < n(G) e

c(G − S) > |S| ,

sendo c(G − S) o número de componentes de G − S. Mostre que G não tem

circuito hamiltoniano. (Veja exercício 1.175.) Outra maneira de formular a
questão: Se G tem um circuito hamiltoniano então c(G − S) ≤ |S| para todo
subconjunto próprio e não vazio S de VG .
Mostre que a condição “c(G − S) > |S|” é uma generalização dos exercí-
cios 17.14, 17.16 e 17.17.
FEOFILOFF Circuitos e caminhos hamiltonianos 138

E 17.20 Suponha que um grafo G satisfaz a desigualdade c(G − S) ≤ |S| para

todo conjunto S de vértices tal que 0 < |S| < n(G). É verdade que G tem um
circuito hamiltoniano?

D 17.21 (C ONDIÇÃO SUFICIENTE : CONJECTURA DE C HVÁTAL2 ) Seja G um

grafo tal que c(G − S) ≤ |S|/2 para todo subconjunto S de VG tal que 2 ≤
|S| < n(G). Prove que G tem um circuito hamiltoniano. (Compare com o
exercício 17.19.)

E 17.22 É verdade que existe um número natural k tal que todo grafo k-
conexo (veja página 133) tem um circuito hamiltoniano? (Compare com os
exercícios 17.19 e 17.35.)

E 17.23 Seja G um grafo conexo e O um circuito em G tal que, para todo

aresta e de O, o grafo O − e é um caminho máximo em G. Prove que G tem
um circuito hamiltoniano.

E 17.24 Seja G um grafo com 4 ou mais vértices tal que δ(G) ≥ n(G) − 2.
Mostre que G tem um circuito hamiltoniano.

E 17.25 Seja G um grafo com n vértices e m arestas. Suponha que m ≥ 2 +

1
2
(n − 1)(n − 2). Prove que G tem um circuito hamiltoniano.

? E 17.26 (C ONDIÇÃO SUFICIENTE : T EOREMA DE D IRAC3 ) Seja G um grafo

com 3 ou mais vértices que satisfaz a condição

δ(G) ≥ n(G)/2 .

Mostre que G tem um circuito hamiltoniano. (Sugestão: Use o exercício

1.129.)

? E 17.27 (G ENERALIZAÇÃO DO TEOREMA DE D IRAC) Seja G um grafo com

3 ou mais vértices que satisfaz a condição

dG (u) + dG (v) ≥ n(G)

para todo par (u, v) de vértices distintos não adjacentes. Mostre que G tem
um circuito hamiltoniano. (Sugestão: Use o exercício 1.129.)
2
Proposta por Vášek Chvátal em 1971.
3
Publicado em 1952 por Gabriel Andrew Dirac ( − ).
FEOFILOFF Circuitos e caminhos hamiltonianos 139

E 17.28 Seja G um grafo e {V1 , V2 , V3 } uma partição de VG em partes não

vazias. Suponha que (1) cada vértice em V1 é adjacente a todos os vértices de
V2 ∪ V3 e (2) cada vértice de V2 é adjacente a todos os vértices de V3 .
Prove que se |V2 | = 2|V1 | e |V3 | = 3|V1 | então G tem um circuito hamilto-
niano. Prove que se |V2 | = 2|V1 | e |V3 | = 3|V1 | + 1 então G não tem circuito
hamiltoniano.

E 17.29 Seja A um algoritmo que decide se um grafo dado tem um circuito

hamiltoniano. Use A para formular um algoritmo que decide se um grafo
dado tem um caminho hamiltoniano.
Seja B um algoritmo que decide se um grafo dado tem um caminho
hamiltoniano. Use B para formular um algoritmo que decide se um grafo
dado tem um circuito hamiltoniano.

D 17.30 (C ONDIÇÃO NECESSÁRIA E SUFICIENTE ?) Descubra uma condição

necessária e suficiente para que um grafo tenha um circuito hamiltoniano.
Descubra uma condição necessária e suficiente para que um grafo tenha um
caminho hamiltoniano.

D 17.31 (A LGORITMO) Invente um algoritmo rápido que receba um grafo e

devolva um circuito hamiltoniano no grafo (ou constate que o grafo não tem
um tal circuito).

D 17.32 (A LGORITMO) Invente um algoritmo rápido que encontre um cir-

cuito máximo em qualquer grafo que não seja uma floresta.4

D 17.33 (A LGORITMO) Invente um algoritmo rápido que receba um grafo

e devolva um caminho hamiltoniano no grafo (ou constate que o grafo não
tem um tal caminho).5

D 17.34 (P ROBLEMA DO C AIXEIRO V IAJANTE6 ) Seja K um grafo completo

e ϕ uma função de EK em {0, 1, 2, 3, . . .}. Para cada arestaP
e do grafo, diremos
que ϕ(e) é o custo de e. O custo de um subgrafo H de K é e∈EH ϕ(e). Invente
um algoritmo para encontrar um circuito hamiltoniano de custo mínimo
em K.7
4
Um tal algoritmo ainda não foi encontrado.
5
Um tal algoritmo ainda não foi encontrado.
6
Traveling Salesman Problem ou TSP.
7
O problema é NP-difícil. Veja os livros de Garey–Johnson [GJ79], Harel [Har92] e
Sipser [Sip97]. Veja o sítio The Traveling Salesman Problem, mantido por Bill Cook na Georgia
Tech University.
FEOFILOFF Circuitos e caminhos hamiltonianos 140

Grafos hamiltonianos planares

! E 17.35 (T EOREMA DE T UTTE8 ) Mostre que todo grafo planar 4-conexo
(veja página 133) tem um circuito hamiltoniano. (Compare com o exercí-
cio 17.22.)

E 17.36 Mostre que nem todo grafo planar 3-conexo (veja página 133) tem
circuito hamiltoniano.

D 17.37 (C ONJECTURA DE B ARNETTE) Prove ou desprove a seguinte con-

jectura: Todo grafo planar bicolorável 3-regular 3-conexo (veja página 133)
tem um circuito hamiltoniano.9

8
William T. Tutte ( − ). (Veja verbete na Wikipedia.)
9
D. Barnette propôs a conjectura em 1970.
Capítulo 18

Coberturas por circuitos

Ums cobertura, ou recobrimento, por circuitos (=Scircuit cover) de um grafo

G é qualquer coleção O de circuitos de G tal que O∈O EO = EG . Em outras
palavras, uma cobertura por circuitos é uma coleção de circuitos tal que cada
aresta do grafo pertence a pelo menos um dos circuitos do coleção.1
Seria natural dedicar este capítulo ao problema da cobertura mínima
por circuitos. Mas este problema é muito difícil. (Veja fim do capítulo.)
Trataremos então do problema da decomposição em circuitos, que é bem
mais simples.
Uma decomposição em circuitos, ou cobertura simples por circuitos, de
um grafo é uma cobertura por circuitos que cobre cada aresta do grafo apenas
uma vez.

P ROBLEMA DA D ECOMPOSIÇÃO EM C IRCUITOS: Encontrar uma de-

composição em circuitos de um grafo dado.

Por conta do exercício 18.16, este problema também é conhecido como

“problema dos ciclos eulerianos”.

Exercícios
E 18.1 Exiba uma decomposição em circuitos de cada um dos grafos da
figura 18.1.

E 18.2 Para que valores de p e q uma grade p-por-q tem uma decomposição
em circuitos?
1
Coberturas por circuitos são muito diferentes de coberturas por emparelhamentos (isto
é, coloração de arestas), porque uma parte de um circuito não é um circuito enquanto toda
parte de um emparelhamento é um emparelhamento.

141
FEOFILOFF Coberturas por circuitos 142

Figura 18.1: Encontre uma decomposição em circuitos. Veja exercício 18.1.

E 18.3 Encontre uma decomposição em circuitos do grafo do cavalo.

E 18.4 Para que valores de k o cubo Qk tem uma decomposição em circuitos?

E 18.5 Dê uma condição necessária e suficiente para que um grafo completo

tenha uma decomposição em circuitos.

◦ E 18.6 Suponha que um grafo G tem uma ponte. Mostre que G não tem
decomposição em circuitos. (Veja exercício 1.199.)

E 18.7 Seja F um conjunto de arestas de um grafo G com três ou mais

vértices. Suponha que o grafo (VG , F ) é conexo e tem uma decomposição
em circuitos. Mostre que G é aresta-biconexo. A recíproca é verdadeira?

◦ E 18.8 Suponha que um grafo G tem um vértice de grau ímpar. Mostre que
G não tem decomposição em circuitos.2 (Outra maneira de dizer a mesma
coisa: se um grafo G tem uma decomposição em circuitos então todos os
vértices de G têm grau par.)

? E 18.9 (T EOREMA DE V EBLEN3 E E ULER4 ) Mostre que um grafo tem uma

decomposição em circuitos se e somente se o grau de cada um de seus
vértices é par. (Compare com o exercício 18.8.) Em outras palavras, mostre
que a ausência de vértices de grau ímpar é condição necessária e suficiente
para que um grafo tenha uma decomposição em circuitos.

E 18.10 Mostre que um grafo tem uma decomposição em circuitos se e so-

mente se todos os seus cortes são pares.

E 18.11 Grafos que têm decomposição em circuitos não têm vértices ímpares.
Por outro lado, grafos bicoloráveis não têm circuitos ímpares. Há algo por
trás desse paralelo?
2
Portanto, um vértice de grau ímpar é um certificado de inexistência de decomposição
em circuitos.
3
Oswald Veblen ( − ). Veja verbete na Wikipedia.
4
Leonhard Euler ( − ). Veja verbete na Wikipedia.
FEOFILOFF Coberturas por circuitos 143

E 18.12 Seja G o grafo de um mapa plano M. Suponha que G é biconexo

e não tem vértices de grau 2. Seja G∗ o grafo das faces (ou seja, grafo
dual) do mapa M. Mostre que G∗ é bicolorável se e somente se G tem uma
decomposição em circuitos.

E 18.13 (A LGORITMO) Construa um algoritmo que receba um grafo G e de-

volva uma decomposição em circuitos de G ou prove que tal decomposição
não existe.

Ciclos e trilhas eulerianas

Como já dissemos no fim da seção 1.9, um passeio (= walk) em um grafo é
qualquer sequência (v0 , v1 , v2 , . . . , vk−1 , vk ) de vértices tal que vi é adjacente
a vi−1 para todo i entre 1 e k. Dizemos que o passeio vai de v0 a vk . O
comprimento do passeio é o número k.
Uma trilha (= trail) é um passeio sem arestas repetidas, isto é, um passeio
cujas arestas são distintas duas a duas. Uma trilha (v0 , . . . , vk ) é fechada
(= closed) se v0 = vk .
Uma trilha é euleriana5 se passa por todas as arestas do grafo.6 Assim,
uma trilha (v0 , v1 , . . . , vk−1 , vk ) é euleriana se e somente se {v0 v1 , v1 v2 , . . . ,
vk−1 vk } é o conjunto de (todas as) arestas do grafo.
Um ciclo (= cycle) é uma trilha fechada.7 Um ciclo é euleriano se e
somente se passa por todas as arestas do grafo.

E 18.14 Encontre um ciclo euleriano no grafo da figura 18.2.

a h

b
c g
e
d f

Figura 18.2: Encontre um ciclo euleriano. Veja exercício 18.14.

5
Referência a Leonhard Euler ( − ). Veja verbete na Wikipedia.
6
Alguns autores também exigem que a trilha passe por todos os vértices do grafo. A
diferença entre as duas definições é superficial.
7
De acordo com essa definição, um ciclo pode ter comprimento 0. Já um circuito, por
definição, tem comprimento pelo menos 3.
FEOFILOFF Coberturas por circuitos 144

E 18.15 Considere as 21 peças do jogo de dominó que não são duplas. Cada
uma dessas peças corresponde a um subconjunto de cardinalidade 2 do con-
junto {0, 1, 2, . . . , 6}. É permitido “encostar” uma peça {i, j} numa peça {j, k}
de forma a produzir a sequência (i, j, j, k). Pergunta: É possível formar um
“roda” que contenha todas as 21 peças? E se eliminarmos todas as peças que
contêm “6”?

? E 18.16 (C ICLOS EULERIANOS) Mostre que todo grafo dotado de um ciclo

euleriano tem uma decomposição em circuitos.
Mostre que todo grafo conexo dotado de uma decomposição em circuitos
tem um ciclo euleriano.

E 18.17 Dê uma condição necessária e suficiente para que um grafo tenha

uma trilha euleriana não fechada.

E 18.18 (A LGORITMO) Construa um algoritmo que encontre uma trilha eu-

leriana (fechada ou não) em qualquer um grafo conexo dado.

! E 18.19 (P ROBLEMA DO C ARTEIRO C HINÊS8 ) Dado um grafo, encontrar

um passeio de comprimento mínimo dentre os que são fechados e passam
por todas as arestas do grafo.

E 18.20 Suponha que um grafo G tem um ciclo euleriano. Mostre que o grafo
das arestas L(G) tem um circuito hamiltoniano (veja exercício 1.24).
Mostre que a recíproca não é verdadeira: L(G) pode ter um circuito
hamiltoniano sem que G tenha um ciclo euleriano.

E 18.21 Sejam xy e yz duas arestas de um grafo conexo G sem vértices de

grau ímpar. É verdade que G tem um ciclo euleriano na qual xy e yz
aparecem consecutivamente?

E 18.22 Seja G um grafo conexo cada um de cujos vértices tem grau par.
Suponha ainda que m(G) é par. Prove que EG admite uma partição {F1 , F2 }
tal que |F1 ∩ ∂{v}| = |F2 ∩ ∂{v}| para cada vértice v, ou seja, v incide no
mesmo número de arestas de F1 e F2 .

Coberturas mínimas por circuitos

Como já dissemos no início do capítulo, uma coberturaSpor circuitos de um
grafo G é qualquer coleção O de circuitos de G tal que O∈O EO = EG .

8
Chinese Postman Problem. Proposto em 1962 pelo matemático chinês Mei-Ko Kwan.
FEOFILOFF Coberturas por circuitos 145

Uma cobertura por circuitos O é mínima se não existe cobertura por

circuitos O0 tal que |O0 | < |O|.
P O comprimento total de uma cobertura por circuitos O é a soma
O∈O |EO |. É claro que toda decomposição em circuitos é uma cobertura
de comprimento total mínimo.
A espessura de uma cobertura por circuitos O de um grafo G é o número
maxe∈EG |{ O ∈ O : EO 3 e }|. Assim, se uma cobertura por circuitos tem
espessura k então toda aresta do grafo pertence a no máximo k dos circuitos.
Reciprocamente, se cada aresta do grafo pertence a ≤ k circuitos da cobertura
então a cobertura tem espessura ≤ k.
É claro que uma decomposição em circuitos é o mesmo que uma cober-
tura de espessura 1.

Exercícios
◦ E 18.23 Mostre que um grafo tem uma cobertura por circuitos se e somente
se não tem pontes. (Veja o exercício 1.199.)

D 18.24 (C OBERTURA MÍNIMA POR CIRCUITOS) Escreva um algoritmo que

encontre uma cobertura por circuitos mínima de qualquer grafo sem pontes.

! E 18.25 Mostre que, para todo k par, o cubo Qk pode ser coberto por apenas
k/2 circuitos.

E 18.26 Encontre uma cobertura por circuitos mínima do grafo de Petersen.

E 18.27 Encontre uma cobertura por circuitos mínima do primeiro grafo da

figura 18.1. (Esse grafo pode ser descrito como K6 − M , sendo M um
emparelhamento perfeito.)

D 18.28 (C OBERTURA DE COMPRIMENTO TOTAL MÍNIMO) Encontre uma co-

bertura por circuitos de comprimento total mínimo em qualquer grafo sem
pontes.9

E 18.29 Encontre uma cobertura por circuitos do grafo de Petersen que tenha
comprimento total mínimo.

? E 18.30 Mostre que todo grafo planar aresta-biconexo G tem uma cober-
tura por circuitos de comprimento total ≤ 2m(G).
9
Não se conhece um algoritmo eficiente para o problema. Em termos técnicos, o pro-
blema é NP-difícil.
FEOFILOFF Coberturas por circuitos 146

D 18.31 (C OBERTURA DE E SPESSURA M ÍNIMA) Encontre uma cobertura

por circuitos que tenha espessura mínima em qualquer grafo sem pontes.
(Segundo a célebre conjectura da Cobertura Dupla por Circuitos,10 todo
grafo sem pontes tem uma cobertura de espessura ≤ 2.)

? E 18.32 Mostre que todo grafo planar aresta-biconexo tem uma cobertura
por circuitos de espessura ≤ 2.

E 18.33 Encontre uma cobertura por circuitos do grafo de Petersen que tenha
espessura mínima.

E 18.34 Encontre uma cobertura por circuitos de K5 que tenha espessura

mínima.

E 18.35 Encontre uma cobertura por circuitos de K3,3 que tenha espessura
mínima.

! E 18.36 (T EOREMA DE K ILPATRICK E J AEGER11 ) Mostre que todo grafo

aresta-4-conexo (veja página 129) tem uma cobertura por circuitos de espes-
sura ≤ 2.

E 18.37 Mostre (por meio de exemplos) que os conceitos de cobertura mí-

nima, cobertura de comprimento total mínimo, e cobertura de espessura
mínima são distintos dois a dois.

E 18.38 Por que o problema do carteiro chinês (exercício 18.19) não resolve
o problema da cobertura por circuitos de espessura mínima (veja exercí-
cio 18.31)? Por que não resolve o problema da cobertura por circuitos de
comprimento total mínimo (veja exercício 18.28)?

10
Circuit Double Cover Conjecture. A conjectura é de George Szekeres e Paul Seymour.
11
Publicado por Kilpatrick em 1975 e F. Jaeger em 1976.
Capítulo 19

Caracterização da planaridade

Como dissemos na seção 1.17, um grafo é planar se for representável por um

mapa plano, ou seja, se for isomorfo ao grafo de algum mapa plano.

P ROBLEMA DA P LANARIDADE: Decidir se um dado grafo é planar ou

não.

Se um grafo não é planar, como é possível tornar isso evidente? Uma

resposta muito bonita envolve o conceito de menores proibidos (veja a se-
ção 1.16): todo grafo não planar tem um menor que é obviamente não planar.

Exercícios
? E 19.1 Mostre que K3,3 não é planar. (Veja, por exemplo, o exercício 1.271.)

? E 19.2 Mostre que K5 não é planar. (Veja, por exemplo, o exercício 1.270.)

Figura 19.1: K3,3 e K5 não são planares. Veja exercícios 19.1 e 19.2.

◦ E 19.3 Mostre que todo subgrafo de um grafo planar é planar. Em outras

palavras, se um grafo G tem um subgrafo não planar então G não é planar.

◦ E 19.4 Suponha que todos os subgrafos próprios de um grafo G são plana-

res. É verdade que G é planar?

147
FEOFILOFF Caracterização da planaridade 148

E 19.5 Suponha que um grafo G não tem subgrafo isomorfo a K5 nem sub-
grafo isomorfo a K3,3 . É verdade que G é planar?

?◦ E 19.6 Mostre que todo menor topológico (veja seção 1.16) de um grafo
planar é planar. Em outras palavras, se um grafo G tem um menor topológico
não planar então G não é planar. (Em particular, se G contém uma uma
subdivisão de K5 ou K3,3 então G não é planar.)

? E 19.7 Mostre que todo menor (veja seção 1.16) de um grafo planar é
planar. Em outras palavras, se um grafo G tem um menor não planar então
G não é planar. (Em particular, se G tem uma subcontração isomorfa a K5
ou a K3,3 então G não é planar.)

E 19.8 Mostre que todo menor próprio de K5 é planar. Mostre que todo
menor próprio de K3,3 é planar.

◦ E 19.9 Mostre que K3,3 não é um menor de K5 . Mostre que K5 não é um

menor de K3,3 .

E 19.10 Para que valores de t o grafo do bispo t-por-t é planar?

E 19.11 Para que valores de t o grafo do cavalo t-por-t é planar?

E 19.12 Mostre que o grafo de Petersen não é planar. (Veja os exercícios 1.247
e 1.248.)

E 19.13 Mostre que o cubo Q4 não é planar. (Veja o exercício 1.249.)

?! E 19.14 (T EOREMA WAGNER1 ) Mostre que um grafo é planar se e

DE
somente se não tem um menor isomorfo a K5 nem um menor isomorfo a K3,3 .
(Compare com o exercício 19.7.)

?! E 19.15 (T EOREMA K URATOWSKI2 ) Mostre que um grafo é planar se

DE
e somente se não tem um menor topológico isomorfo a K5 nem um menor
topológico isomorfo a K3,3 . (Compare com o exercício 19.6.)

E 19.16 Discuta a seguinte afirmação: “Como K5 não é bicolorável, pode-

mos concluir que todo grafo bicolorável não planar tem um minor topoló-
gico K3,3 .”
1
Publicado em 1937 por Klaus W. Wagner ( − ).
2
Publicado em 1930 por Kazimierz Kuratowski ( − ).
FEOFILOFF Caracterização da planaridade 149

! E 19.17 (A LGORITMO) Construa um algoritmo que decida se um dado

grafo é planar.

! E 19.18 Mostre que todo grafo não planar 4-conexo tem um menor K5 .
Mostre que todo grafo não planar 3-conexo com 6 ou mais vértices tem um
menor K3,3 .

D 19.19 Prove a seguinte conjectura de Dirac:3 Se um grafo G não tem um

menor topológico K5 então m(G) ≤ 3n(G) − 6. (Compare com o exercí-
cio 1.268.)

E 19.20 Mostre que um grafo é exoplanar (veja o exercício 1.283) se e somente

se não tem menor K4 nem menor K2,3 . Mostre que um grafo é exoplanar se e
somente se não tem menor topológico K4 nem menor topológico K2,3 .

3
A conjectura foi proposta por G. A. Dirac em 1964.
FEOFILOFF Caracterização da planaridade 150
Apêndice A

Algumas dicas

Exercício 1.208. Prova por indução na distância entre r e s. Ela cuida primeiro
do caso em que r e s são vizinhos, depois do caso em que existe um caminho de
comprimento 2 de r a s, etc.
Seja v0 v1 . . . vk um caminho de r a s. Por hipótese de indução, existem dois
caminhos, P e Q, de v0 a vk−1 tais que EP ∩ EQ = ∅. Seja C um circuito que contém
a aresta vk−1 vk . O grafo P ∪ Q ∪ C contém dois caminhos de v0 a vk sem arestas em
comum.

Exercício 1.226. Suponha que há dois caminhos diferentes, digamos P e Q, com

extremos x e y. Encontre um circuito no grafo P ∪ Q.

Exercício 1.233. Seja v um vértice tal que d(v) = ∆. Para cada vizinho w de v,
tome um caminho maximal dentre os que têm v como primeiro vértice e w como
segundo vértice.

Exercício 1.228. Faça a prova por indução em m(G). Passo da indução: Seja a
uma aresta de T e sejam T1 e T2 os dois componentes de T − a. Por hipótese de
indução, m(T1 ) = n(T1 ) − 1 e m(T2 ) = n(T2 ) − 1.

Exercício 1.229. Indução em n(G). Passo da indução: Suponha m(G) = n(G) − 1.

Seja v um vértice v tal que d(v) = 1. O grafo G−v é conexo e m(G−v) = n(G−v)−1.
Por hipótese de indução, G − v não tem circuitos. Portanto, G não tem circuitos.

Exercício 1.266. Faça indução no número de faces. A base da indução usa a

igualdade m = n − 1 válida para árvores (veja exercício 1.228).

Exercício 1.268. Comece tratando do caso em que G é aresta-biconexo. Veja os

exercícios 1.266 e 1.267.

151
FEOFILOFF 152

Exercício 1.275. Veja o exercício 1.268.

Exercício 4.23. Digamos que as aresta em D são vermelhas e as outras são pretas.
Um caminho é par se tem um número par de arestas vermelhas e ímpar se tem um
número ímpar de arestas vermelhas.
Fato fundamental: se dois caminhos têm os mesmos extremos, então têm a
mesma paridade. Prove este fato por indução no número de vértices comuns.

Exercício 5.27. Mostre que o algoritmo do exercício 5.22 produz um conjunto

estável S tal que |S| ≥ n/(µ + 1).

Exercício 6.15. Suponha ω ≤ 2. Construa um grafo bicolorável H tal que VH = VG

e dG (v) ≤ dH (v) para todo vértice v. Use o exercício 4.12.

Exercício 8.47. Seja {X1 , . . . , Xk } uma coloração mínima que maximiza o número
Pk
i=1 i |Xi |.
Então existe um caminho da forma x1 x2 . . . xk com xi ∈ Xi .
Outra possibilidade: veja algoritmos nos exercícios 8.28 e 8.29.
Outra possibilidade: remova o último vértice de um caminho de comprimento
máximo e aplique indução.

Exercício 8.41. No início de cada iteração os vértices v1 , . . . , vj já foram coloridos

com k cores e G[{v1 , . . . , vj }] tem uma clique com k vértices.

Exercício 9.23. Veja o exercício 9.17.

Exercício 9.36. Mostre que G − v tem pelo menos um componente ímpar. Depois,
mostre que G − v não pode ter mais que um componente ímpar.

Exercício 10.4. Prove que uma das pontas de cada aresta é saturada por todos os
emparelhamentos máximos. Prova por contradição: suponha que existe uma aresta
uw e emparelhamentos máximos M e N tais que M não satura u e N não satura w.
Estude o componente de (VG , M ∪ N ) que contém u.

Exercício 10.6. Prova por indução no número de vértices. Tome um vértice u

que seja saturado por todos os emparelhamentos máximos. Aplique a hipótese de
indução a G − u.

Exercício 10.18. Seja M um emparelhamento máximo. Digamos que um caminho

é bom se tiver um extremo em U r V (M ) e for M -alternante Seja X o conjunto dos
vértices de todos os caminhos bons. Seja K := (W ∩ X) ∪ (U r X). Mostre que K é
uma cobertura. Mostre que |K| = |M |.
FEOFILOFF Algumas dicas 153

Exercício 10.12. Seja M ∗ um emparelhamento máximo e suponha por um mo-

mento que |M ∗ | < k. De acordo com o teorema de Kőnig, G tem uma cobertura K∗
tal que |K∗ | < k. Logo, m(G) ≤ |U | |K∗ | ≤ |U | (k − 1). Contradição.

Exercício 10.22. Seja M um emparelhamento e K uma cobertura tais que |M | =

|K| (veja exercício 10.6). Mostre que |U | ≤ |K| e veja o exercício 9.30.

Exercício 10.22. A prova é uma indução na cardinalidade de U . O passo da

indução tem dois casos. No primeiro, |NG (Z)| > |Z| para todo subconjunto próprio
e não vazio Z de U . No segundo, |NG (Y )| = |Y | para algum subconjunto próprio e
não vazio Y de U . No primeiro caso, tome qualquer aresta uw com u ∈ U e aplique
a hipótese de indução a G − {u, w}. No segundo, aplique a hipótese de indução a
G − (Y ∪ NG (Y )) e a G[(U r Y ) ∪ (W r N(Y ))].

Exercício 10.32. Considere o grafo (VG , M ∪ N ). Veja exercício 9.17.

Exercício 12.2. Cada operário é um vértice do meu grafo; cada máquina também
é um vértice; cada aresta é uma tarefae que associa um operário com uma máquina;
cada cor é um dia de trabalho.

Exercício 12.15. G não tem emparelhamento perfeito.

Exercício 12.16. G não tem emparelhamento perfeito. Segue do exercício 12.15.

Exercício 12.23. Faça indução em r. Veja exercício 10.29.

Exercício 12.25. Veja o exercício 10.34.

Exercício 13.4. Basta provar que cada aresta de C é uma ponte no grafo (VG , C).
(Veja também os exercícios 1.149 e 1.157.)

Exercício 13.8. Veja o exercício 1.226.

Exercício 14.9. Sejam x e z dois vértices não adjacentes de uma árvore. Seja L o
único caminho de x a z. Mostre que se exc(x) = exc(z) então exc(y) < exc(x) para
todo vértice interno y de L.

Exercício 14.14. Veja o exercício 14.13.

Exercício 14.18. Para cada vértice r, analise a árvore das distância (exercício 14.7)
centrada em r. Veja exercícios 14.13, 14.5, 1.123, e 14.3.
FEOFILOFF 154

Exercício 14.19. Para cada vértice r, analise a árvore das distância 14.7 centrada
em r.

Exercício 14.20. Encontre um emparelhamento perfeito de peso mínimo (veja

exercício 11.17) num grafo apropriado construído a partir de (G, u, v).

Exercício 14.21. Encontre um emparelhamento perfeito de peso mínimo (veja

exercício 11.17) num grafo apropriado construído a partir de (G, u, v).

Exercício 15.6. Faça a prova por indução em k. Adote as seguintes definições:

Para qualquer subconjunto B de EG , seja V (B) o conjunto dos vértices que incidem
em elementos de B e seja G(B) o grafo (V (B) ∪ {r}, B). Um subconjunto B de EG
é bom se G(B) é conexo e dG−B (Y ) ≥ k − 1 para todo Y que contém r mas não
contém s.
Comece por provar o seguinte lema: Para qualquer conjunto bom B, se s não
está em G(B) então existe uma aresta e em EG r B tal que B ∪ {e} é bom. Use o
exercício 1.115.

Exercício 16.10. Acrescente a G um novo vértice y e novas arestas ligando y a

cada um dos vértices em S. Mostre que o novo grafo é k-conexo.

Exercício 16.25. Faça indução em k, começando com k = 2. No passo da indução,

use o lema do leque, exercício 16.10.

Exercício 17.10. Tome um caminho maximal. (Veja a seção 1.7.)

Exercício 17.19. Veja os exercícios 1.174 e 1.175.

Exercício 17.26. Sejam u e v os extremos de um caminho máximo P . Mostre que

o grafo (VP , EP ∪ ∂(u) ∪ ∂(v)) contém um circuito hamiltoniano.

Exercício 18.6. Veja os exercícios 1.110 e 18.8.

Exercício 18.7. Veja os exercícios 1.110, 1.199 e 18.6.

Exercício 18.16. Veja o exercício 1.126.

Exercício 18.19. Se não há vértices de grau ímpar, basta encontrar um ciclo eu-
leriano. Se há apenas dois vértices de grau ímpar, basta tomar um caminho de
comprimento mínimo entre esses vértice e. . . Se há mais que dois vértices de grau
ímpar, use o algoritmo do emparelhamento de peso mínimo (exercício 11.17) para
escolher caminhos ligando vértices ímpares dois a dois.
FEOFILOFF Algumas dicas 155

Exercício 19.6. Segue de 19.7 e 1.250.

Exercício 19.7. Isto é uma generalização do exercício 19.6. Veja os exercícios 1.250
e 1.251.

Exercício 19.14. Segue de 19.15 e 1.250.

Exercício 19.15. Segue de 19.14 e 1.251.

FEOFILOFF 156
Apêndice B

O alfabeto grego

A teoria dos grafos, tal como outras áreas da matemática, considera o alfabeto latino
insuficiente e recorre muitas vezes ao alfabeto grego:

α A alfa ν N nü
β B beta ξ Ξ ksi
γ Γ gama o O ômicron
δ ∆ delta π Π pi
ε E epsilon ρ P rô
ζ Z zeta σ Σ sigma
η H eta τ T tau
θ Θ teta υ Υ upsilon
ι I iota ϕ Φ fi
κ K kapa χ X qui
λ Λ lambda ψ Ψ psi
µ M mü ω Ω ômega

O símbolo ∂ não pertence ao alfabeto grego. Este texto usa o símbolo para
denotar cortes (veja a seção 1.8).

157
FEOFILOFF 158
Bibliografia

[BM76] J.A. Bondy and U.S.R. Murty. Graph Theory with Applicati-
ons. Macmillan/Elsevier, 1976. [Link]
[Link]. 5
[BM08] J.A. Bondy and U.S.R. Murty. Graph Theory. Graduate Texts in
Mathematics 244. Springer, 2008. 5, 17
[Bol98] B. Bollobás. Modern Graph Theory. Springer, 1998. 5
[Car11] D.M. Cardoso. Teoria dos Grafos e Aplicações. Internet: http:
//[Link]/handle/arquivo-e/78, 2011.
[Die00] R. Diestel. Graph Theory. Springer, 2nd edition, 2000. http://
[Link]/[Link]. 5
[Die05] R. Diestel. Graph Theory. Springer, 3rd edition, 2005. http://
[Link]/[Link]. 5, 8, 17
[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide
to the Theory of NP-Completeness. W.H. Freeman, 1979. 5, 139
[Har92] D. Harel. Algorithmics: The Spirit of Computing. Addison-Wesley,
2nd edition, 1992. 5, 139
[JNC10] D. Joyner, M.V. Nguyen, and N. Cohen. Algorithmic Graph Theory.
Google Code, 2010. [eBook].
[Knu93] D.E. Knuth. The Stanford GraphBase: A Platform for Combinatorial
Computing. ACM Press and Addison-Wesley, 1993. 12
[Lov93] L. Lovász. Combinatorial Problems and Exercises. North-Holland,
second edition, 1993. 5
[LP86] L. Lovász and M.D. Plummer. Matching Theory, volume 29 of
Annals of Discrete Mathematics. North-Holland, 1986. 5
[Luc79] C.L. Lucchesi. Introdução à Teoria dos Grafos. 12o. Colóquio
Brasileiro de Matemática. IMPA (Instituto de Matemática Pura e
Aplicada), 1979. 5

159
FEOFILOFF BIBLIOGRAFIA 160

[MST+ 98] O. Melnikov, V. Sarvanov, R. Tyshkevich, V. Yemelichev, and

I. Zverovich. Exercises in Graph Theory, volume 19 of Kluwer Texts
in the Mathematical Sciences. Kluwer, 1998. 5

[OPG] Open Problem Garden. Internet: [Link]

Hosted by Simon Fraser University.

[Per09] J.M.S. Simões Pereira. Matemática Discreta: Grafos, Redes, Aplica-

ções. Luz da Vida, Coimbra, Portugal, 2009. 14, 21, 26

[Sch03] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency.

Springer, 2003. 119

[Sip97] M. Sipser. Introduction to the Theory of Computation. PWS Pu-

blishing, 1997. [Link]
5, 139

[vL90] J. van Leeuwen. Graph algorithms. In J. van Leeuwen, editor,

Algorithms and Complexity, volume A of Handbook of Theoretical
Computer Science, pages 527–631. Elsevier and MIT Press, 1990.

[Wil79] R.J. Wilson. Introduction to Graph Theory. Academic Press, 2nd

edition, 1979. 5

[Zha97] C.-Q. Zhang. Integer Flows and Cycle Covers of Graphs. Marcel
Dekker, 1997.
Índice Remissivo

bxc, 10, 38 δ(X), 29

dxe, 76 ∆(G), 17
V (2) , 8 κ(G), 133
Adj , 17 κ 0 (G), 129
VG , 8 µ(G), 17
EG , 8 o(G), 109
n(G), 8 χ(G), 85
m(G), 8 χ 0 (G), 113
c(G), 39 ω(G), 79
d(v), 17 ∂(X), 29
d(X), 29 ∇(X), 29
G, 8
Kn , 8 α(G), 73
Kp,q , 15 α 0 (G), 97
Qk , 12 abrangente (subgrafo), 26
L(G), 14 acíclico, 119
N(v), 17 adjacent, 8
N(X), 30 adjacentes
X ⊂ Y , 26 arestas, 14, 97
Y ⊃ X, 26 vértices, 8
A ⊕ B, 30 alcanos, 9
G ⊆ H, 26 aleatório, 59
G ∪ H, 24 algoritmo
G ∩ H, 24 de aproximação, 84, 101
G[X], 26 de Kruskal, 121
G∼ = H, 61 de Prim, 121
G(n), 59 fluxo máximo e corte mínimo, 128
G − v, 26 guloso, 75, 88, 92, 115
G − X, 26 húngaro, 105
G − e, 26 alternating, 98
G − A, 26 Appel, 93
α(G), 73 aresta, 8
α 0 (G), 97 de corte, 42
β(G), 83 aresta-biconexo, 44, 129
γ(G, S), 110 aresta-conexidade, 129
δ(G), 17 aresta-k-conexo, 129
arestas

161
FEOFILOFF ÍNDICE REMISSIVO 162

adjacentes, 14, 97 par mínimo, 126

múltiplas, 8, 55 caminhos
paralelas, 8, 55 internamente disjuntos, 131
articulação, 45 carteiro chinês, 144
articulation, 45 Catlin, 87
árvore, 47 cavalo, 11
abrangente, 119 centro, 125
das distâncias, 124 certificado, 71, 90, 101, 110, 128, 132, 142
geradora, 119 chinese postman, 144
augmenting path, 98 chromatic
auto-complementar, 64 index, 113
number, 85
β(G), 83 Chudnovsky, 95
Barnette, 140 Chvátal, 138
Berge, 95 ciclo, 35, 143
BFS, 124 euleriano, 143
bicoloração, 69 cintura, 123
bicolorável, 69 ímpar, 125
biconexo, 45, 133 par, 125
aresta-biconexo, 44 circuit cover, 141
biconnected, 45 circuit decomposition, 141
bipartição circuit double cover, 146
de conjunto, 69 circuito, 21
de grafo, 15 hamiltoniano, 135
bipartido, 15 ímpar, 69, 71
completo, 15 ímpar mínimo, 125
bipartite, 15 máximo, 135
bishop, 11 mínimo, 123
bispo, 11 par, 71
Bollobás, 5 par mínimo, 125
breadth-first search, 124 circunferência, 135
bridge, 42 clique, 79
buraco ímpar, 95 clique cover, 86
busca em largura, 124 clique number, 79
closed, 35, 143
c(G), 39
cobertura, 83
caixeiro viajante, 139
dupla por circuitos, 146
caminho, 21
por arestas, 111
alternante, 98
por circuitos, 141
de aumento, 98
por cliques, 86
hamiltoniano, 135
por vértices, 83
ímpar, 71
coboundary, 29
ímpar mínimo, 126
coleção, 59
maximal, 32
colorable, 85
máximo, 32, 135
k-coloração, 85
mínimo, 123
coloração
par, 71
FEOFILOFF ÍNDICE REMISSIVO 163

de arestas, 113 dama, 10

de vértices, 85 decomposição
mínima, 85, 113 em circuitos, 141
colorável, 85 degree, 17
k-colorável, 85 desigualdade triangular, 124
comparabilidade, 14 diameter, 126
complemento, 8 diâmetro, 126
completo, 8 diferença simétrica, 30, 99
componente, 39 Dirac, 134, 138, 149
ímpar, 109 disjuntos internamente, 45
comprimento dist( ), 123
de caminho, 21 distância, 123
de circuito, 21 dual de mapa plano, 55
de passeio, 34, 143
de trilha, 35 E, 6
conector, 119 ◦ E, 6
conexidade, 129, 133 ! E, 6
conexo, 36 !! E, 6
k-conexo, 133 ? E, 6
conjectura ?! E, 6
Barnette, 140 ?◦ E, 6
Berge, 95 . E, 6
Chvátal, 138 E ♥, 6
cobertura dupla por circuitos, 146 EG , 8
Hadwiger, 95 eccentricity, 125
conjunto edge, 8
acíclico, 119 edge cover, 111
completo, 79 edge-biconnected, 44
estável, 73 Edmonds, 111
independente, 73 Egerváry, 104
connected, 36 emparelhamento, 97
corte, 29 de peso máximo, 111
trivial, 29 perfeito, 97
cubo, 12 Erdős, 68, 117
k-cubo, 12 estável, 73
cut, 29 estrela, 15
cut edge, 42 Euler, 56, 143
cut vertex, 45 euleriana, 143
cycle, 35, 143 excentricidade, 125
exoplanar, 58
D, 6 extremos de caminho, 21
δ(G), 17
δ(X), 29 face, 54
∆(G), 17 face, 54
d(v), 17 fechado (passeio, trilha), 35, 143
d(X), 29 filho de vértice, 47
∂(X), 29 floresta, 47
FEOFILOFF ÍNDICE REMISSIVO 164

flow, 127 dos estados, 13

fluxo, 127 dual, 55
internamente disjunto, 131 exoplanar, 58
fluxo máximo, 127 grade, 10
folha, 47 lineal, 14
forest, 47 perfeito, 95
fórmula de Euler, 56 periplanar, 58
franja, 29 planar, 25, 54
fronteira de face, 54 plano, 53
regular, 17
γ(G, S), 110 simples, 8
G(n), 59 vazio, 8
Gallai, 68, 91, 111 grafos disjuntos, 24
gerador (subgrafo), 26 graph, 8
girth, 123 graph design, 67
grade, 10 grau
gráfica (sequência), 67 de conjunto de vertices, 29
grafo, 8 de face, 54
-linha, 14 de vértice, 17
acíclico, 47 máximo, 17
aleatório, 59 médio, 17
aresta-biconexo, 44, 129 mínimo, 17
bicolorável, 69 greedy, 75, 88
biconexo, 45, 133 grid, 10
bipartido, 15 guloso, 75
bipartido completo, 15
k-colorável, 85 Hadwiger, 95
complementar, 8 Hajós, 94
completo, 8 Haken, 93
cúbico, 17 Hall, 106
da dama, 10 Hamilton, 135
da torre, 11 hamiltoniano, 135
das arestas, 14 Heawood, 33, 125
das faces, 55 heurística
das palavras, 12 da troca de cores, 116
de Catlin, 87 hexágono, 21
de comparabilidade, 14 hidrocarbonetos, 9
de Heawood, 33, 125
de intervalos, 14 incide, 8
de Kneser, 12 independence number, 73
de mapa plano, 53 independent, 73
de matriz quadrada, 13 índice de estabilidade, 73
de Petersen, 12 indução, 26, 136
de Turán, 77 internamente disjunto, 131
do bispo, 11 interseção de grafos, 24
do cavalo, 11 intervalos, 14
do rei, 12 isolado (vértice), 17
FEOFILOFF ÍNDICE REMISSIVO 165

isolador, 31 multiple edges, 8, 55

isomorfismo, 61
isomorphism, 61 n(G), 8
isthmus, 42 N(v), 17
istmo, 42 N(X), 30
não ordenado, 8
Kn , 8 neighbor, 8
Kp,q , 15 neighborhood, 17
Kn , 8 NP-completo, 5
κ(G), 133 NP-difícil, 5
κ 0 (G), 129 número cromático, 85
king, 12 número de cores, 85, 113
Kirkman, 135
Kneser, 12 o(G), 109
knight, 11 ω(G), 79
Kőnig, 104, 116 odd component, 109
Kruskal, 121 odd hole, 95
Kuratowski, 148 ordem parcial, 14
origem de passeio, 34
L(G), 14 outerplanar, 58
laço, 8, 55
leaf, 47 pai de vértice, 47
liga u a v, 21 palavras, 12
ligado, 36 par não ordenado, 8
line graph, 14 parallel edges, 8, 55
lineal (grafo), 14 paridade, 71
linhas (de mapa plano), 53 partição, 15
loop, 8, 55 passeio, 34, 143
Lovász, 5, 13, 95 de v a w, 34, 143
fechado, 35
m(G), 8 simples, 35
µ(G), 17 pentágono, 21
máinor, 50 perfect
mapa plano, 53 elimination scheme, 90
matching, 97 graph, 95
maximum weight, 111 matching, 97
matriz perfeito
de adjacências, 9 emparelhamento, 97
de incidências, 9 grafo, 95
maximal, 73, 97 periplanar, 58
maximal vs máximo, 32, 73, 97, 119 permutação, 21, 47
máximo, 27, 73, 97 peso de aresta, 111, 121
Menger, 128, 132 Petersen, 12
menor, 50 planar, 25, 54, 147
menor topológico, 50 ponta de aresta, 8
minimal vs mínimo, 119 ponte, 42
minor, 50 pontos (de mapa plano), 53
FEOFILOFF ÍNDICE REMISSIVO 166

Prim, 121 Berge, 100

problema Brooks, 89
do caixeiro viajante, 139 Dirac, 134, 138
do carteiro chinês, 144 Erdős e Gallai, 68
Euler, 142
Qk , 12 Gallai e Roy, 91
quadrado, 21 Hall, 106
quase todo, 59 Havel e Hakimi, 68
queen, 11 Kőnig, 116
radius, 125 Kőnig–Egerváry, 104
raio, 125 Kuratowski, 148
raiz de árvore, 47 Menger, 128, 132
random, 13 Turán, 77
recobrimento Tutte, 109, 140
por circuitos, 141 Tutte–Berge, 110
regular, 17 Veblen, 142
rei, 12 Vizing, 117
Robertson, 93, 95 Wagner, 148
roda, 24 término de passeio, 34
rook, 11 Thomas, 93, 95
Roy, 91 topological minor, 50
torre, 11
separa, 34, 127, 131 trail, 35, 143
separador, 131 traveling salesman, 139
sequência gráfica, 67 tree, 47
Seymour, 93, 95, 146 triângulo, 21
slither, 100 trilha, 35, 143
spanning, 26, 119 euleriana, 143
stability number, 73 fechada, 143
stable, 73 TSP, 139
star, 15 Turán, 77
subcontração, 50 Tutte, 109, 140
subdivisão, 51
subgrafo, 26 união de grafos, 24
abrangente, 26 usa k cores, 85
gerador, 26 VG , 8
induzido, 26 vai de v a w, 32
maximal, 39 vazio, 8
próprio, 26 vertex cover, 83
subpartição, 50 vértice, 8
suporte de mapa plano, 54 de corte, 45
Szekeres, 146 interno, 21, 131
tabuleiro, 11 isolado, 17
teorema das saturado, 97
Quatro Cores, 93 vértices
teorema de brancos, 15
FEOFILOFF ÍNDICE REMISSIVO 167

pretos, 15
vértices adjacentes, 8
vizinho, 8

Wagner, 148
walk, 34, 143
wheel, 24
Wilson, 117

χ(G), 85
χ 0 (G), 113

Younger, 5