04.05.2008
Quarta lista de exercı́cios — Introdução à Teoria dos grafos
Depto. de Matemática – UnB
1. Jair Donadelli Jr., Algoritmos e Teoria dos Grafos. (versão nova no Moodle)
Fazer, da Seção 2.1 – Caminhos e circuitos, os Exercı́cios 74–86.
2. P. Feofiloff, Y. Kohayakawa e Y. Wakabayashi, Uma introdução sucinta à Teoria dos grafos.
(cópia no Moodle)
Fazer, das Seções 1.3 e 1.5–1.7, os Exercı́cios E1.16–E1.18 e E1.30–E1.42 (menos E1.34 e E1.35)
(Obs: Circuitos para eles é ciclo para nós!)
3. a) Mostre que se um grafo G é desconexo, então o seu complementar GC é conexo. Vale a volta?
b) Um grafo é dito auto–complementar se ele é isomorfo ao seu complementar. Mostre que P4 ,
o caminho de comprimento 4, C5 , o ciclo de comprimento 5, e L(K3,3 ), o grafo aresta do
grafo bipartido completo K3,3 , são grafos auto–complementares.
c) Mostre que todo grafo auto–complementar é conexo.
4. Forneça o número de automorfismos do K3,3 , ou seja, número de isomorfismos distintos h :
K3,3 → K3,3 . Fazer o mesmo com K4 , P5 e C6 .
5. Mostre que um isomorfismo de grafos preserva:
a) Vértice e aresta adjacência para vértices e arestas isomorfos.
b) Grau de vértices isomorfos.
c) Grau mı́nimo e máximo.
d) Subgrafo, subgrafo gerador e induzido (na ida, como na volta).
e) Clique, conjunto independente, cobertura, corte, k–partição (na ida, como na volta).
f ) α(·), β(·), ω(·) e χ(·).
g) Passeios, caminhos, circuitos e ciclos (na ida, como na volta).
h) Cintura, circunferência e diâmetro.
i) Conexidade (na ida, como na volta).
j) Árvore (na ida, como na volta).
6. Seja KGn,r o Grafo de Kneser, ou seja, os vértices são todos os subconjuntos de r elementos
do conjunto {1, 2, . . . , n} e as arestas interligam subconjuntos disjuntos. Forneça os isomorfismos:
a) KGn,1 ∼
= Kn , para n ≥ 3 e
∼
b) KGn,2 = LC (Kn ) (o grafo complementar do grafo aresta do grafo n–completo), para n ≥ 5.
7. Seja G um grafo com n vértices, m arestas e c componentes conexas.
a) Quantos subgrafos geradores tem G?
b) Quantas arestas é necessário acrescentar em G para torná-lo conexo?
c) Quantos subgrafos induzidos tem G?
1
8. Prove ou refute: Um subgrafo induzido de um grafo aresta é um grafo aresta.
.
9. Seja G := (A ∪ B, E) um grafo bipartido sem vértices isolados e com d(a) ≥ d(b), para todos
a ∈ A e b ∈ B adjacente. Prove ou refute: |A| ≥ |B|.
Sugestão: Tome duas matrizes, MA e MB , e indexe as suas linhas pelos vértices a ∈ A e as
suas colunas pelos vértices b ∈ B (assim ambas matrizes são |A| × |B|). Em cada entrada de MA
coloque 1/d(a) se a e b são adjacentes e 0 caso contrário. Em MB coloque analogamente 1/d(b).
De um lado, some todas as entradas de MA começando pelas linhas, de outro lado, some todas
as entradas de MB começando pelas colunas. Use a desigualdade para comparar estas somas.
10. Para o Grafo de Petersen G := KG5,2 , calcule (e demonstre) a cintura (i.e., comprimento
de um menor ciclo), a circunferência (i.e., comprimento de um maior ciclo), o diâmetro (i.e.,
comprimento de um maior caminho), αG (i.e., o ı́ndice de independência), βG (i.e., tamanho de
uma cobertura mı́nima), ωG (i.e., tamanho de um clique máximo) e χG (i.e., o maior número de
classes de uma partição).
11. Mostre que um grafo k–regular de cintura 4 precisa ter pelo menos 2k vértices. Determine todos
estes possı́veis grafos com exatamente 2k vértices.
12. Seja G um grafo.
a) Um passeio P é um subgrafo de G composto por uma seqüência de vértices (v0 , v1 , . . . , vk ),
com k ∈ N e vi ∈ VG , para todo i := 0..k e arestas vi−1 vi ∈ EG , para todo i := 1..k.
Denotamos P := (v0 , v1 , . . . , vk ). Os vértices v0 e vk são chamados de extremos de P e
os demais vértices, de internos a P . Este passeio P também é dito um v0 , vk –passeio. O
comprimento de P é definido e denotado por lhP := k. Um passeio P é um dito caminho
se todos os vértices vi ’s são distintos entre si, menos possivelmente os dois extremos v0 e vk .
Demonstre —obrigatoriamente por indução finita— que todo x, y–passeio tem um subgrafo
que é um x, y–caminho.
b) Um passeio C := (v1 , v2 , . . . , vk ), com k ∈ N∗ , k ≥ 2, quando acrescido da aresta v1 vk ∈ EG ,
é dito um circuito. O seu comprimento é lhC := k (note que o circuito começa com v1 ). Se
todos os vértices vi ’s são distintos entre si e k ≥ 3, dizemos que C é um ciclo. Demonstre que
se k ≥ 3 e C := (v1 , v2 , . . . , vk ) é um circuito com ao menos uma das suas arestas ocorrendo
somente uma vez em C, então C tem um subgrafo que é um ciclo.
c) Se para dois vértices distintos x, y ∈ VG existem dois x, y–passeios distintos de comprimento
k1 e k2 resp., então demonstre que G tem um ciclo de comprimento no máximo k1 + k2 .
13. a) Mostre que toda árvore tem pelo menos uma folha (e se ela tem pelo menos 2 nós, esta folha
é distinta da raiz).
b) Se G é um grafo conexo, mostre que podemos ordenar todos os seus vértices (v1 , v2 , , vnG ) de
tal modo que Gi := G[v1 , v2 , , vi ] é conexo e vi tem um vizinho em Gi−1 , para todo i := 2..nG .
c) Se T é uma árvore, mostre que a ordem acima é tal que Ti := T [v1 , v2 , , vi ] é uma árvore e vi
tem um só vizinho em Ti−1 , para todo i := 2..nT .
d) Mostre de dois modos diferentes, um usando o Item a) e outro usando o Item c) que se T é
uma árvore, então mT = nT − 1.
e) Utilize o fato de que uma árvore é um conexo aresta–minimal para mostra que se T é conexo
com mT = nT − 1, então T é uma árvore.
Sugestão: Tome a sub–árvore geradora de T .
14. Mostre que uma árvore T tem pelo menos ∆(T ) folhas.
2
15. Se G é um grafo conexo e P é um caminho de comprimento maximal em G, então G − VP (o
grafo induzido por VG \ VP ) tem diâmetro menor do que o diâmetro de G. O mesmo continua
válido se G não é conexo?
16. Dado um grafo G, mostre que existe um subconjunto independente SG ⊆ VG de G tal que todo
vértice de G tem distância no máximo 2 de algum vértice de SG .
Sugestão: Faça indução no número de vértices de G. Se nG ≤ 3, é trivial. Caso contrário, para
um vértice v ∈ VG , defina N (v) := ΓG (v) ∪ {v}. Tome H o subgrafo induzido de G sobre os
vértices no complementar de N (v) em G (i.e., VH := VG \ N (v)). Por indução, seja SH ⊆ VH
o subconjunto independente de H que satisfaz o exercı́cio. Assim todos os vértices de H são
alcançados por um vértice de SH através de um caminho de comprimento ≤ 2. Precisamos
assim alcançar também os vértices em N (v). Divida em dois casos: Se SH ∪ {v} é subconjunto
independente, então tome SG := SH ∪ {v}. Caso contrário, tome SG := SH .
17. a) Para um grafo G, se mG ≥ nG + 4, então mostre que G tem dois circuitos aresta–disjuntos.
b) Ache um grafo G com nG ≥ 5, mG = nG + 3 e que não tenha dois circuitos aresta–disjuntos.
Atenção: Certifique-se que você está justificando tudo, absolutamente tudo, com muita precisão e
cuidado.
Claus
3