Teoria dos Grafos

Prévia do material em texto

Mario Leston
Teoria dos Grafos
Sumário
1 Noções básicas 5
1 Para um conjunto X e um inteiro não-
negativo k,
(X
k
)
é o conjunto cujos ele-
mentos são os subconjuntos de X de ta-
manho k, i.e.,(X
k
)
= {Y ⊆ X | |Y | = k}.
Por exemplo,({1, 2, 3}
2
)
= {{1, 2}, {1, 3}, {2, 3}}.
Note que (∅, ∅) é um grafo; tal grafo é
chamado de vazio.
|G|
||G||
Assim, por exemplo,
|{1, 5, 2, 3}| = 4.
2 Cuidado! Essa notação não é padrão!
1
Noções básicas
Grafos
Um grafo é um objeto constituído de três ingredientes: um conjunto
de vértices, um conjunto de arestas, e uma função que leva cada aresta
num par de vértices. Formalmente, um grafo é uma tripla (V,E, ι) em
que
• V é um conjunto finito cujos elementos são chamados de vértices;
• E é um conjunto finito cujos elementos são chamados de arestas;
• ι, a função de incidência, é uma função que leva cada aresta num par
(não-ordenado) 1 de vértices, isto é, ι : E →
(
V
2
)
.
Além disso, V e E são conjuntos disjuntos, ou seja, V ∩ E = ∅. Vamos
tecer alguns comentários sobre a notação que, às vezes, pode se tornar
uma chateação por diversos motivos, inclusive o estético. Um grafo
G é uma tripla. Logo, é conveniente definir uma notação para extrair
cada componente da tripla. Escrevemos, assim, V (G) para denotar o
conjunto dos vértices de G. De forma similar, escrevemos E(G) e ι(G)
para denotar o conjunto das arestas de G e a função de incidência de G.
Às vezes, por uma questão puramente estética, vamos alternativamente
escrever VG, EG e ιG em vez de V (G), E(G) e ι(G), respectivamente.
Esta convenção será utilizada com frequência para outras funções que
vamos definir. Além disso, quando houver um único grafo no contexto
da discussão evidentemente vamos simplesmente escrever V,E e ι em
vez de suas versões mais longas. O número de vértices de G, |V (G)|,
é denotado mais simplesmente por |G|, e o número de arestas, |E(G)|,
por ||G||. Para cada aresta e, ι(e) é um objeto da forma {u, v} em que u e
v são vértices distintos de V . Por brevidade, escrevemos
uv
no lugar de {u, v}. Para pesar menos na notação, vamos adotar a se-
guinte convenção: escrevemos 2
6 TEORIA DOS GRAFOS
3 É claro que tal convenção pode carre-
gar uma certa ambiguidade quando uma
mesma aresta estiver envolvida em mais
de um grafo.
4 Duas funções f, g : X → Y são iguais
se
f(x) = g(x)
para cada x ∈ X .
e ≃ uv
quando ι(e) = {u, v}.3 Os vértices u e v são as pontas de e. Dizemos
também que u e v incidem, ou são incidentes, em e e que u e v são vizinhos.
Vamos abusar um pouco da notação e escrever
u ∈ e
em vez de u ∈ ι(e) quando o vértice u é uma das pontas da aresta e.
v1 v2
v3v4
v5e1
e2
e3 e8
e4
e5
e6 e7
Figura 1.1: A figura exibe um dese-
nho de um grafo cujo conjunto de vérti-
ces é {v1, v2, v3, v4, v5}, e cujo conjunto
de arestas é {e1, e2, e3, e4, e5, e6, e7, e8},
onde e1 ≃ v1v4, e2 ≃ v3v4, e3 ≃ v2v3,
e4 ≃ v1v2, e5 ≃ v1v5, e6 ≃ v4v5,
e7 ≃ v3v5, e8 ≃ v2v3.
Observe que e3 e e8 têm as mesmas pon-
tas. O corte de v2, ∇(v2), é o conjunto
{e3, e4, e8}.
A noção de igualdade é fundamental na matemática. Não seria, en-
tão, diferente aqui. Dizemos que os grafos G e H são iguais, denotado
não surpreendentemente por G = H , se VG = VH , EG = EH e ιG = ιH .4
Um momento de reflexão o fará constatar que a noção de igualdade en-
volvendo grafos é um tanto quanto sem graça. No momento apropri-
ado, vamos introduzir a noção de isomorfismo. Esta, sim, muito mais
interessante e de fundamental importância uma vez que decidir se dois
grafos são isomorfos é um problema ainda não muito bem compreen-
dido.
Alguns conceitos envolvendo grafos são extremamente intuitivos e
formalizam relações corriqueiras envolvendo entidades da realidade.
Essa é uma das motivações que tornam o conceito tão atraente e reche-
ado de aplicações práticas.
Vamos fixar um grafo G na discussão que segue cujo propósito é o
de definir uma série de funções sobre o conjunto dos vértices de um
grafo.
Corte e grau de um vértice
Seja u um vértice de G. O corte de u, denotado ∇G(u), é o conjunto
das arestas de G que incidem em u. Formalmente,
∇G(u) = {e ∈ E | u ∈ e}.
A notação ∇G(u) é um tanto quanto pesada, por isso, quando não hou-
ver possibilidade de confusão e para simplificar, vamos escrever ∇(u)
ou ainda, mais simplesmente,
∇u.
NOÇÕES BÁSICAS 7
u
v1 v2 v3
e1
e2
e3 e4
Figura 1.2: A figura ilustra o vértice
u com ∇u = {e1, e2, e3, e4}. Assim,
d(u) = 4.
O tamanho (ou a cardinalidade) de ∇u, denotada d(u), é chamado de
grau de u. O grau mínimo de G, denotado δ(G), é o número min{d(v) |
v ∈ V }.
Os dois próximos fatos costumam ser os primeiros destacados em
introduções à Teoria dos Grafos. Vamos, então, manter a tradição. No
entanto, vamos aproveitar a oportunidade para introduzir uma notação
que será útil.
Seja U um conjunto universo e X uma parte de U , ou seja, X ⊆ U . A
função característica de X em relação a U é a função
χXU : U → {0, 1}
tal que
χXU (u) =
1, se u ∈ X0, se u /∈ X
para cada u ∈ U . Observe que |X| =
∑
u∈U χ
X
U (u). O gosto pela brevi-
dade nos fará escrever
χX
em vez de sua versão mais longa, deixando, então, subjacente o con-
junto universo em questão. A prova do lema que segue adota esta ati-
tude e escreve χ∇u no lugar de χ∇uE para cada vértice u.
Lema 1.1. Se G é um grafo, então
∑
v∈V d(v) = 2||G||.
Prova. Suponha que G é um grafo. Observe, primeiro, que
d(v) =
∑
e∈E
χ∇v(e)
para cada v ∈ V . Ademais, ∑
v∈V
χ∇v(e) = 2
para cada e ∈ E. Assim,∑
v∈V
d(v) =
∑
v∈V
∑
e∈E
χ∇v(e) =
∑
e∈E
∑
v∈V
χ∇v(e) =
∑
e∈E
2 = 2|E|.
Corolário 1.1. Todo grafo possui um número par de vértices de grau
ímpar.
Prova. Seja G um grafo, P o conjunto dos vértices de grau par de G e I o
conjunto dos vértices de grau ímpar de G. É evidente que
∑
v∈V d(v) =∑
v∈P d(v) +
∑
v∈I d(v). Ora, pelo Lema 1.1,
∑
v∈V d(v) é par. Mas,∑
v∈P d(v) também é par. Segue assim que
∑
v∈I d(v) é par e, portanto,
|I| é par.
8 TEORIA DOS GRAFOS
u
v1 v2 v3
Figura 1.3: A figura ilustra o vértice u
com Γu = {v1, v2, v3}, donde γ(u) = 3.
5 Note que aqui, mais uma vez, estamos
fazendo uso da convenção implícita –
agora não mais implícita – de omitir o
nome do grafo e os parênteses na nota-
ção, convenção esta que permeará este
texto sempre que não houver possibili-
dade de confusão.
6 Uma função f : X → Y pode ser en-
carada como um conjunto de pares da
forma (x, f(x)) para cada x ∈ X :
f = {(x, f(x)) | x ∈ X}.
Desta forma, para funções f e g, estamos
autorizados a escrever
f ⊆ g
uma vez que f e g são conjuntos. Para
uma função
f : X → Y
e uma parte Z de X ,
f|Z : Z → Y
é a restrição de f aos elementos de Z:
f|Z = {(z, f(z)) | z ∈ Z}.
Exercício 1.1. Mostre que se G é um grafo e |E| ⩾ |V | + 1, então
existe v ∈ V tal que d(v) ⩾ 3.
Vizinhança de um vértice
Seja u um vértice de G. Um vértice v de G é vizinho de u se uma das
arestas de G tem pontas u e v. Vamos coletar esses elementos em um
conjunto, denotado por ΓG(u), e chamá-lo de vizinhança (ou de conjunto
dos vizinhos) de u. Mais formalmente,
ΓG(u) = {v ∈ V | ∃e ∈ E : e ≃ uv}.
Reiterando, para tornar a notação mais leve vamos escrever
Γu
sempre que possível e esteticamente agradável. A função ΓG é cha-
mada de função de vizinhança de G. O número de vizinhos de u, denotado
por γ(u), é o tamanho (ou a cardinalidade) do conjunto Γu. Assim,
γu = |Γu| para cada u ∈ V .5 Convém observar que, em geral, γ ̸= d.
Subgrafos
Sejam G e H grafos. Dizemos que H é um subgrafo de G, escrito
H ⊆ G, se 6
VH ⊆ VG, EH ⊆ EG e ιH ⊆ ιG.
Em palavras, um grafo H é subgrafo de um grafo G se as seguintes
condições são satisfeitas:
• todo vértice de H é vértice de G, e
• se e é uma aresta de H com pontas x e y, então e é uma aresta de
G e suas pontas são também x e y.
Um subgrafo H de G é dito gerador se V (H) = V (G).
Subgrafo induzido
Seja X ⊆ V . Cada aresta que possui ambas as pontas em X é dita
induzida por X . O conjunto das arestas induzidas por X é denotado por
EG[X] (ou simplesmente E[X]), isto é,
E[X] = {e ∈ E | ∃x1, x2∈ X : e ≃ x1x2}.
O subgrafo de G induzido por X , denotado G[X], é o grafo
(X,E[X], ι|E[X]).
NOÇÕES BÁSICAS 9
7 Xc é o conjunto V −X .
Seja, agora, F ⊆ E. O subgrafo de G induzido por F , denotado G[F ],
é o grafo
(
⋃
f∈F
ι(f), F, ι|F ),
ou seja, é o grafo cujo conjunto dos vértices é constituído dos vérti-
ces que incidem em alguma aresta de F , e cujo conjunto das arestas é
F . Neste último caso costuma se conveniente confundir o conjunto de
arestas F com o grafo G[F ], hábito este que será recorrente durante o
texto sempre que não houver possibilidade de confusão.
Remoção de vértices e arestas
Para um conjunto de vértices X ⊆ V , denotamos por G−X o grafo
induzido por 7 Xc, isto é, G[Xc], e dizemos que G−X é o grafo obtido
de G através da remoção dos vértices em X . Para um vértice v de G,
escrevemos G − v no lugar de G − {v}. De forma similar, para cada
F ⊆ E, denotamos por G − F o grafo (V,E − F, ι|E−F ) e dizemos que
G− F é o grafo obtido de G através da remoção das arestas em F . Para
uma aresta e de G, escrevemos, por simplicidade, G − e em vez de
G− {e}.
Como ilustração vamos provar por indução em ||G|| que se G é um
grafo, então
∑
v∈V d(v) = 2||G||. Suponha que G é um grafo. Se ||G|| = 0,
então
∑
v∈V d(v) = 0, e não há mais nada a verificar. Suponha, então,
que ||G|| ⩾ 1. Selecione uma aresta e de G, e suponha que x e y são
as pontas de e. Considere o grafo H = G − e (tanto G quanto H tem
conjunto de vértices V ). Note que ||H|| = ||G|| − 1. Assim, por hipótese
de indução, ||H|| =
∑
v∈V dH(v). Ora, dH(x) = d(x)−1, dH(y) = d(y)−1
e dH(v) = d(v) para cada v ∈ V − {x, y}. Então∑
v∈V
d(v) =
∑
v∈V−{x,y}
d(v) + d(x) + d(y)
=
∑
v∈V−{x,y}
dH(v) + dH(x) + 1 + dH(y) + 1
=
∑
v∈V
dH(v) + 2
= 2||H||+ 2
= 2(||H||+ 1)
= ||G||.
Exercício 1.2. Prove o Corolário 1.1 por indução no número de
arestas.
10 TEORIA DOS GRAFOS
P
Figura 1.4: A figura ilustra um caminho
simples.
8 Para um inteiro não-negativo k,
[k] = {1, 2, . . . , k}.
Além disso, para inteiros ℓ, k, escreve-
mos [ℓ : k] para denotar o conjunto
{i ∈ Z | ℓ ⩽ i ⩽ k}.
Observe que [0] = ∅.
9 Com frequência, quando não houver
possibilidade de confusão, vamos escre-
ver v0vk-caminho.
10 Ou ainda outras variantes linguísticas
equivalentes.
11 Note que ℓ(P ) é, em geral, diferente de
|EP |, salvo se P for uma trilha.
12 Assim, por exemplo, vamos escrever
v0v1 . . . vk para destacar a sequência de
vértices de um caminho de v0 até vk .
P (vi, vj)
P1 · P2
Caminhos e outros animais
A noção de grafo e sua representação gráfica sugerem imediatamente
a noção de caminho. Vamos lidar com diversas variantes desta noção.
Seja G um grafo. Um caminho em G é uma sequência que alterna vérti-
ces e arestas de tal forma que as pontas de cada aresta na sequência são
os vértices que imediatamente precedem e sucedem a aresta na sequên-
cia.
Formalmente, um caminho é uma sequência, digamos P ,
v0e1v1 . . . ekvk
em que8
• k ⩾ 0,
• v0, . . . , vk ∈ V ,
• e1, . . . , ek ∈ E, e
• ei ≃ vi−1vi para cada i ∈ [k].
Vamos escrever V (P ) (ou VP ) para denotar o conjunto dos vértices de
P , isto é, {v0, . . . , vk}, e E(P ) (ou EP ) para denotar o conjunto das ares-
tas de P , isto é, {e1, . . . , ek}. Dizemos que P é um9 (v0, vk)-caminho (ou
um caminho de v0 até vk ou, ainda, um caminho que une v0 e vk10) e que
v0 é o início (ou a ponta inicial) de P e vk é o término (ou a ponta final) de
P . O comprimento de P , denotado por ℓ(P ), é o número k.11 É conveni-
ente muitas vezes confundir um caminho P com o grafo (VP , EP , ι|EP ).
Assim, por exemplo, se u ∈ VP , então dP (u) é o grau de u no grafo P .
Com esta identificação, podemos escrever |P | em vez de |V (P )| e ||P ||
em vez de |E(P )|. Às vezes, vamos nos interessar tão somente pelos
vértices de um caminho quando, então, vamos enumerar tão somente
os vértices.12 De forma similar, quando o interesse residir somente nas
arestas de um caminho, vamos, pois, tão somente enumerar as arestas.
No primeiro caso dizemos que um tal caminho é um caminho de vértices;
no segundo, um caminho de arestas. Muitas vezes vamos nos interessar
por certos segmentos de P . Assim, para 0 ⩽ i ⩽ j ⩽ k escrevemos
P (vi, vj) para denotar a sequência viei+1vi+1 . . . ejvj que constitui um
caminho que une os vértices vi e vj .
Caminhos são sequências finitas e estas podem ser concatenadas. A
concatenação dos caminhos P1 = v0e1v1 . . . ekvk e P2 = w0f1w1 . . . flwl
tais que vk = w0, denotada P1 · P2, é o caminho
v0e1v1 . . . ekvkf1w1 . . . flwl.
Trilhas e caminhos simples Dizemos que P é uma trilha se não repete
arestas, ou seja, ||P || = k = ℓ(P ). Dizemos que P é um caminho sim-
ples se não repete vértices, ou seja, |P | = k + 1. Naturalmente, se P é
um caminho simples, então P é uma trilha, mas, evidentemente, a re-
cíproca não é em geral verdadeira. A mesma nomenclatura usada para
NOÇÕES BÁSICAS 11
Figura 1.5: A figura ilustra um grafo que
é um caminho simples.
Figura 1.6: A figura ilustra um grafo que
é um ciclo.
13 Lembre-se que dada uma coleção não-
vazia X de subconjuntos de um certo
conjunto, dizemos que um elemento X ∈
X é maximal se
Y ⊇ X ⇒ Y = X
para cada Y ∈ X.
14 Ou, ainda, G[Y ] não é conexo sempre
que Y ⊆ V é tal que Y ⊃ X .
Figura 1.7: A figura ilustra um grafo co-
nexo.
Figura 1.8: Um grafo e suas duas compo-
nentes conexas.
caminhos é estendida para trilhas e caminhos simples. É conveniente,
como já fizemos anteriormente, identificar uma trilha P com o grafo
(VP , EP , ι|EP ).
Exercício 1.3. Seja G um grafo, e u, v ∈ V . Se P é um uv-caminho,
então existe um uv-caminho simples Q tal que
VQ ⊆ VP e EQ ⊆ EP .
Circuitos e ciclos Uma trilha P é um circuito se ℓ(P ) ⩾ 2 e o início
e o fim de P coincidem. Um ciclo é um circuito no qual, exceto pelo
início e pelo fim, nenhum outro vértice se repete na sequência. As-
sim, o circuito v0e1v1 . . . ekvk (donde k ⩾ 2 e v0 = vk) é um ciclo se
v0e1 . . . ek−1vk−1 é um caminho simples. A cintura de um grafo G que
possui pelo menos um ciclo é o comprimento de um ciclo de compri-
mento mínimo de G.
Finalmente, dizemos que um grafo G é um caminho simples (um ci-
clo) se existe um caminho simples (um ciclo) P em G tal que G =
(VP , EP , ι).
Exercício 1.4. Mostre que se um grafo possui um circuito de com-
primento ímpar, então também possui um ciclo de comprimento
ímpar.
Componentes conexas
Um grafo G é conexo se para cada u, v ∈ V existe um caminho que
une u e v. Uma componente conexa (ou, simplesmente, componente) de
um grafo G é uma parte maximal13X ⊆ V tal que o grafo G[X] é co-
nexo, isto é, é uma parte X ⊆ V tal que G[X] é conexo e se Y ⊆ V é
tal que Y ⊇ X e G[Y ] é conexo, então Y = X .14 Observe que se X
é uma componente de um grafo não-vazio G, então X ̸= ∅ uma vez
que G[{v}] é obviamente conexo para cada vértice v de G. É conveni-
ente, muitas vezes, confundir uma componente conexa X de um grafo
G com o grafo G[X]. Como de costume, tal convenção será utilizada
sempre que não houver possibilidade de confusão.
Lema 1.2. Seja G um grafo e X1, X2 ⊆ V . Se G[X1] e G[X2] são
conexos e X1 ∩X2 ̸= ∅, então G[X1 ∪X2] também é conexo.
Prova. É suficiente mostrar que existe um caminho de x1 até x2 para
cada x1 ∈ X1 e cada x2 ∈ X2. Sendo assim, seja x1 ∈ X1 e x2 ∈ X2.
Seja, também, x ∈ X1 ∩X2. Como G[X1] é conexo e x, x1 estão em X1,
então existe um caminho P1 de x1 até x. De forma similar, existe um
12 TEORIA DOS GRAFOS
Uma partição de um conjunto U é
um conjunto de partes não-vazias, e
duas a duas disjuntas, de U cuja
união é igual a U . Por exemplo,
{{1, 4}, {2, 5}, {3, 6, 7}} é uma partição
do conjunto [7].
c(G)
caminho P2 de x até x2. Segue daí que P1 · P2 é um caminho de x1 até
x2. Concluímos, assim, que G[X1 ∪X2] é conexo.
Corolário 1.2. Se X1 e X2 são componentes conexas de um grafo G,
então X1 = X2 ou X1 ∩X2 = ∅.
Prova. Suponha que X1 ∩X2 ̸= ∅. Pelo Lema 1.2, G[X1 ∪X2] é conexo.
A maximalidade de X1 implica que X1 = X1 ∪X2. A maximalidade de
X2 implica que X2 = X1 ∪X2. Logo, X1 = X2.
Corolário 1.3. O conjunto das componentesconexas de um grafo G é
uma partição de V .
O número de componentes conexas de um grafo G é denotado por
c(G). Todo vértice de um grafo pertence a uma e só uma componente
conexa do grafo; a componente conexa que contém um certo vértice x
é chamada de território de x.
Exercício 1.5. Suponha que um grafo G tem exatamente dois vér-
tices, digamos u e v, de grau ímpar. Mostre que existe um caminho
em G que une os vértices u e v.
Proposição 1. Se G é um grafo conexo e e ∈ E, então c(G− e) ⩽ 2.
Prova. Suponha que G é um grafo conexo e e ≃ xy é uma das arestas
de G. Seja X o território de x em G−e e Y o território de y em G−e. Os
grafos (G − e)[X] e (G − e)[Y ] são conexos. Logo, é suficiente mostrar
que V = X ∪ Y . Suponha que v ∈ V . Como G é conexo, então existe
um caminho simples P de v até x em G. Se e /∈ E(P ), então P é um
caminho de v até x em G − e, donde v ∈ X . Se e ∈ E(P ), então e é
a última aresta de P uma vez que P é simples. Assim, P (v, y) é um
caminho de v até y em G− e, donde v ∈ Y .
Corolário 1.4. Se G é um grafo e e ∈ E, então
c(G− e) ⩽ c(G) + 1.
Corolário 1.5. Se G é um grafo não-vazio, então c(G) ⩾ |G| − ||G||.
Prova. Vamos provar por indução em ||G|| que se G é não-vazio, então
c(G) ⩾ |G| − ||G||. Suponha que G é um grafo não-vazio. Se ||G|| = 0,
então c(G) = |G|, e não há mais nada a provar. Suponha ||G|| ⩾ 1.
NOÇÕES BÁSICAS 13
∇(X)
;; X
∇X
Xc
Figura 1.9: As arestas de cor azul consti-
tuem um corte ∇X . As margens do corte
são os conjuntos X e Xc. É claro que
∇X = ∇Xc. Note que todo caminho
de X até Xc usa uma aresta de ∇(X).
Figura 1.10: A remoção das arestas de cor
azul desconecta o grafo. No entanto, tais
arestas não constituem um corte.
15 Tal notação é uma abreviatura para as
afirmações
• v0v1v2 . . . vk é um caminho, e
• x = v0 e y = vk .
Escolha uma aresta e ∈ E. Por hipótese de indução, c(G − e) ⩾ |G −
e|+ ||G− e||. Segue daí que
c(G) ⩾ c(G− e)− 1
⩾ |G− e| − ||G− e|| − 1
= |G| − (||G|| − 1)− 1
= |G| − ||G||.
Corte de um conjunto de vértices
Seja G um grafo e X ⊆ V . O conjunto das arestas que têm uma
ponta em X e a outra em Xc é denotado por ∇(X). É evidente que
∇X = ∇Xc. Os conjuntos X e Xc são margens de ∇X . Uma parte K
de E é um corte se K = ∇X para algum X ⊆ V . Um corte é dito trivial
se uma de suas margens é vazia. Para cada X ⊆ V , a cardinalidade de
∇X , |∇X|, é denotada por dG(X) ou, como de hábito, simplesmente
d(X).
É claro que todo caminho que leva de um vértice x ∈ X até um
vértice y ∈ Xc usa uma aresta de ∇X . Logo, se G é conexo e ∇X ̸= ∅,
então G − ∇X não é conexo. Note, entretanto, que não é verdade que
num grafo conexo G se G −K não é conexo para algum K ⊆ E, então
K é um corte.
Lema 1.3. Se X é o território de um vértice s em um grafo G, então
∇X = ∅.
Prova. Suponha que X é o território de s e que x ∈ X . Então existe um
sx-caminho (de vértices), digamos P , em G. Admita que e ∈ ∇x e seja
y a ponta de e distinta de x. Ora, P · xy é um sy-caminho em G, donde
y ∈ X e, portanto, e /∈ ∇X . Concluímos, assim, que ∇X = ∅.
Teorema 1.1. Um grafo G é conexo se, e só se,
∇X ̸= ∅
sempre que ∅ ⊂ X ⊂ V .
Prova. (⇒) Suponha que G é conexo e que ∅ ⊂ X ⊂ V . Tome um
vértice x ∈ X e um vértice y ∈ Xc. Como G é conexo, então existe um
caminho 15
(x = v0)e1v1 . . . ek(vk = y)
tal que k > 0. Tome o maior i ∈ [0 : k] tal que vi ∈ X . De v0 ∈ X e
vk ∈ Xc vem que 0 ⩽ i < k. Ademais, a maximalidade de i implica que
vi+1 ∈ Xc, donde ei+1 ∈ ∇X e, portanto, ∇X ̸= ∅.
14 TEORIA DOS GRAFOS
(⇐) Suponha agora que ∇X ̸= ∅ sempre que ∅ ⊂ X ⊂ V . Seja X o
território de x. Pelo Lema 1.3, ∇X = ∅, donde X = ∅ ou X = V . Ora,
x está em X e, assim, X = V . Logo, existe um xy-caminho em G e,
portanto, G é conexo.
O próximo lema exibe uma condição suficiente que garante a cone-
xidade de um grafo.
Proposição 2. Se G é um grafo simples e γv ⩾ |G|/2 para cada
v ∈ V , então G é conexo.
Prova. Suponha que G é um grafo simples e γv ⩾ |G|/2 para cada v ∈
V . Suponha que ∅ ⊂ X ⊂ V . Observe que ∇X = ∇Xc. Renomeie X ,
se necessário, de tal forma que |X| ⩽ |Xc|. Neste caso, |X| ⩽ |G|/2.
Tome x ∈ X . Como γx ⩾ |G|/2, então x tem ao menos um vizinho em
Xc, donde ∇X ̸= ∅. Portanto, G é conexo.
Para um grafo conexo G, dizemos que um conjunto de arestas F ⊆ E
desconecta G se o grafo G − F não é conexo. Um conjunto minimal de
arestas que desconecta G é uma parte F de E tal que
• F desconecta G, e
• se F ′ ⊂ F , então G− F ′ é conexo.
O próximo lema estabelece que um tal conjunto F nada mais é que
um corte de G. Note, entretanto, que a recíproca não é verdadeira, ou
seja, não é verdade que todo corte é um conjunto minimal de arestas
que desconecta G salvo se as margens do corte induzirem subgrafos
conexos, como mostra a próxima proposição.
Proposição 3. Seja G um grafo conexo. Uma parte F de E é um
conjunto minimal de arestas que desconecta G se, e só se, existe
∅ ⊂ X ⊂ V tal que ∇X = F , e os grafos G[X] e G[Xc] são ambos
conexos.
Prova. (⇒) Suponha que F é um conjunto minimal de arestas que des-
conecta um grafo conexo G. Seja X uma componente conexa de G−F .
De G−F não conexo vem que ∅ ⊂ X ⊂ V . Vamos provar que F ⊆ ∇X .
Suponha que f é uma aresta em F . Como X é uma componente de
G− F , então ∇G−F (X) = ∅. A minimalidade de F implica que o grafo
H = G − (F − {f}) é conexo, donde ∇H(X) ̸= ∅, o que, combinado
com ∇G−F (X) = ∇H(X) − {f} = ∅, implica que ∇H(X) = {f}. Mas,
∇H(X) ⊆ ∇X . Segue daí que f ∈ ∇X e, portanto, F ⊆ ∇X . Por
outro lado, ∇G−FX = ∅ implica que ∇X ⊆ F . Logo, ∇X = F , como
queríamos.
(⇐)Vamos provar a contra-positiva: se G[X] ou G[Xc] não é co-
nexo, então ∇X não é um conjunto minimal de arestas que desco-
necta G. Ajuste a notação de tal forma que H = G[X] não é conexo.
NOÇÕES BÁSICAS 15
16 Isto quer dizer que não existe X ⊆ V
tal que ∇X = L.
bom
17 Verifique!
18 Verifique!
F
R
Figura 1.11: A figura ilustra um par bom
(S, F ). Se um vértice está em S − F , en-
tão todos os seus vizinhos estão em S.
Pelo Lema 1.1, existe ∅ ⊂ Y1 ⊂ X tal que ∇HY1 = ∅. Ponha Y2 = X−Y1.
Segue daí que não existe aresta de G com uma ponta em Y1 e a outra
em Y2 o que, por sua vez, implica que ∇X = ∇Y1 ∪∇Y2. Por hipótese,
G é conexo, donde ∇Y1 ̸= ∅ e ∇Y2 ̸= ∅. Logo, ∇Y1 ⊂ ∇X e ∇Y2 ⊂ ∇X .
Segue daí que existem partes próprias de ∇X que desconectam G. Por-
tanto, ∇X não é um conjunto minimal de arestas que desconecta G.
Exercício 1.6. Suponha que G é um grafo conexo e X é uma parte
própria e não-vazia de V tal que G[X] e G[Xc] são ambos conexos.
Mostre que se Z é uma parte própria e não-vazia de V tal que
∇Z = ∇X , então Z = X ou Z = Xc.
Um corte K ⊆ E em um grafo G é minimal se L não é um corte para
cada L ⊂ K 16. O próximo lema caracteriza quando um corte é minimal
em um grafo conexo.
Corolário 1.6. Seja G um grafo conexo e X uma parte própria e não-
vazia de V . Então ∇X é um corte minimal se, e só se, G[X] e G[Xc] são
conexos.
Exercício 1.7. Seja G um grafo. Mostre que se X é uma parte mini-
mal e não-vazia de V que é Γ -fechada, então X é uma componente
conexa de G.
Algoritmo de busca
O propósito agora é exibir um algoritmo que determina o território
de um vértice de um grafo e, consequentemente, uma das componentes
conexas de tal grafo. Vamos admitir que um grafo G é dado pela sua
função de vizinhança Γ . Seja s um dos vértices de G. A correção do
algoritmo depende da seguinte noção. Dizemos que um par (S, F ) é
bom se
• s ∈ S e S é uma parte do território de s em G,
• F ⊆ S, e
• Γx ⊆ S para cada x ∈ S − F .
Note que ({s}, {s}) é um par bom. Suponha que (S, F ) é bom. Admita,
primeiro, que F = ∅. Neste caso, Γx ⊆ S para cada x ∈ V , donde
∇S = ∅. Como S é uma parte do território de s e ∇S = ∅, então S é
uma componente conexa de G. Admita, agora, que F ̸= ∅. Seja x ∈ F .
Há duas possibilidades. Se Γx ⊆ R, então (R,F − {x}) é também
bom.17 Se Γx − R ̸= ∅, então selecione y ∈ Γx − R e note que o par
(S ∪ {y}, F ∪ {y}) também é bom.18
16 TEORIA DOS GRAFOS
X
Xc
Figura 1.12: A figura ilustra um grafo bi-
partido G com bipartição X,Xc. Note
quetoda aresta tem exatamente uma das
pontas no conjunto X , assim, não há
arestas com ambas as pontas em X ou
com ambas as pontas em Xc.
C ∩Xc
C ∩X Cc ∩X
Cc ∩Xc
C
e
Figura 1.13: Toda aresta, exceto e, tem
uma ponta em X e a outra em Xc. As-
sim. Y = (C ∩ X) ∪ (Cc ∩ Xc) é uma
bipartição de G.
Grafos bipartidos
Um grafo G é bipartido se existe X ⊆ V tal que toda aresta tem uma
ponta em X e a outra em Xc; o par X,Xc é chamado de bipartição de
G e X e Xc são os lados da bipartição. No entanto, vamos abreviar e
dizer simplesmente que X é uma bipartição de G uma vez que o outro
participante da bipartição, o conjunto Xc, pode ficar subentendido.
Dizemos que um ciclo C em um digrafo D é ímpar se o seu compri-
mento, ℓ(C), é ímpar. O próximo teorema caracteriza grafos biparti-
dos.
Teorema 1.2. Um grafo G é bipartido se, e só se, G é livre de ciclos
ímpares.
Prova. (⇒) Suponha que X é uma bipartição de G. Note que se P é
uma trilha que começa e termina num mesmo lado da bipartição, então
P tem comprimento par. De fato, suponha que P = v0v1 . . . vk é tal que
v0 ∈ X ⇔ vk ∈ X . Então
vi−1 ∈ X ⇔ vi ∈ Xc
para cada i ∈ [k] o que implica que k é par. Portanto, se G tem um ciclo,
então tal ciclo tem comprimento par.
(⇐)Vamos mostrar por indução em ||G|| que se G é um grafo livre de
ciclos ímpares, então G é bipartido. O grafo vazio é bipartido. Suponha,
então, que G é um grafo livre de ciclos ímpares e que ||G|| ⩾ 1. Seja
e ≃ xy uma aresta de G, e considere o grafo H = G − e. É claro que H
é livre de ciclos ímpares e ||H|| < ||G||.
Assim, por hipótese de indução, H é bipartido. Seja X uma biparti-
ção de H e suponha que x ∈ X . Se y ∈ Xc, então X é uma bipartição de
G, e não há mais nada a provar. Suponha, então, que y ∈ X . Note que
todo caminho simples cuja origem e destino está num mesmo lado da
bipartição tem comprimento par. Isso, aliado a e ∈ E, implica que não
existe um caminho de x até y em G. Seja C a componente de G− e que
contém x. Então y ∈ Cc. Considere o conjunto Y = (C∩X)∪(Cc∩Xc).
Então Y c = (C∩Xc)∪(Cc∩X). Vamos mostrar que Y é uma bipartição
de G. Note primeiro que a ponta x de e está em C ∩X e a ponta y de e
está Cc ∩X , donde x ∈ Y e y ∈ Y c. Suponha que f ∈ E − {e}. Temos
dois casos. Suponha, primeiro, que f é uma aresta de G[C]. Como X é
uma bipartição de G, então f tem uma de suas pontas, digamos u, em
X e, a outra, digamos v, em Xc. Mas, u, v ∈ C, donde u ∈ C ∩ X e
v ∈ C ∩ Xc e, portanto, u ∈ Y e v ∈ Y c. Suponha que f é uma aresta
de G[Cc]. Como X é bipartição de G, então f tem uma de suas pontas,
digamos u, em Xc e, a outra, digamos v, em X . Mas, u, v ∈ Cc, donde
u ∈ Cc ∩Xc e v ∈ Cc ∩X e, portanto, u ∈ Y e v ∈ Y c. Logo, Y é uma
bipartição de G.
NOÇÕES BÁSICAS 17
Figura 1.14: A figura ilustra uma árvore.
Vamos exibir uma prova alternativa da recíproca. Suponha, então, que
G é um grafo não-vazio livre de ciclos ímpares. Podemos supor que G
é conexo uma vez que o argumento que segue pode ser aplicado a cada
uma das componentes de G quando G é desconexo. Seja s ∈ V e
dist(s, x) = min{ℓ(P ) | P é um sx-caminho em G}
para cada x ∈ V e
X = {x ∈ V | dist(s, x) é par}.
Vamos mostrar que X é uma bipartição de G. Para isso, é suficiente
mostrar que não há arestas com ambas as pontas em X ou ambas as
pontas em Xc. Suponha que x1 ̸= x2 são vértices de G tais que x1, x2 ∈
X ou x1, x2 ∈ Xc. Vamos mostrar que G não possui uma aresta com
pontas x1 e x2. Seja Pi um sxi-caminho simples de comprimento mí-
nimo de s até xi para i = 1, 2. Escreva
P1 = (s = v0)v1v2 . . . (vk = x1).
Seja i ∈ {0, 1, . . . , k} o maior índice tal que vi ∈ P2. A escolha de
i implica P1(vi, x1) ∩ P2(vi, x2) = {vi}. A minimalidade de P1 im-
plica que ℓ(P1(s, vi))+ ℓ(P1(vi, x1)) ⩽ ℓ(P2(s, vi))+ ℓ(P1(vi, x1)), donde
ℓ(P1(s, vi)) ⩽ ℓ(P2(s, vi)). De forma similar, a minimalidade de P2 im-
plica que ℓ(P2(s, vi)) ⩽ ℓ(P1(s, vi)). Assim,
ℓ(P1(s, vi)) = ℓ(P2(s, vi)).
Ora, como ℓ(P1) e ℓ(P2) têm a mesma paridade, então as paridades de
ℓ(P1(vi, x1)) e ℓ(P2(vi, x2)) também são iguais. Isto, combinado com a
ausência de ciclos ímpares em G, implica que não há aresta em G com
pontas x1 e x2.
Árvores
Um grafo é dito acíclico (ou uma floresta) se não possui ciclos. Não
é difícil ver que se um grafo G é acíclico, então existe no máximo um
único caminho simples unindo dois vértices arbitrários de G. De fato,
suponha que x, y são vértices de G e que P1 e P2 são dois caminhos
simples distintos unindo x e y. Observe que, neste caso, ℓ(P1) ⩾ 1 e
ℓ(P2) ⩾ 1. Escreva P1 = v0v1 . . . vk com k ⩾ 1 e seja i o menor inteiro
em {1, . . . , k} tal que vi ∈ P2. Então P1(v0, vi) · P−12 (vi, v0) é um ciclo,
como queríamos.
Os grafos conexos e acíclicos têm um papel fundamental na Teoria
dos Grafos e, por isso, recebem um nome especial: árvores. Em virtude
da discussão acima, em uma árvore existe exatamente um caminho sim-
ples unindo cada par de vértices. A recíproca, ou seja, que em um grafo
18 TEORIA DOS GRAFOS
19 Justifique!
no qual cada par de vértices é unido por exatamente um caminho sim-
ples é uma árvore também é verdadeira: o fato de existir um caminho
entre cada par de vértices implica que o grafo é conexo; o fato de existir
exatamente um implica que o grafo é acíclico. Portanto, é uma árvore.
As verificações formais desses fatos são bem simples e, por isso, são
deixadas para o leitor. Vamos, entretanto, destacar este último resul-
tado.
Teorema 1.3. Um grafo é uma árvore se, e só se, cada par de vértices é
unido por exatamente um único caminho simples.
Corolário 1.7. Se T é uma árvore e e ∈ ET , então T − e não é conexo.
Prova. Suponha que T é uma árvore e e ≃ xy ∈ ET . Ora xey é um
caminho simples de x até y em T e, portanto, é único. Segue daí que
T − e não contém nenhum caminho de x até y, donde T − e não é
conexo.
O seguinte exercício será útil para o próximo teorema.
Exercício 1.8. Se C é um ciclo e K é um corte de um grafo G, então
|EC ∩K| mod 2 = 0.
Teorema 1.4. Um grafo conexo T é uma árvore se, e só se, T − e não é
conexo para cada e ∈ ET .
Prova. (⇒) Suponha que T é uma árvore e e ∈ ET . O Corolário 1.7
implica que se T − e não é conexo, como queríamos.
(⇐) Suponha agora que T é um grafo conexo para o qual T − e não
é conexo para cada e ∈ ET . Vamos provar por indução em |T | que T
é uma árvore. Se |T | ⩽ 1, o resultado segue por vacuidade. Suponha,
então, que |T | ⩾ 2. Como T é conexo, então ET ̸= ∅. Tome, assim, uma
aresta e ∈ ET e considere o grafo T − e. Ora, a conexidade de T e a
desconexidade de T − e implicam que c(T − e) = 2. Sejam, pois, T1
e T2 as componentes conexas de T − e. Agora, para cada i ∈ {1, 2} e
para cada aresta f ∈ E(Ti), o grafo Ti − f não é conexo.19 Assim, por
hipótese de indução, T1 e T2 são árvores o que, por sua vez, implica que
T é uma árvore. De fato, suponha, por um momento, que C é um ciclo
de T . Como T1 e T2 são árvores, então C não é um ciclo de T1 e nem de
T2. Logo, C deve usar a aresta e. No entanto, EC ∩∇(VT1) = {e}, o que
contraria o exercício anterior. Portanto, T é uma árvore.
Há uma relação simples envolvendo o número de vértices e o nú-
mero de arestas de uma árvore.
NOÇÕES BÁSICAS 19
20 Uma vez que um grafo conexo com um
vértice e nenhuma aresta é uma árvore, e
o grafo vazio não satisfaz as hipóteses da
afirmação.
21 Verifique!
x
y z
Figura 1.15: Os vértices x, y e z são folhas
da árvore ilustrada na figura.
Teorema 1.5. Um grafo T é uma árvore não-vazia se, e só se, T é conexo
e ||T || = |T | − 1.
Prova. (⇒)Vamos provar por indução em |T | que se T é uma árvore
não-vazia, então ||T || = |T |−1. Seja T uma árvore não-vazia. Se |T | = 1,
então ||T || = 0 e, portanto, ||T || = |T | − 1. Suponha, então, que |T | ⩾ 2.
Como T tem pelo menos dois vértices e T é conexo, então ET ̸= ∅.
Selecione uma aresta e ∈ ET . Ora, o grafo T − e não é conexo. Pelo
Lema 1.4, c(T − e) = 2. Cada uma das componentes de T − e, digamos
T1 e T2, é acíclica pois T é acíclico. Ademais, tanto T1 quanto T2 são
conexas. Logo, T1 e T2 são árvores e, portanto, por hipótese de indução,||T1|| = |T1| − 1 e ||T2|| = |T2| − 1. Agora,
||T || = ||T1||+ ||T2||+ 1 = |T1| − 1 + |T2| − 1 + 1 = |T | − 1,
como queríamos.
(⇐)Vamos provar por indução em |T | que se T é conexo e ||T || =
|T | − 1, então T é uma árvore. O resultado vale quando |T | ⩽ 1.20
Suponha que |T | > 1. Como T é conexo, então δ(T ) ⩾ 1. Vamos mos-
trar que δ(T ) = 1. Para isso, vamos mostrar que se um grafo G é tal
que δ(G) ⩾ 2, então ||G|| ⩾ |G|. De fato, 2||G|| =
∑
v∈VG d(v) ⩾ 2|G| e,
portanto, ||G|| ⩾ |G|, como queríamos. Ora, ||T || = |T | − 1, logo, pela
afirmação anterior, δ(T ) ⩽ 1. Assim, δ(T ) = 1. Selecione um vértice x
de T que d(x) = 1. Como o grafo T é conexo, então T − x também é
conexo, e ||T − x|| = ||T || − 1 = |T | − 1 − 1 = |T − x| − 1. Além disso,
|T − x| < |T |, donde T − x, por hipótese de indução, é uma árvore o
que, por sua vez, acarreta que T é também uma árvore.21
Vamos esboçar no exercício abaixo uma prova alternativa para a afir-
mação se T é uma árvore não-vazia, então ||T || = |T | − 1. Para isso, é
conveniente introduzir a seguinte definição. Uma folha em uma árvore
T é um vértice v de T tal que d(v) = 1.
Exercício 1.9. Primeiro, você vai provar que se T é uma árvore e
|T | ⩾ 2, então T possui uma folha. Sugestão: escolha um caminho
simples de comprimento máximo de T e observe as suas pontas.
Agora, você pode tentar provar o Teorema 1.5. Sugestão: faça uma
prova por indução em |T | no qual o passo da indução consiste em
remover uma folha de T .
Exercício 1.10. Prove que um grafo não-vazio T é uma árvore se,
e só se, T é acíclico e ||T || = |T | − 1.
Árvores geradoras Dizemos que um grafo T é uma árvore geradora de
um grafo G se
20 TEORIA DOS GRAFOS
22 Uma vez que se t1, t2 ∈ VT , então
existe um caminho de T de t1 até t2; tal
caminho é também um caminho de U .
23 Poderíamos argumentar de uma forma
menos construtiva. A prova é por indu-
ção no número de ciclos de G. Se G não
possui ciclos, então G é uma árvore gera-
dora, e não há mais nada a provar. Supo-
nha, então, que G possui ao menos um
ciclo e seja e uma aresta em um de tais
ciclos. Você, agora, deve verificar que o
grafo G−e é conexo, donde, por hipótese
de indução, possui uma árvore geradora
T ; é claro que T é também uma árvore
geradora de G. Isto completa a prova.
r
t1 t2
C1 C2
Figura 1.16: As arestas pretas são arestas
de T ; as vermelhas, de EG − T .
• T é uma árvore, e
• T é um subgrafo gerador de G.
Observe que se T é uma árvore geradora de G, então a conexidade T
implica na conexidade de G. Não é difícil intuir que todo grafo conexo
possui uma árvore geradora.
Teorema 1.6. Um grafo G possui uma árvore geradora se, e só se, G é
conexo.
Prova. A discussão precedente mostra que se G possui uma árvore ge-
radora, então G é conexo. Vamos, então, provar a recíproca. Suponha
que G é conexo. Admita que ∅ ≠ X ⊆ V é tal que G[X] possui uma
árvore geradora. Um tal X evidentemente existe uma vez que G[{v}]
é uma árvore para cada v ∈ V . Suponha, ademais, que X ⊂ V . Seja
T uma árvore geradora de G[X]. Como G é conexo, então ∇X ̸= ∅.
Seja e ∈ ∇X e considere o subgrafo U = G[ET ∪ {e}]. Seja x a ponta
de e em X e y a ponta de e em Xc. Vamos mostrar que U é uma ár-
vore geradora de G[X ∪ {y}]. Ora, U é um grafo conexo. Para verificar
isso, basta provar22 que existe um caminho em U que une t e y para
cada t ∈ VT . Por hipótese, existe um caminho P que une t e x em T ,
donde P · xey é um caminho de t até y em U . Logo, U é conexo. Além
disso, U é acíclico uma vez que T é acíclico e dU (y) = 1. Portanto, U é
uma árvore geradora de G[X ∪ {y}]. Assim, se X é uma parte maximal
de V tal que G[X] possui uma árvore geradora, então X = V , como
queríamos.23
Árvores de busca em profundidade
Seja T uma árvore não-vazia e r um de seus vértices. Como de cos-
tume, para simplificar, vamos confundir uma árvore com o seu con-
junto de arestas. Podemos definir uma ordem parcial sobre os vértices
de T da seguinte forma. Para cada x, y ∈ VT , dizemos que x e y são
comparáveis em (T, r) se x ∈ V (T (r, y)), ou seja, se x está no caminho de
r até y em T ou y ∈ V (T (r, x)), ou seja, se y está no caminho de r até x
em T .
Seja T uma árvore geradora de um grafo G e r ∈ V . Dizemos que T é
uma árvore de busca em profundidade com raiz r se x e y são comparáveis
em (T, r) sempre que e ≃ xy ∈ E − T .
Teorema 1.7. Se G é um grafo conexo e r ∈ V , então G possui uma
árvore de busca em profundidade com raiz r.
Prova. A prova é por indução em |G|. Suponha que G é um grafo co-
nexo e r ∈ V . Se |G| = 1, então G é uma árvore de busca em profundi-
dade com raiz r.
NOÇÕES BÁSICAS 21
24 Isto é, ℓ(P ) ⩾ 1.
Suponha, então, que |G| ⩾ 2. Sejam C1, . . . , Ck com k ⩾ 1 as com-
ponentes conexas de G − r. Para cada i ∈ [k], seja ti um vizinho de
r em Ci e ei uma aresta com pontas r e ti. Por hipótese de indução,
existe uma árvore de busca em profundidade Ti de G[Ci] com raiz ti
para cada i ∈ [k]. É claro que T = {ei | i ∈ [k]} ∪
⋃
i∈[k] Ti é uma ár-
vore geradora de G. Vamos mostrar que (T, r) é uma árvore de busca
em profundidade. Note que não há arestas cujas pontas estão em di-
ferentes componentes de G − r. Seja e ∈ EG − T . Então (i) ou ambas
as pontas de e, digamos x e y, estão em Ci para algum i, donde x e y
são comparáveis em (Ti, ti) e, assim, x e y também são comparáveis em
(T, r) ou (ii) uma das pontas de e é r e, neste caso, evidentemente r e s
são comparáveis em (T, r), onde s é a outra ponta de e. Portanto, T é
uma árvore de busca em profundidade de G com raiz r.
Vamos, agora, fornecer uma prova alternativa deste último teorema.
A prova depende do conceito de H-caminho simples que passaremos a
definir. Seja G um grafo e H um subgrafo de G. Dizemos que um ca-
minho simples P , não-trivial,24 é um H-caminho simples se P e H com-
partilham tão somente o vértice inicial e o vértice final de P .
Transversal de um conjunto Vamos definir a noção de transversal de um
conjunto. Este será o primeiro contato com esta noção que terá um pa-
pel fundamental nos capítulos futuros. Suponha que U é um conjunto
e que X ⊆ 2U . Dizemos que T ⊆ U é uma transversal de X se
T ∩X ̸= ∅
para cada X ∈ X. Uma transversal T de X é dita minimal se U não é
transversal de X para cada U ⊂ T .
Exemplo 1. Considere o conjunto U = {1, 2, 3, 4} e
X = {{1, 2}, {1, 3}, {2, 3, 4}} ⊆ 2U .
Os conjuntos {1, 2} e {1, 4} são exemplos de transversais minimais
de X. Note que qualquer superconjunto de uma transversal é tam-
bém uma transversal.
Suponha que T é uma árvore geradora de um grafo G. Se ∅ ̸= X ⊂
V , então a conexidade de T implica que ET ∩ ∇X ̸= ∅. Portanto, as
arestas de uma árvore geradora de G constituem uma transversal do
conjunto
{∇X | ∅ ≠ X ⊂ V }.
Exercício 1.11. Seja G um grafo conexo, e x, y vértices de G. Mostre
que se P é um caminho de G que une x e y, então as arestas de P
22 TEORIA DOS GRAFOS
são uma transversal do conjunto
{∇X | X ⊆ V, x ∈ X, y ∈ Xc}.
Note, no enunciado do próximo teorema, a identificação de um con-
junto de arestas com o grafo induzido por este conjunto de arestas.
Teorema 1.8. Seja G um grafo conexo e C = {∇X | ∅ ≠ X ⊂ V }. Uma
parte T de E é uma árvore geradora de G se, e só se, T é uma transversal
minimal de C.
Prova. O resultado é claro se |G| = 1. Logo, vamos supor que |G| ⩾ 2.
Suponha que T é uma transversal minimal de C. Vamos mostrar que T é
um subgrafo conexo e gerador de G. Para isso, tome ∅ ≠ X ⊂ V . Como
T é uma transversal de C, então T ∩ ∇X ̸= ∅, mas T ∩ ∇X = ∇T (X)
donde, pelo Lema 1.1, T é conexo. Além disso, a escolha de X como
uma parte própria e não-vazia de V implica que T é gerador. Logo, T
é um subgrafo gerador e conexo de G. Seja e uma aresta de T . Como
T é uma transversal minimal de C, então T − e não é uma transversal.
Logo, existe ∅ ≠ X ⊂ V tal que
∇T−e(X) = (T − e) ∩∇(X) = ∅,
donde T − e não é conexo. Concluímos, assim, que T é conexo e T − e
não é conexo para cada e ∈ T o que, de acordo com o Teorema 1.4,
implica que T é uma árvore.
Exercício 1.12. Seja G um grafo conexo, e x, y vérticesde G. Mostre
que o conjunto das arestas de um caminho P de G que une x e y é
uma transversal minimal de
{∇X | X ⊆ V, x ∈ X, y ∈ Xc}
se, e só se, P é simples
Grafos simples
Um grafo G é simples se para cada e, f ∈ E se e ̸= f , então ι(e) ̸= ι(f),
ou seja, não existem duas arestas com as mesmas pontas. Neste caso,
por simplicidade, convém dispensar a função de incidência, e conside-
rar um grafo simples como um par (V,E) tal que V é, como de cos-
tume, um conjunto finito e E ⊆
(
V
2
)
. Assim, cada aresta é um par
não-ordenado de vértices distintos.
Cliques e conjuntos independentes Seja G um grafo e X ⊆ V . Dizemos
que X é um clique se G[X] é completo, ou seja, se para cada x1, x2 ∈ X ,
NOÇÕES BÁSICAS 23
Figura 1.17: Um grafo simples e com-
pleto com 6 vértices, K6.
X
Xc
v
Γv
se x1 ̸= x2 então existe e ∈ E tal que e ≃= x1x2. Para cada k ∈ N, uma
parte X de V é um k-clique se X é um clique e |X| = k. Um 3-clique é
também chamado de triângulo. Dizemos que uma parte X de V é um
conjunto independente se E(G[X]) = ∅, ou seja, se não existe aresta de G
com ambas as pontas em X . Por outro lado, dizemos que um conjunto
C de vértices de G é uma cobertura de vértices se toda aresta de G tem ao
menos uma de suas pontas em C. Assim, se X é independente, então
toda aresta de G tem ou as duas pontas em Xc ou exatamente uma
ponta em Xc e, portanto, Xc é uma cobertura de vértices.
Um grafo G é completo se V é um clique. Se G é um grafo simples e
completo, então
||G|| =
∣∣∣(V
2
)∣∣∣ = |G|(|G| − 1)
2
.
Usualmente escrevemos Kn para denotar um grafo simples e completo
com n vértices.
Teorema 1.9 (Mantel). Se G é um grafo simples livre de triângulos,
então ||G|| ⩽ |G|2/4.
Primeira prova. A prova depende do seguinte lema.
Lema 1.4. Para todo natural n, max{k(n− k) | k ∈ [0 : n]} ⩽ n2/4.
Prova. O resultado é óbvio se n = 1. Assim, vamos supor que n ⩾ 2. É
evidente que existe a ∈ [0 : n] tal que a(n− a) = max{k(n− k) | k ∈ [0 :
n]}. É fácil ver que n ⩾ 2 implica 0 < a < n. Note que
(a−1)(n−(a−1)) ⩽ a(n−a) ⇔ an−n−a2−1+2a ⩽ an−a2 ⇔ 2a ⩽ n+1,
donde a ⩽
n+ 1
2
⩽
⌊n+ 1
2
⌋
=
⌈n
2
⌉
. Além disso,
(a+ 1)(n− (a+ 1)) ⩽ a(n− a) ⇔ 2a ⩾ n− 1,
donde a ⩾
n− 1
2
⩾
⌈n− 1
2
⌉
=
⌊n
2
⌋
. Logo, a =
⌊n
2
⌋
ou a =
⌈n
2
⌉
. Final-
mente,
a(n− a) =
⌈n
2
⌉⌊n
2
⌋
⩽
n2
4
,
como queríamos.
Suponha que G é um grafo simples livre de triângulos. Seja v um
vértice de grau máximo de G, digamos k. Como G é livre de triângulos,
24 TEORIA DOS GRAFOS
então Γv é um conjunto independente. Seja X = {v} ∪ Γv. Então,
||G|| ⩽ k +
∑
v∈Xc
d(x)
⩽ k +
∑
v∈Xc
k
= k + k(|G| − k − 1) = k(|G| − k)
⩽
|G|2
4
,
onde a última desigualdade segue do Lema 1.4.
Segunda prova. Vamos fornecer uma prova alternativa do Teorema de
Mantel. Desta vez vamos provar por indução em |G| que
se G é um grafo simples e ||G|| > |G|2/4,
então G possui triângulos.
Suponha que G é um grafo simples e ||G|| > |G|2/4. O resultado segue
imediatamente se |G| ⩽ 2 em virtude da ausência de grafos com não
mais que dois vértices satisfazendo a hipótese do teorema. Suponha,
então, que |G| ⩾ 3. É claro que, neste caso, E ̸= ∅. Seja, então, xy uma
aresta de G e G′ o grafo G− {x, y}. Temos dois casos:
Caso 1 ||G′|| > |G′|2/4.
Por hipótese de indução, G′ tem um triangulo, e tal triângulo é tam-
bém um triângulo de G, pois G′ é subgrafo de G.
Caso 2 ||G′|| ⩽ |G′|2/4.
Seja n = |G|. Note que
||G|| − ||G′|| > n
2
4
− (n− 2)
2
4
= n− 1.
Então existem pelo menos n − 1 arestas com uma das pontas em
{x, y} e a outra em V − {x, y}. Mas |V − {x, y}| = n − 2, donde,
pelo Princípio da Casa de Pombos, existe z ∈ V − {x, y} tal que
z ∈ Γx ∩ Γy. Portanto, G[{x, y, z}] é um triângulo.
Lema 1.5. Se G é um grafo simples e δ(G) ⩾ 2, então G possui ciclo.
Prova. Seja P := x0x1 . . . xk um caminho maximal de G. Como δ(G) ⩾
2 vem que d(x0) ≥ 2, ou seja, x0 possui um vizinho distinto de x1. Ade-
mais, todo vizinho de x0 está em P caso contrário poderíamos estender
P contrariando, assim, a maximalidade de P . Portanto, existe i tal que
2 ≤ i ≤ k e xi é vizinho de x0. Agora, x0x1 . . . xix0 é um ciclo de G.
NOÇÕES BÁSICAS 25
25 Considere o conjunto C cujos elemen-
tos são os grafos simples G tais que
||G|| ⩾ |G|+ 4 e G não possui dois ciclos
disjuntos nas arestas. Queremos mostrar
que C = ∅. Para isso, vamos admitir que
C ̸= ∅. Considere o conjunto Z = {||G||+
|G| | G ∈ C}. Como C é não-vazio,
então Z é um conjunto não-vazio de in-
teiros não-negativos e, portanto, possui
um menor elemento, digamos m. Seja,
então, G ∈ C tal que ||G|| + |G| = m.
Este é o tal contra-exemplo minimal. Ob-
serve que se H é um grafo simples tal que
||H|| + |H| < m, então H /∈ C, donde H
possui dois ciclos disjuntos nas arestas.
26 Lembre-se que a cintura de um grafo
que contém ciclos é o comprimento de
um menor ciclo.
Lema 1.6. Se G é um grafo simples e ||G|| ⩾ |G|, então G possui ciclo.
Prova. Vamos provar por indução em |G| que se ||G|| ⩾ |G|, então G
possui um ciclo. Seja, então, G um grafo tal que ||G|| ⩾ |G|. Se δ(G) ⩾ 2
então, pelo Lema 1.5, G possui um ciclo. Assim, suponha que δ(G) < 2.
Seja x um vértice de G com d(x) ⩽ 1 e considere o grafo H = G − x.
Então
||H|| ⩾ ||G|| − 1 ⩾ |G| − 1 = |H|.
Sendo assim, por hipótese de indução, H possui um ciclo C. Como H
é um subgrafo de G segue que C também é um ciclo de G. Isto finaliza
a prova do lema.
Proposição 4. Se G é um grafo simples e ||G|| ⩾ |G| + 4, então G
possui dois ciclos disjuntos nas arestas.
Prova. A prova é por contradição. Seja G um contra-exemplo para o
lema com ||G||+ |G| mínimo25. Observe, primeiro, que
|G| ⩾ 5 (1.1)
uma vez que nenhum grafo com menos de 5 vértices satisfaz a hipótese
da proposição. Afirmamos que
||G|| = |G|+ 4. (1.2)
Suponha que ||G|| > |G| + 4. Seja e uma aresta de G e H o grafo G − e.
Então ||H|| ⩾ |H|+ 4. O grafo H não pode ser um contra-exemplo pois
||H|| + |H| < ||G|| + |G|. Assim, H satisfaz o lema, ou seja, H possui
dois ciclos disjuntos nas arestas. Mas, H é um subgrafo de G donde
tais ciclos também são ciclos de G. Esta contradição prova (1.2).
Agora, mostraremos26 que
a cintura de G é pelo menos 5. (1.3)
Suponha que G possua um ciclo C tal que ||C|| ⩽ 4. Considere o grafo
H := G − E(C). Temos que ||H|| ⩾ ||G|| − 4 = |G| = |H|. Logo, pelo
Lema 1.6, H possui um ciclo C ′. Portanto, C e C ′ são ciclos disjuntos
nas arestas de G. Esta contradição prova (1.3).
Temos, também, que
δ(G) ⩾ 3. (1.4)
Suponha que δ(G) ⩽ 2. Seja x um vértice de G com d(x) ⩽ 2. Suponha,
inicialmente, que d(x) ⩽ 1. O grafo H = G − x é tal que ||H|| ⩾ ||G|| −
1 = |G| + 4 − 1 = |H| + 4. Logo, H satisfaz as condições do lema.
Como H tem menos vértices que G, segue que H possui dois ciclos,
digamos C e C ′, disjuntos nas arestas. No entanto, H é um subgrafo
26 TEORIA DOS GRAFOS
x
y z y z=⇒
Figura 1.18: A figura ilustra a operação
envolvida na construção de H quando
d(x) = 2.
de G donde C e C ′ são ciclos de G, uma contradição. Suponha, agora,
que d(x) = 2. Denote por y e z os vizinhos de x. Note que, em virtude
de (1.3), yz não é uma aresta de G. O grafo H = (G− x) + yz é tal que
||H|| = ||G|| − 1 = |G|+ 4− 1 = |H|+ 4. Assim, H satisfaz a hipótese do
lema e H é menor que G. Vem daí que H possui ciclos C,C ′ disjuntos
nas arestas. Se tanto C quanto C ′ não incluem a aresta yz então C e C ′
também são ciclos disjuntos de G o que é uma contradição.
Suponha, pois, que um dos ciclos, digamos C, inclua yz. Então tro-
que na sequência que determina C o segmento yz pelo segmento yxz
e seja C ′′ o ciclo assim obtido. Com isto, temos que C ′ e C ′′ são ciclos
disjuntos nas arestas de G. Novamente uma contradição. Isto completa
a prova de (1.4).
Afirmamos que
|G| ⩽ 8. (1.5)
De fato. Suponha que |G| ⩾ 9. Como ||G|| = |G|+ 4 vem que
d(G) = 2
||G||
|G|
= 2
|G|+ 4
|G|
= 2 +
8
|G|
.
Agora, |G| ⩾ 9 implica d(G) < 3 donde δ(G) ⩽ 2. No entanto, isto
contraria (1.4). Isto prova (1.5).
Para completar a prova do lema basta mostrar que não existe ne-
nhum grafo G satisfazendo simultaneamente as seguintesproprieda-
des:
• ||G|| = |G|+ 4,
• cintura de pelo menos 5,
• δ(G) ⩾ 3 e
• 5 ⩽ |G| ⩽ 8.
A prova disto é deixada para o leitor.
Exercício 1.13. Mostre que se G é um grafo simples e G possui k
componentes conexos, então
||G|| ⩽ (|G| − k + 1)(|G| − k)
2
.
	Noções básicas
	Grafos
	Corte e grau de um vértice
	Vizinhança de um vértice
	Subgrafos
	Caminhos e outros animais
	Componentes conexas
	Corte de um conjunto de vértices
	Algoritmo de busca
	Grafos bipartidos
	Árvores
	Árvores de busca em profundidade
	Grafos simples